一.冒泡排序

1.1冒泡排序引入

對(duì)于任何編程語(yǔ)言，當(dāng)我們學(xué)到循環(huán)和數(shù)組的時(shí)候，都會(huì)介紹一種排序算法：冒泡排序；深入學(xué)習(xí)更多排序算法后和在實(shí)際使用情況中，冒泡排序的使用還是極少的。它適合數(shù)據(jù)規(guī)模很小的時(shí)候，而且它的效率也比較低，但是作為入門的排序算法，還是值得學(xué)習(xí)的。

1.2冒泡排序的核心思想與算法分析

核心思想：相鄰的元素兩兩比較，較大的數(shù)下沉，較小的數(shù)冒起來，這樣一趟比較下來，最大(小)值就會(huì)排列在一端。

因?yàn)檩^大的數(shù)會(huì)下沉，所以我們也可以將冒泡排序稱作沉石排序。

算法分析：

• 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)；
• 每趟從第一對(duì)相鄰元素開始，對(duì)每一對(duì)相鄰元素作同樣的工作，直到最后一對(duì)；
• 針對(duì)所有的元素重復(fù)以上的步驟，除了已排序過的元素(每趟排序后的最后一個(gè)元素)，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

1.3實(shí)例說明

以3，2，5，6，1，11為例子，排序過程：

• 底部畫線的為已確定的數(shù)據(jù)
• 有n個(gè)數(shù)據(jù)，需要跑n-1趟即可

1.4優(yōu)化

上面的排序過程在第四趟處理完時(shí)，就已經(jīng)完全有序了（肉眼觀察的），理應(yīng)直接退出循環(huán)即可，第五趟順序完全可以省略，那么我們就會(huì)有一個(gè)問題：

怎樣判斷數(shù)據(jù)完全有序？

從先到后遍歷一遍，發(fā)現(xiàn)數(shù)據(jù)兩兩比較都是前面小于后面（沒有交換操作），這個(gè)時(shí)候，就可以判定數(shù)據(jù)已經(jīng)完全有序。

1.5代碼實(shí)現(xiàn)

void BubbleSort(int* arr, int len)
{
	int count = 0;
	bool tag = true;//標(biāo)記  首先賦初值為真
	//從頭到尾遍歷一般，沒有交換操作，則可以認(rèn)定完全有序
	//反過來說：只要有一次交換操作，則不能認(rèn)定完全有序
	for (int i = 0; i < len - 1; i++)//需要多少趟
	{
		tag = true;//注意：不要忘，每一趟開始的時(shí)候，記得將tag重新置為true
		for (int j = 0; j + 1 < len - i; j++)//控制兩兩比較   j指向兩兩比較的開始位置
		{
			if (arr[j] > arr[j + 1])
			{
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
				tag = false;
			}
		}
		count++;
		if (tag)//如果一趟跑完之后，發(fā)現(xiàn)tag沒有變，還是真，則代表沒有前面大于后面的情況發(fā)生，則已經(jīng)完全有序
		{
			break;
		}
	}
	printf("%d\n", count);
}

1.6性能分析

• 時(shí)間復(fù)雜度：o（n^2）；
• 空間復(fù)雜度：o（1）；
• 穩(wěn)定性：穩(wěn)定

二.堆排序

2.1堆的基礎(chǔ)知識(shí)

2.1.1堆是什么

堆是一種數(shù)據(jù)結(jié)構(gòu)，一種叫做完全二叉樹的數(shù)據(jù)結(jié)構(gòu)。

2.1.2堆的性質(zhì)

這里我們用到兩種堆，其實(shí)也算是一種。

大頂堆：每個(gè)節(jié)點(diǎn)的值都大于或者等于它的左右子節(jié)點(diǎn)的值。

小頂堆：每個(gè)節(jié)點(diǎn)的值都小于或者等于它的左右子節(jié)點(diǎn)的值。

查找數(shù)組中某個(gè)數(shù)的父結(jié)點(diǎn)和左右孩子結(jié)點(diǎn)，比如已知索引為i的數(shù)，那么

