選擇排序：每趟從待排序的記錄中選出關(guān)鍵字最小的記錄，順序放在已排序的記錄序列末尾，直到全部排序結(jié)束為止。

選擇排序正如定義所講，在數(shù)組查詢出最小值，然后放在此次循環(huán)開始位置（前一次循環(huán)已經(jīng)獲取比它更小的值放在前面）。

簡單選擇排序就是單純的從數(shù)組中一次一次循環(huán)獲取到最小值，放到循環(huán)位置。而堆排序正如名字，是從一個(gè)堆中選擇，然后放在堆的循環(huán)開始位置，所以重點(diǎn)就是如何爭取獲取堆（分組）。

一、簡單選擇排序

1、算法思想

正如圖上所示，每次選擇最小值，然后放在本次循環(huán)的開始位置。

2、代碼

//選擇排序 void SortAlgorithm::SelectSort(pSqlList pList) {int i,j,min;printf("開始驗(yàn)證選擇排序");//選擇排序和低級冒泡排序很像，關(guān)鍵就是在比較時(shí)，低級冒泡進(jìn)行數(shù)據(jù)交換，而選擇排序進(jìn)行記錄，最后只交換一次for (i =0;i<pList->length;i++){min = i;for(j = pList->length-1;j>=i;j--){//注意數(shù)組坐標(biāo)，千萬別溢出if (pList->SqlArray[min] > pList->SqlArray[j]){min = j;}}//最后進(jìn)行交換，先選擇最小的，最后一次交換 swap(pList,i,min);PrintSqlList(pList);}}

簡單選擇排序算法海華絲比較簡單，關(guān)鍵點(diǎn)就是遍歷尋找最小記錄，然后入循環(huán)開始位置進(jìn)行交換。

二、堆排序

1、堆排序概念

堆排序是首先引入完全二叉樹的概念，就是構(gòu)建完全二叉樹，前提是完全二叉樹是有特點(diǎn)的，也就是大根堆和小根堆。

上圖是完全二叉樹，在完全二叉樹中有幾個(gè)性質(zhì)：

設(shè)當(dāng)前元素在數(shù)組中以R[i]表示，那么，
(1) 它的左孩子結(jié)點(diǎn)是：R[2*i+1];
(2) 它的右孩子結(jié)點(diǎn)是：R[2*i+2];
(3) 它的父結(jié)點(diǎn)是：R[(i-1)/2];

(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

大根堆：每個(gè)結(jié)點(diǎn)的關(guān)鍵字都不小于其孩子結(jié)點(diǎn)的關(guān)鍵字。

小根堆：每個(gè)結(jié)點(diǎn)的關(guān)鍵字都不大于其孩子結(jié)點(diǎn)的關(guān)鍵字。

2、算法思想

（1）根據(jù)初始數(shù)組去構(gòu)造初始堆，默認(rèn)是大根堆（構(gòu)建一個(gè)完全二叉樹，保證所有的父結(jié)點(diǎn)都比它的孩子結(jié)點(diǎn)數(shù)值大）。

（2）每次交換第一個(gè)和最后一個(gè)元素，輸出最后一個(gè)元素（最大值），然后把剩下元素重新調(diào)整為大根堆。

上述算法是個(gè)循環(huán)操作，先構(gòu)建，然后交換輸出，最后調(diào)整余下的為大根堆，其實(shí)就是尋找最大值，其實(shí)只需要左右兩個(gè)結(jié)點(diǎn)，那個(gè)比較大，就獲取那個(gè)，所以調(diào)整堆排序也是比較簡單，就是比較左右結(jié)點(diǎn)，獲取最大值

第一步：構(gòu)建大根堆

第二步、輸出、調(diào)整

3、代碼

////堆排序 void SortAlgorithm::HeapSort(pSqlList pList) {//循環(huán)構(gòu)建堆for (int i = pList->length/2;i>0;i--){AdjustHeap(pList,i,pList->length-1);}PrintSqlList(pList);for (int i = pList->length-1;i>1;i--){//循環(huán)輸出根節(jié)點(diǎn)，同時(shí)再次調(diào)整為大根堆swap(pList,1,i); //根節(jié)點(diǎn)位于最前面，也就是1，這樣就將1最大值，放在數(shù)組后面了AdjustHeap(pList,1,i-1);PrintSqlList(pList);} } inline void SortAlgorithm::AdjustHeap(pSqlList pList,int start,int length) {int temp = pList->SqlArray[start]; //這是分支節(jié)點(diǎn)，然后比較它的分支節(jié)點(diǎn)，也就是2ifor (int i = 2*start;i<length;i = i*2){//獲取左右結(jié)點(diǎn)中比較大的值的坐標(biāo)if (i<length && pList->SqlArray[i] < pList->SqlArray[i+1]){i++;}//如果根節(jié)點(diǎn)本來就大，無序調(diào)整if (temp > pList->SqlArray[i]){break;}//交換值，將左右結(jié)點(diǎn)大值放在根節(jié)點(diǎn)pList->SqlArray[start] = pList->SqlArray[i];start = i;}//將開始需要比較的值，放在最后交換出的位置上pList->SqlArray[start] = temp;}

4、代碼分析

程序中一開始構(gòu)建，調(diào)整大根堆，最大值是length/2，因?yàn)閺耐耆鏄涞母拍钌戏治?#xff1a;

