欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序圖文示例

 更新時(shí)間:2022年05月10日 17:53:57   作者:_奇奇  
這篇文章主要為大家介紹了C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序的圖文示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

“大弦嘈嘈如急雨,小弦切切如私語”“嘈嘈切切錯(cuò)雜彈,大珠小珠落玉盤”

C語言朱武大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)專欄

C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)快速排序圖文示例

C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)希爾排序算法

C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹遞歸

TOP.堆排序前言

什么是堆排序?假如給你下面的代碼讓你完善堆排序,你會(huì)怎么寫?你會(huì)怎么排?

void HeapSort(int* a, int n)
{
}
int main()
{
	int arr[] = { 4,2,7,8,5,1,0,6 };
	int sz = sizeof(arr) / sizoef(arr[0]);
	HeapSort(arr, sz);
	return 0;
}

堆排序就是利用堆這個(gè)數(shù)據(jù)結(jié)構(gòu),對(duì)一組數(shù)據(jù)進(jìn)行排序。

所以說,堆排序整體分兩步完成。

第一步,建堆

第二步,進(jìn)行排序

注意:以下代碼針對(duì)的是對(duì)一組 數(shù)據(jù) 排升序

一、向下調(diào)整堆排序

對(duì)的,向下調(diào)整方法,是最優(yōu)秀的堆排序。

不是太想介紹那種向上調(diào)整拉胯的堆排序,我們經(jīng)常用的是這種優(yōu)秀的向下排序。

二者區(qū)別在于建堆的方法不同。一個(gè)是向下建堆O(N),一個(gè)是向上建堆O(N*logN)。

具體證明用到了高中 簡單的數(shù)列公式。

1.向下調(diào)整建堆

建堆的技巧

向下建堆也有兩種情況。

1.建大堆

2.建小堆

那么到底建大堆還是小堆呢?

解釋:建堆在于你是想要排升序,還是排降序。假如建的大堆,因?yàn)槎秧數(shù)臄?shù)是最大的,在我們對(duì)堆 向下調(diào)整排序時(shí),這時(shí)候每次都需要把最大的交換到堆底。所以導(dǎo)致最后堆的順序是升序。

建大堆前

建大堆后

向下調(diào)整排序后

此時(shí)數(shù)組就有序了。

結(jié)論:實(shí)質(zhì)是在數(shù)組上建堆。排升序建大堆,排降序建小堆。

建堆思路代碼

思路:

因?yàn)槿~子結(jié)點(diǎn)本身就是一個(gè)大堆,所以從最后一個(gè)葉子結(jié)點(diǎn)的父親結(jié)點(diǎn)開始進(jìn)行向下建堆。

這樣就能夠保證每次建的堆都是大堆。

注意:

1.注意循環(huán)結(jié)束條件,和if語句里的邊界問題child + 1 < n

2.注意完全二叉樹父子關(guān)系公式

#include <stdio.h>
//交換
void swap(int* x, int* y)
{
	int t = 0;
	t = *x;
	*x = *y;
	*y = t;
}
//向下調(diào)整
void AdjustDown(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child  < n)
	{
		//每次調(diào)整都需要從左右兩邊選出孩子最大的那個(gè)
		//假設(shè)坐孩子較大,選出左右孩子大的那個(gè)
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		//開始調(diào)整。
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		//不滿足就跳出,開始下次for循環(huán)調(diào)整。
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	//向下調(diào)整建堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
}
int main()
{
	int arr[] = { 4,2,7,8,5,1,0,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr, sz);
	return 0;
}

2.向下調(diào)整排序

調(diào)整思路

1.從堆底依次 和 堆頂?shù)臄?shù)據(jù)進(jìn)行交換。

2.對(duì)交換后的 堆頂?shù)闹?進(jìn)行向下調(diào)整。向下調(diào)整時(shí)請(qǐng)無視交換到堆底那個(gè)最大的值。