1.父結(jié)點(diǎn)索引：(i-1)/2（這里計(jì)算機(jī)中的除以2，省略掉小數(shù)）

2.左孩子索引：2*i+1

3.右孩子索引：2*i+2

如下圖所示：

兩種堆就是如上圖所示。

如果我們把這種邏輯結(jié)構(gòu)映射到數(shù)組中，如下所示：

大頂堆：

小頂堆：

從這里我們可以得出以下性質(zhì)：

對(duì)于大頂堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

對(duì)于小頂堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

2.2堆排序的核心思想與基本步驟

核心思想：將無(wú)序數(shù)組構(gòu)造成一個(gè)大頂堆，固定一個(gè)最大值，將剩余的數(shù)重新構(gòu)造成一個(gè)大頂堆，重復(fù)這樣的過程構(gòu)造堆。

基本步驟：

1. 將帶排序的序列構(gòu)造成一個(gè)大頂堆，根據(jù)大頂堆的性質(zhì)，當(dāng)前堆的根節(jié)點(diǎn)（堆頂）就是序列中最大的元素；
2. 將堆頂元素和最后一個(gè)元素交換，然后將剩下的節(jié)點(diǎn)重新構(gòu)造成一個(gè)大頂堆；
3. 重復(fù)步驟2，如此反復(fù)，從第一次構(gòu)建大頂堆開始，每一次構(gòu)建，我們都能獲得一個(gè)序列的最大值，然后把它放到大頂堆的尾部；
4. 最后，就得到一個(gè)有序的序列了。

2.3實(shí)例說明與分析

以4，5，8，2，3，9，7，1為例，按照上面的基本步驟進(jìn)行排序，過程如下：

1.將無(wú)序序列構(gòu)造為一個(gè)大頂堆

2.現(xiàn)在我們需要找到最后一個(gè)非葉子節(jié)點(diǎn)的位置，也就是索引值。

對(duì)于一個(gè)完全二叉樹，在填滿的情況下，每一層的元素個(gè)數(shù)是上一層的二倍，根節(jié)點(diǎn)數(shù)量是1，所以最后一層的節(jié)點(diǎn)數(shù)量，一定是之前所有層節(jié)點(diǎn)總數(shù)+1，所以，我們能找到最后一層的第一個(gè)節(jié)點(diǎn)的索引，即節(jié)點(diǎn)總數(shù)/2（根節(jié)點(diǎn)索引為0），這也就是第一個(gè)葉子節(jié)點(diǎn)，所以第一個(gè)非葉子節(jié)點(diǎn)的索引就是第一個(gè)葉子結(jié)點(diǎn)的索引-1。

那么對(duì)于填不滿的二叉樹呢？這個(gè)計(jì)算方式仍然適用，當(dāng)我們從上往下，從左往右填充二叉樹的過程中，第一個(gè)葉子節(jié)點(diǎn)，一定是序列長(zhǎng)度/2，所以第一個(gè)非葉子節(jié)點(diǎn)的索引就是（數(shù)組長(zhǎng)度/ 2 -1）。

現(xiàn)在找到了最后一個(gè)非葉子節(jié)點(diǎn)，即元素值為2的節(jié)點(diǎn)，比較它的左右節(jié)點(diǎn)的值，是否比他大，如果大就換位置。這里因?yàn)?<2，所以，不需要任何操作，繼續(xù)比較下一個(gè)，即元素值為8的節(jié)點(diǎn)，它的左節(jié)點(diǎn)值為9比它本身大，所以交換。

3.因?yàn)樵?沒有子節(jié)點(diǎn)，所以繼續(xù)比較下一個(gè)非葉子節(jié)點(diǎn)，元素值為5的節(jié)點(diǎn)，它的兩個(gè)子節(jié)點(diǎn)值都比本身小，不需要調(diào)整；然后是元素值為4的節(jié)點(diǎn)，也就是根節(jié)點(diǎn)，因?yàn)?>4，所以需要調(diào)整位置

4.原來元素值為9的節(jié)點(diǎn)值變成4了，而且它本身有兩個(gè)子節(jié)點(diǎn)，所以，這時(shí)需要再次調(diào)整該節(jié)點(diǎn)