在上圖中大根堆的建立，就是調(diào)整前四個(gè)元素的位置，就是放再分支節(jié)點(diǎn)上還是葉子結(jié)點(diǎn)上，所以只要輸入4即可。

一開始大根堆，發(fā)現(xiàn)是90在最前面。

首先，將位于第一位（根節(jié)點(diǎn)樹最大），然后和最后一位交換，然后調(diào)整前8位（第九位已經(jīng)是最大了）。

然后，再講獲取到的80，和最后一位（第九位，第十已經(jīng)不需交換），然后調(diào)整前7位，當(dāng)然都是從1開始了。

最后經(jīng)過一次次循環(huán)調(diào)整，完成算法的排序。

其中關(guān)鍵的思想是獲取調(diào)整堆排序，比如一開始90和20交換后，20位于第一位置；此時(shí)20和左右結(jié)點(diǎn)中的較大值80交換，關(guān)鍵是后續(xù)繼續(xù)拿20和后面左右結(jié)點(diǎn)比較，直到break，也就是找到比它小的，跳出，然后賦值。

三、性能分析

1、簡單選擇排序

從簡單選擇排序的過程來看，它最大的特點(diǎn)就是交換移動(dòng)數(shù)據(jù)次數(shù)相當(dāng)少，這樣也就節(jié)約了相應(yīng)的時(shí)間。分析它的時(shí)間復(fù)雜度，無論最好最差的情況，其比較次數(shù)都是一樣多，第i趟排序需要進(jìn)行n-i次關(guān)鍵字的比較，此時(shí)需要n-1 +...+1 = n(n - 1)/2次。而對于交換次數(shù)而言，當(dāng)最好的時(shí)候，交換次數(shù)為0，最差的時(shí)候，也就初始降序時(shí)，交換次數(shù)為n-1次。總的時(shí)間復(fù)雜度依然為O(n²)。

??? 盡管簡單選擇排序與冒泡排序同為O(n²)，但簡單選擇排序的性能上還是要優(yōu)于冒泡排序的。

2、堆排序

堆排序是一種不穩(wěn)定的排序方法。

因?yàn)樵诙训恼{(diào)整過程中，關(guān)鍵字進(jìn)行比較和交換所走的是該結(jié)點(diǎn)到葉子結(jié)點(diǎn)的一條路徑。

在程序運(yùn)行時(shí)主要消耗在初始化構(gòu)建堆和重建堆的反復(fù)刷選上。在初始化構(gòu)建堆時(shí)，是從非終結(jié)點(diǎn)開始，其實(shí)比較兩次，本來時(shí)n/2，這樣最多對n/2進(jìn)行兩次比較工作，所以初始化構(gòu)建大根堆是O(n)。

在調(diào)整構(gòu)建堆時(shí)，第i次構(gòu)建樹logI（根據(jù)完全二叉樹性質(zhì)），需要遍歷N-1記錄,所以時(shí)間復(fù)雜度是O(nlogn)

轉(zhuǎn)載于:https://www.cnblogs.com/polly333/p/4816828.html

總結(jié)

以上是生活随笔為你收集整理的浅谈数据结构-选择排序(简单、堆排序）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。