3.繼續(xù)循環(huán)第一步和第二步,直到到正數(shù)第二個(gè)數(shù)結(jié)束。

排序整體代碼

void swap(int* x, int* y)
{
	int t = 0;
	t = *x;
	*x = *y;
	*y = t;
}
void AdjustDown(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child  < n)
	{
		//每次調(diào)整都需要從左右兩邊選出孩子最大的那個(gè)
		//假設(shè)坐孩子較大,選出左右孩子大的那個(gè)
		if (child + 1 < n && a[child + 1] > a[child])
		{
			++child;
		}
		//開始調(diào)整。
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		//不滿足就跳出,開始下次for循環(huán)調(diào)整。
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	//向下調(diào)整建堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//向下調(diào)整排序
	int end = 0;
	for (end = n-1; end > 0; end--)
	{
		swap(&a[0], &a[end]);
		//向下調(diào)整時(shí)無視最大的那個(gè)值,所以end是n-1。
		AdjustDown(a, end, 0);
	}
}
int main()
{
	int arr[] = { 4,2,7,8,5,1,0,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr, sz);
	return 0;
}

3.時(shí)間復(fù)雜度(難點(diǎn))

向下建堆O(N)

//向下調(diào)整建堆
	int i = 0;
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

很多人的誤區(qū)在于他的時(shí)間復(fù)雜度是N*Log2N。這是錯(cuò)誤的。

時(shí)間復(fù)雜度的計(jì)算是看思想,而不是看循環(huán)猜測(cè)。

當(dāng)是滿二叉樹,在最壞的情況下,除了最后一層,上面所有層都需要進(jìn)行向下調(diào)整。

最壞情況下的調(diào)整次數(shù) = 每層數(shù)據(jù)個(gè)數(shù) * 向下調(diào)整次數(shù)

第一層向下調(diào)整次數(shù)是h-1,節(jié)點(diǎn)個(gè)數(shù)是21-1

第二層向下調(diào)整次數(shù)是h-2, 節(jié)點(diǎn)個(gè)數(shù)是22-1

第h-1層向下調(diào)整次數(shù)是1,節(jié)點(diǎn)個(gè)數(shù)是2h-1-1

所以總的調(diào)整次數(shù)為n:n = 20*(h-1) + 21 *(h-2)+… + 2h-1-1 *(1)

根據(jù)高中錯(cuò)位相減得到 n = 1−h+21+22+…+2h−2+2h−1

由等比數(shù)列前n項(xiàng)和得到 n = 2h−h−1

由二叉樹性質(zhì)N=2h−1和 h = log2(N+1) 得到 n=N−log2?(N+1)

大O漸進(jìn)表示法為n= O(N)

向下調(diào)整(N*LogN)

需要向下調(diào)整n-1次。每次需要調(diào)整的高度為LogN,N為節(jié)點(diǎn)的個(gè)數(shù),因?yàn)楣?jié)點(diǎn)個(gè)數(shù)每次少一個(gè)。

所以n-1次調(diào)整總次數(shù) = log2+log3+…+log(n-1)+log(n)≈log(n!)

由數(shù)學(xué)知識(shí)得log(n!)和nlog(n)是同階函數(shù)。

所以向下調(diào)整排序時(shí)間復(fù)雜度為N*LogN

所以堆排序時(shí)間復(fù)雜度為:N + N*LogN

大O漸進(jìn)表示法為:O(N*LogN)

總結(jié):堆排序時(shí)間復(fù)雜度 O(N*LogN)

二、向上調(diào)整堆排序

向上調(diào)整排序和向下調(diào)整排序的唯一不同在于建堆的不同,導(dǎo)致二者的建堆的時(shí)間復(fù)雜度略微不同。

1.向上調(diào)整建堆

向上調(diào)整建堆時(shí)間復(fù)雜度為N*LogN.具體原因還需要經(jīng)過殘酷的數(shù)學(xué)計(jì)算。孩子不會(huì)啊。但是經(jīng)過網(wǎng)上查閱資料我又找到了計(jì)算方法。如圖。