5.排序序列，將堆頂?shù)脑刂岛臀膊康脑亟粨Q

6.將剩余的元素重新構(gòu)建大頂堆，其實(shí)就是調(diào)整根節(jié)點(diǎn)以及其調(diào)整后影響的子節(jié)點(diǎn)，因?yàn)槠渌?jié)點(diǎn)之前已經(jīng)滿足大頂堆性質(zhì)

7.繼續(xù)交換，堆頂節(jié)點(diǎn)元素值為8與當(dāng)前尾部節(jié)點(diǎn)元素值為1的進(jìn)行交換

8.重新構(gòu)建大頂堆

9.重復(fù)交換

10.重新構(gòu)建大頂堆

11.重復(fù)交換

12.重新構(gòu)建大頂堆

13.重復(fù)交換

14.重新構(gòu)建大頂堆

15.重復(fù)交換

16.重新構(gòu)建大頂堆

17.重復(fù)交換

18.重新構(gòu)建大頂堆

19.繼續(xù)交換

這里我么就交換結(jié)束了 得到了最后的結(jié)果。

2.4代碼實(shí)現(xiàn)

void HeapAdjust(int arr[], int start, int end)
{
	//assert
	int tmp = arr[start];
	for (int i = start * 2 + 1; i <= end; i = start * 2 + 1)//start*2+1 相當(dāng)于是start這個(gè)節(jié)點(diǎn)的左孩子
	{                     //i<end  退出for循環(huán)  觸發(fā)的是情況1
		if (i<end && arr[i + 1] > arr[i])//i<end 代表存在右孩子，且右孩子的值還大于左孩子
		{
			i++;//則此時(shí)，讓i指向右孩子
		}
		//此時(shí)i肯定已經(jīng)指向較大的那個(gè)孩子
		if (arr[i] > tmp)//子大于父
		{
			arr[start] = arr[i];
			start = i;
		}
		else
		{
			break;//退出for循環(huán)，觸發(fā)情況2
		}
	}
	arr[start] = tmp;
}
void HeapSort(int* arr, int len)
{
	//1.整體從最后一個(gè)非葉子節(jié)點(diǎn)開始由內(nèi)到外調(diào)整一次
	//首先需要知道最后一個(gè)非葉子節(jié)點(diǎn)的下標(biāo)
	for (int i = (len - 1 - 1) / 2; i >= 0; i--)//因?yàn)樽詈笠粋€(gè)非葉子節(jié)點(diǎn)肯定是 最后一個(gè)葉子節(jié)點(diǎn)的父節(jié)點(diǎn)
	{
		HeapAdjust(arr, i, len - 1);//調(diào)用我們一次調(diào)整函數(shù)  //這里第三個(gè)值比較特殊，沒有規(guī)律可言，則直接給最大值len-1
	}
	//此時(shí)，已經(jīng)調(diào)整為大頂堆了
	//接下來，根節(jié)點(diǎn)的值和當(dāng)前最后一個(gè)節(jié)點(diǎn)的值進(jìn)行交換，然后將尾結(jié)點(diǎn)剔除掉
	for (int i = 0; i < len - 1; i++)
	{
		int tmp = arr[0];
		arr[0] = arr[len - 1 - i];//len-1-i 是我們當(dāng)前的尾結(jié)點(diǎn)下標(biāo)
		arr[len - 1 - i] = tmp;
		HeapAdjust(arr, 0, (len - 1 - i) - 1);//len-1-i 是我們當(dāng)前的尾結(jié)點(diǎn)下標(biāo)，然后再給其-1則相當(dāng)于將其剔除出我們的循環(huán)
	}
}

2.5性能分析

1. 時(shí)間復(fù)雜度：最好和最壞的情況時(shí)間復(fù)雜度都是（n*logn） 。
2. 空間復(fù)雜度：O（1）。
3. 穩(wěn)定性：不穩(wěn)定。

到此這篇關(guān)于C語(yǔ)言深入探究冒泡排序與堆排序使用案例講解的文章就介紹到這了,更多相關(guān)C語(yǔ)言排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！