前文知識(shí)清單：

一、選擇排序

直接選擇排序通過(guò)每一輪的比較，找到最大值和最小值，將最大值的節(jié)點(diǎn)跟右邊交換，最小值節(jié)點(diǎn)跟左邊交換，達(dá)到排升序的效果。

一圖看懂直接選擇排序：

void SelectSort(ShellDataType* a, int n)
{
	//左下標(biāo) 和右下標(biāo)
	int left = 0;
	int right = n - 1;
	
	//不需要left <= right，最后一個(gè)元素不需要再交換,當(dāng)然給<=也沒(méi)問(wèn)題
	while (left < right)
	{
		//假設(shè)最小最大全部在left
		int mini = left, maxi = left;
		//單趟查找最小值和最大值下標(biāo)
		for (int i = left; i < right; i++)
		{
			//找到最小的，更新下標(biāo)
			if (a[i] < a[mini])
			{
				mini = i;
			}
			//找到最大的，更新下標(biāo)
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		//maxi和right交換，mini和left交換

		Swap(&a[left], &a[mini]);
		//這里存在特殊情況，如果maxi在left位置，left和mini交換了之后，最大值的下標(biāo)就是mini了
		//所以這里需要判斷一下，如果真的是這種情況，就更新最大值下標(biāo)。
		if (maxi == left)
		{
			maxi = mini;
		}
		Swap(&a[right], &a[maxi]);
		//后面的不需要再更新了，因?yàn)楹竺婢退鉳ini是在right位置，這輪也已經(jīng)結(jié)束了，所以不需要再管它

		//更新left和right 的下標(biāo)
		left++;
		right--;
	}

}

直接選擇排序時(shí)間復(fù)雜度

每一輪比較都需要遍歷數(shù)組，查找最大最小值，第一輪遍歷N個(gè)數(shù)據(jù)，第二輪是N-2個(gè)數(shù)據(jù)，第三輪N-4 …，遍歷次數(shù)為：N+N-2+N-4+…+1，一個(gè)等差數(shù)列求和

所以總的時(shí)間復(fù)雜度為O(N^2)

二、堆排序

向上調(diào)整算法和向下調(diào)整算法請(qǐng)參照：數(shù)據(jù)結(jié)構(gòu)——堆

所謂堆排序，就是排序堆，要求是堆才能夠進(jìn)行排序，所以給任意一個(gè)連續(xù)數(shù)組對(duì)數(shù)組排序的話(huà)，需要先建堆。

使用向上調(diào)整法建堆如下圖：

結(jié)果如下：

時(shí)間復(fù)雜度為O(N*logN)

使用向下調(diào)整建堆如下圖：

時(shí)間復(fù)雜度O(N)

堆排序：

堆排序使用交換之后再向下調(diào)整原理：
在建了大根堆之后，堆頂?shù)淖笥易訕?shù)都是大根堆，不管最后一個(gè)元素是否是最小的，與堆頂元素交換后,
堆頂元素就被放到了堆尾，然后再讓堆頂元素向下調(diào)整，因?yàn)榇藭r(shí)堆頂元素是一個(gè)較小的元素，會(huì)向下調(diào)整，調(diào)整之后是第二大的元素在堆頂下一次再排序時(shí)，排的是堆尾的前一個(gè)了，那個(gè)最大的元素不用再排了，排的就是第二大的元素，
再讓堆的最后一個(gè)元素與堆頂元素交換，再進(jìn)行向下調(diào)整，調(diào)整完后第三大的元素就上來(lái)了。

建好堆后，對(duì)堆進(jìn)行排序，堆排序過(guò)程圖如下：

堆排序代碼如下：

void HeapSort(int* a, int n)
{
	
	assert(a);

	//1.先建堆，向上調(diào)整建堆,建堆的時(shí)間復(fù)雜度為O(N*logN)
	
	//也可以采用向下調(diào)整的方法建堆，向下調(diào)整的方法建堆的時(shí)間復(fù)雜度為O(N)
	//強(qiáng)烈建議采用向下調(diào)整的建堆方式
	//for (int i = 0; i < n; ++i)
	//{
	//	AdjustUp(a, i);
	//}
	//向下調(diào)整建堆，是從第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始調(diào)整，因?yàn)樗械娜~子節(jié)點(diǎn)都不需要進(jìn)行向下調(diào)整
	//child = (parent-1)/2
	//此時(shí)parent就是n-1
	for (int i = (n - 1 - 1) / 2; i >=0; -- i)
	{
		AdjustDown(a, n, i);
	}
	//現(xiàn)在是大根堆
	
	//2.堆排序，采用向下調(diào)整算法進(jìn)行排序,讓最后一個(gè)節(jié)點(diǎn)和堆頂節(jié)點(diǎn)進(jìn)行交換，然后堆頂節(jié)點(diǎn)向下調(diào)整
	//調(diào)整完后繼續(xù)倒數(shù)第二個(gè)節(jié)點(diǎn)和堆頂節(jié)點(diǎn)交換,以此類(lèi)推

	for (int i = n-1; i >0; --i)
	{
		swap(&a[0], &a[i]);
		//這里傳參不能傳n，傳n-1,因?yàn)榻粨Q之后最后一個(gè)數(shù)字就不需要參與進(jìn)來(lái)了，相當(dāng)于size--
		//堆排序使用交換之后再向下調(diào)整原理：
		//在建了大根堆之后，堆頂?shù)淖笥易訕?shù)都是大根堆，不管最后一個(gè)元素是否是最小的，與堆頂元素交換后
		//堆頂元素就被放到了堆尾，然后再讓堆頂元素向下調(diào)整，因?yàn)榇藭r(shí)堆頂元素是一個(gè)較小的元素，會(huì)向下調(diào)整，調(diào)整之后是第二大的元素在堆頂
		// 
		//下一次再排序時(shí)，排的是堆尾的前一個(gè)了，那個(gè)最大的元素不用再排了，排的就是第二大的元素，
		//再讓堆的最后一個(gè)元素與堆頂元素交換，再進(jìn)行向下調(diào)整，調(diào)整完后第三大的元素就上來(lái)了。
		AdjustDown(a, i, 0);
	}
	//總結(jié)：排升序的話(huà)，建大根堆
	//排降序建小根堆

	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

堆排序時(shí)間復(fù)雜度

建堆的時(shí)間復(fù)雜度為O(N)
調(diào)整過(guò)程遍歷N個(gè)數(shù)的時(shí)間復(fù)雜度為O(N)
每次調(diào)整一個(gè)數(shù)的時(shí)間復(fù)雜度為O(logN)
總的時(shí)間復(fù)雜度為O(N+N*logN)
綜上：

堆排序的時(shí)間復(fù)雜度為：O(N*logN)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-413943.html

到了這里，關(guān)于【一圖看懂選擇排序】——選擇排序和堆排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！