根據(jù)二叉樹的性質(zhì):h = Log2(N+1)

可以將T(h) = 2h * (h-2) + 2換為:

所以總體來說就是向上調(diào)整的建堆時(shí)間復(fù)雜度為O(N * LogN).

2.建堆代碼

思路:從第二個(gè)元素開始,只關(guān)注前兩個(gè)元素建堆,然后再依次增加元素建堆,使它一直為堆。

向上調(diào)整建堆雖然時(shí)間復(fù)雜度略高,但是代碼相對(duì)于向下調(diào)整簡單一點(diǎn)點(diǎn)。

void AdjustUp(int* a, int child)
{
	//先把父親節(jié)點(diǎn)表示出來。
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//比較孩子和父親,開始向上調(diào)整。
		if (a[child] > a[parent])
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

以上就是C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)堆排序圖文示例的詳細(xì)內(nèi)容,更多關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)堆排序的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • C語言刪除輸入字符串中的空格示例代碼

    C語言刪除輸入字符串中的空格示例代碼

    最近工作中遇到了需求,要?jiǎng)h除字符串中的所有空格,就要篩選出空格字符,這篇文章主要給大家介紹了關(guān)于利用C語言刪除輸入字符串中的空格的相關(guān)資料,需要的朋友可以參考下
    2022-12-12
  • C++函數(shù)重載詳解及實(shí)例代碼

    C++函數(shù)重載詳解及實(shí)例代碼

    這篇文章主要介紹了C++函數(shù)重載詳解及實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下
    2016-09-09
  • 詳解C++編程中類的成員變量和成員函數(shù)的相關(guān)知識(shí)

    詳解C++編程中類的成員變量和成員函數(shù)的相關(guān)知識(shí)

    這篇文章主要介紹了C++編程中類的成員變量和成員函數(shù)的相關(guān)知識(shí),是C++入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下
    2015-09-09
  • C語言中的文件操作詳解

    C語言中的文件操作詳解

    這篇文章主要介紹了C語言中的文件操作詳解,使用文件可以將數(shù)據(jù)直接存放到電腦的硬盤上,做到了數(shù)據(jù)的持久化
    2022-07-07
  • C++實(shí)現(xiàn)校園導(dǎo)游系統(tǒng)

    C++實(shí)現(xiàn)校園導(dǎo)游系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)校園導(dǎo)游系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • c++中引用和指針的區(qū)別和聯(lián)系

    c++中引用和指針的區(qū)別和聯(lián)系

    許多人對(duì)于引用和指針的區(qū)別與聯(lián)系很糾結(jié)(包括我在內(nèi)O(∩_∩)O哈哈~),最近看到一篇關(guān)于引用和指針區(qū)別和聯(lián)系的文章,感覺茅塞頓開,在這里和大家分享下
    2014-04-04
  • 基于memset()函數(shù)的深入理解

    基于memset()函數(shù)的深入理解

    本篇文章是對(duì)memset()函數(shù)又進(jìn)行了深一步的了解,需要的朋友參考下
    2013-05-05
  • C語言圖書管理系統(tǒng)實(shí)驗(yàn)

    C語言圖書管理系統(tǒng)實(shí)驗(yàn)

    這篇文章主要為大家詳細(xì)介紹了C語言圖書管理系統(tǒng)實(shí)驗(yàn),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • opencv+arduino實(shí)現(xiàn)物體點(diǎn)追蹤效果

    opencv+arduino實(shí)現(xiàn)物體點(diǎn)追蹤效果

    這篇文章主要為大家詳細(xì)介紹了opencv+arduino實(shí)現(xiàn)物體點(diǎn)追蹤效果,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-01-01
  • C++超集C++/CLI模塊的基本用法

    C++超集C++/CLI模塊的基本用法

    這篇文章介紹了C++超集C++/CLI模塊的基本用法,對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-07-07

最新評(píng)論