轉(zhuǎn)載：http://blog.csdn.net/wzyhb123456789/article/details/5974790

一個(gè)月沒有寫文章，原因是一直在忙碌著，但是其實(shí)是有收獲的，下面就是我這前半個(gè)月最大的收獲：對(duì)于數(shù)據(jù)結(jié)構(gòu)中排序算法的總結(jié)，在我找工作的道路上幫助了我好多。如有錯(cuò)誤，歡迎指正！

?

?

一、基本概念：

1、??排序：按照一定的關(guān)鍵字，將一個(gè)序列排列成想要得到的一個(gè)新的序列。

2、??內(nèi)部排序和外部排序：整個(gè)排序過程完全在內(nèi)存中進(jìn)行，叫做內(nèi)部排序。數(shù)據(jù)量較大需要借助外部存儲(chǔ)設(shè)備才能完成，叫做外部排序。

3、??主關(guān)鍵字和此關(guān)鍵字：

4、??排序的穩(wěn)定性：對(duì)于相同的元素來說，在排序之前和之后的書訊是一樣的，那么這種排序就是穩(wěn)定的排序，如果順序發(fā)生了變化，那么就是不穩(wěn)定排序。

二、插入類排序：

（一）???思想：在一個(gè)已經(jīng)排好序的序列中，將未被排進(jìn)的元素按照原先的規(guī)定插入到指定位置。

（二）???分類：

1、??直接插入排序：

①???思想：最基本的插入排序，將第i個(gè)插入到前i-1個(gè)中的適當(dāng)位置。

②???時(shí)間復(fù)雜度：T(n) = O(n2)。

③???空間復(fù)雜度：S(n) = O(1)。

④???穩(wěn)定性：穩(wěn)定排序。循環(huán)條件while(r[0].key < r[j].key)保證的。

⑤???程序：

[cpp]?view plaincopy

void?InsSort(RecordType?r[],?int?length)??

{??

????for(i?=?2;?I?<=?length;?i++)??

????{??

????????r[0]?=?r[i];??

????????j?=?i?–?1;??

????????while(r[0].key?<?r[j].key)??

????????{??

????????????r[j?+?1]?=?r[j];?j?=?j?–?1;??

????????}??

????????r[j+1]?=?r[0];??

????}??

}??

2、??折半插入排序：

①???思想：因?yàn)槭且呀?jīng)確定了前部分是有序序列，所以在查找插入位置的時(shí)候可以用折半查找的方法進(jìn)行查找，提高效率。

②???時(shí)間復(fù)雜度：比較時(shí)的時(shí)間減為O(n㏒n)，但是移動(dòng)元素的時(shí)間耗費(fèi)未變，所以總是得時(shí)間復(fù)雜度還是O(n2)。

③???空間復(fù)雜度：S(n) = O(1)。

④???穩(wěn)定性：穩(wěn)定排序。

⑤???程序：

[cpp]?view plaincopy

void?BinSort(RecordType?r[],?int?length)??

{??

????for(i?=?2;?i?<=?length;?i++)??

????{??

????????x?=?r[i];??

????????low?=?1;?high?=?i?–?1;??

????????while(low?<=?high)??

????????{??

????????????mid?=?(low?+?high)?/?2;??

????????????if(x.key?<?r[mid].key)??

????????????????high?=?mid?–?1;??

????????????else??

????????????????low?=?mid?–?1;??

????????}??

????????for(j?=?i?–?1;?j?>=?low;?--j)??

????????????r[j?+?1]?=?r[j];??

????????r[low]?=?x;??

????}??

}??

3、??希爾排序：

①???思想：又稱縮小增量排序法。把待排序序列分成若干較小的子序列，然后逐個(gè)使用直接插入排序法排序，最后再對(duì)一個(gè)較為有序的序列進(jìn)行一次排序，主要是為了減少移動(dòng)的次數(shù)，提高效率。原理應(yīng)該就是從無序到漸漸有序，要比直接從無序到有序移動(dòng)的次數(shù)會(huì)少一些。

②???時(shí)間復(fù)雜度：O(n的1.5次方)

③???空間復(fù)雜度：O(1)

④???穩(wěn)定性：不穩(wěn)定排序。{2,4,1,2}，2和1一組4和2一組，進(jìn)行希爾排序，第一個(gè)2和最后一個(gè)2會(huì)發(fā)生位置上的變化。

⑤???程序：

[cpp]?view plaincopy

void?ShellInsert(RecordType?r[],?int?length,?int?delta)??

{??

????for(i?=?1?+?delta;?i?<=?length;?i++)/*1+delta為第一個(gè)子序列的第二個(gè)元素的下表*/??

????if(r[i].key?<?r[1?-?delta].key)??

????{??

????????r[0]?=?r[i];??

????????for(j?=?i?–?delta;?j?>?0?&&?r[0].key?<?r[j].key;?j?-=delta)??

????????????r[j?+?delta]?=?r[j];??

????????r[j?+?delta]?=?r[0];??

????}??

}??

void?ShellSort(RecordType?r[],?int?length,?int?delta[],?int?n)??

{??

????for(i?=?0;?i?<=?n?–?1;?++i)??

????????ShellInsert(r,?length,?delta[i]);??

}??

三、交換類排序：

（一）???思想：通過交換逆序元素進(jìn)行排序的方法。

（二）???分類：

1、??冒泡排序：

①???思想：反復(fù)掃描待排序序列，在掃描的過程中順次比較相鄰的兩個(gè)元素的大小，若逆序就交換位置。第一趟，從第一個(gè)數(shù)據(jù)開始，比較相鄰的兩個(gè)數(shù)據(jù)，（以升序?yàn)槔?#xff09;如果大就交換，得到一個(gè)最大數(shù)據(jù)在末尾；然后進(jìn)行第二趟，只掃描前n-1個(gè)元素，得到次大的放在倒數(shù)第二位。以此類推，最后得到升序序列。如果在掃描過程中，發(fā)現(xiàn)沒有交換，說明已經(jīng)排好序列，直接終止掃描。所以最多進(jìn)行n-1趟掃描。

②???時(shí)間復(fù)雜度：T(n) = O(n2)。

③???空間復(fù)雜度：S(n) = O(1)。

④???穩(wěn)定性：穩(wěn)定排序。

⑤???程序：

[cpp]?view plaincopy

void?BubbleSort(RecordType?r[],?int?length)??

{??

????n?=?length;??

????change?=?TRUE;??

????for(i?=?1;?i?<=?n?–?1?&&?change;?i++)??

????{??

????????change?=?FALSE;??

????????for(j?=?1;?j?<=?n?–?I;?++j)??

????????????if(r[j].key?>?r[j?+?1].key)??

????????????{??

????????????????x?=?r[j];??

????????????????r[j]?=?r[j?+?1];??

????????????????r[j?+?1]?=?x;??

????????????????change?=?TRUE;??

?????????????}??

????}??

}??

2、??快速排序：

①???思想：冒泡排序一次只能消除一個(gè)逆序，為了能一次消除多個(gè)逆序，采用快速排序。以一個(gè)關(guān)鍵字為軸，從左從右依次與其進(jìn)行對(duì)比，然后交換，第一趟結(jié)束后，可以把序列分為兩個(gè)子序列，然后再分段進(jìn)行快速排序，達(dá)到高效。

②???時(shí)間復(fù)雜度：平均T(n) = O(n㏒n)，最壞O(n2)。

③???空間復(fù)雜度：S(n) = O(㏒n)。

④???穩(wěn)定性：不穩(wěn)定排序。{3，?2，?2}

⑤???程序：

[cpp]?view plaincopy

void?QKSort(RecordType?r[],?int?low,?int?high)??

{??

????int?pos;??

????if(low?<?high)??

????{??

????????pos?=?QKPass(r,?low,?high);??

????????QKSort(r,?low,?pos?-?1);??

????????QKSort(r,?pos?+?1,?high);??

????}??

}??

int?QKPass(RecordType?r[],?int?left,?int?right)??

{??

????RecordType?x;??

????int?low,?high;??

????x?=?r[left];??

????low?=?left;??

????high?=?right;??

????while(low?<?high)??

????{??

????????while(low?<?high?&&?r[high].key?>=?x.key)??

????????????high--;??

????????if(low?<?high)??

????????{??

????????????r[low]?=?r[high];??

????????????low++;??

????????}??

????????while(low?<?high?&&?r[low].key?<?x.key)??

????????????low++;??

????????if(low?<?high)??

????????{??

????????????r[high]?=?r[low];??

????????????high--;??

????????}??

????}??

????r[low]?=?x;??

????return?low;??

}??

四、選擇類排序：

（一）???思想：每一趟在n – i + 1 ( i = 1,2,?…?, n - 1)個(gè)記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個(gè)記錄。

（二）???分類：

1、??簡(jiǎn)單選擇排序：

①???思想：第一趟時(shí)，從第一個(gè)記錄開始，通過n – 1次關(guān)鍵字的比較，從n個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第一個(gè)記錄進(jìn)行交換。第二趟從第二個(gè)記錄開始，選擇最小的和第二個(gè)記錄交換。以此類推，直至全部排序完畢。

②???時(shí)間復(fù)雜度：T(n) = O(n2)。

③???空間復(fù)雜度：S(n) = O(1)。

④???穩(wěn)定性：不穩(wěn)定排序，{3，?3，?2}。

⑤???程序：

[cpp]?view plaincopy

void?SelectSort(RecordType?r[],?int?length)??

{??

????n?=?length;??

????for(i?=?1;?i?<=?n?-?1;?i++)??

????{??

????????k?=?i;??

????????for(j?=?i?+?1;?j?<=?n;?i++)??

????????if(r[j].key?<?r[k],key)??

????????????k?=?j;??

????????????if(k?!=?i)??

????????????{??

????????????????x?=?r[i];??

????????????????r[i]?=?r[k];??

????????????????r[k]?=?x;??

????????????}??

????}??

}??

2、??樹形選擇排序：

①???思想：為了減少比較次數(shù)，兩兩進(jìn)行比較，得出的較小的值再兩兩比較，直至得出最小的輸出，然后在原來位置上置為∞，再進(jìn)行比較。直至所有都輸出。

②???時(shí)間復(fù)雜度：T(n) = O(n㏒n)。

③???空間復(fù)雜度：較簡(jiǎn)單選擇排序，增加了n-1個(gè)額外的存儲(chǔ)空間存放中間比較結(jié)果，就是樹形結(jié)構(gòu)的所有根節(jié)點(diǎn)。S(n) = O(n)。

④???穩(wěn)定性：穩(wěn)定排序。

⑤???程序：

3、??堆排序：

①???思想：把待排序記錄的關(guān)鍵字存放在數(shù)組r[1…n]中，將r看成是一刻完全二叉樹的順序表示，每個(gè)節(jié)點(diǎn)表示一個(gè)記錄，第一個(gè)記錄r[1]作為二叉樹的根，一下個(gè)記錄r[2…n]依次逐層從左到右順序排列，任意節(jié)點(diǎn)r[i]的左孩子是r[2i]，右孩子是r[2i+1]，雙親是r[i/2向下取整]。然后對(duì)這棵完全二叉樹進(jìn)行調(diào)整建堆。

②???時(shí)間復(fù)雜度：T(n) = O(n㏒n)。

③???空間復(fù)雜度：S(n) = O(1)。

④???穩(wěn)定性：不穩(wěn)定排序。{5，?5，?3}

⑤???程序：

(1)?????調(diào)整堆：

[cpp]?view plaincopy

void?sift(RecordType?r[],?int?k,?int?m)??

{??

????/*假設(shè)r[k...m]是以r[k]為根的完全二叉樹，而且分別以r[2k]和r[2k+1]為根的左右子樹為大根堆，調(diào)整r[k]，使整個(gè)序列r[k...m]滿足堆的性質(zhì)*/??

????t?=?r[k];/*暫存“根”記錄r[k]*/??

????x?=?r[k].key;??

????i?=?k;??

????j?=?2?*?i;??

????finished?=?FALSE;??

????while(j?<=?m?&&?!finished)??

????{??

????????if(j?<?m?&&?r[j].key?<?r[j?+?1].key)??

????????????j?=?j?+?1;/*若存在右子樹，且右子樹根的關(guān)鍵字大，則沿右分支“篩選”*/??

????????if(x?>=?r[j].key)??

????????????finished?=?TRUE;/*篩選完畢*/??

????????else??

????????{??

????????????r[i]?=?r[j];??

????????????i?=?j;??

????????????j?=?2?*?i;??

????????}/*繼續(xù)篩選*/??

????}??

????r[i]?=?t;/*將r[k]填入到恰當(dāng)?shù)奈恢?/??

}??

(2)?????建初堆：

[cpp]?view plaincopy

void?crt_heap(recordType?r[],?int?length)??

{??

????n?=?length;??

????for(i?=?n?/?2;?i?>=?1;?--i)/*自第n/2向下取整?個(gè)記錄開始進(jìn)行篩選建堆*/??

????????sift(r,?i,?n);??

}??

(3)?????堆排序：

[cpp]?view plaincopy

void?HeapSort(RecordType?r[],?int?length)??

{??

????crt_heap(r,?length);??

????n?=?length;??

????for(i?=?n;?i?>=?2;?--i)??

????{??

????????b?=?r[1];/*將堆頂記錄和堆中的最后一個(gè)記錄互換*/??

????????r[1]?=?r[i];??

????????r[i]?=?b;??

????????sift(r,?1,?i?-?1);/*進(jìn)行調(diào)整，使r[1…i-1]變成堆*/??

????}??

}??

五、歸并排序：

（一）???思想：

（二）???分類：

1、??歸并排序：

①???思想：假設(shè)初始序列右n個(gè)記錄，首先將這n個(gè)記錄看成n個(gè)有序的子序列，每個(gè)子序列的長(zhǎng)度為1，然后兩兩歸并，得到n/2向上取整?個(gè)長(zhǎng)度為2（n為奇數(shù)時(shí)，最后一個(gè)序列的長(zhǎng)度為1）的有序子序列。在此基礎(chǔ)上，在對(duì)長(zhǎng)度為2的有序子序列進(jìn)行兩兩歸并，得到若干個(gè)長(zhǎng)度為4的有序子序列。如此重復(fù)，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。

②???時(shí)間復(fù)雜度：T(n) = O(n㏒n)。

③???空間復(fù)雜度：S(n) = O(n)。

④???穩(wěn)定性：穩(wěn)定排序。

⑤???程序：

[cpp]?view plaincopy

void?Merge(RecordType?r1[],?int?low,?int?mid,?int?high,?RecordType?r2[])??

{??

????/*已知r1[low...mid]和r1[mid?+?1...high]分別按關(guān)鍵字有序排列，將它們合并成一個(gè)有序序列，存放在r2[low...high]*/??

????i?=?low;??

????j?=?mid?+?1;??

????k?=?low;??

????while((i?<=?mid)?&&?(j?<=?high))??

????{??

????????if(r1[i].key?<=?r1[j].key)??

????????{??

????????????r2[k]?=?r1[i];??

????????????++i;??

????????}??

????????else??

????????{??

????????????r2[k]?=?r1[j];??

????????????++j;??

????????}??

????????++k;??

????}??

????while(i?<=?mid)??

????{??

????????r2[k]?=?r1[i];??

????????k++;??

????????i++;??

????}??

????while(j?<=?high)??

????{??

????????r2[k]?=?r1[j];??

????????k++;??

????????j++;??

????}??

}??

void?MSort(RecordType?r1[],?int?low,?int?high,?RecordType?r3[])??

{??

????/*r1[low...high]經(jīng)過排序后放在r3[low...high]中，r2[low...high]為輔助空間*/??

????RecordType?r2[N];??

????if(low?==?high)??

????r3[low]?=?r1[low];??

????else??

????{??

????????mid?=?(low?+?high)?/?2;??

????????MSort(r1,?low,?mid,?r2);??

????????MSort(r1,?mid?+?1,?high,?r2);??

????????Merge(r2,?low,?mid,?high,?r3);??

????}??

}??

void?MergeSort(RecordType?r[],?int?n)??

{??

????/*對(duì)記錄數(shù)組r[1...n]做歸并排序*/??

????MSort(r,?1,?n,?r);??

}??

六、分配類排序：

（一）???思想：分配類排序是利用分配和收集兩種基本操作。

（二）???分類：

1、??多關(guān)鍵字排序：

2、??鏈?zhǔn)交鶖?shù)排序：

①???思想：先分配，再收集，就是先按照一個(gè)次關(guān)鍵字收集一下，然后進(jìn)行收集（第一個(gè)排序），然后再換一個(gè)關(guān)鍵字把新序列分配一下，然后再收集起來，又完成一次排序，這樣所有關(guān)鍵字分配收集完后，就完成了排序。

②???時(shí)間復(fù)雜度：T(n) = O( d ( n + rd ) )。

③???空間復(fù)雜度：S(n) = O(rd)。

④???穩(wěn)定性：穩(wěn)定排序。

⑤???程序：

七、總結(jié)：

（1）簡(jiǎn)單排序法一般只用于n較小的情況（例如n<30）。當(dāng)序列的記錄“基本有序”時(shí)，直接插入排序是最佳的排序方法。如果記錄中的數(shù)據(jù)較多，則應(yīng)采用移動(dòng)次數(shù)較少的簡(jiǎn)單選擇排序法。

（2）快速排序、堆排序和歸并排序的平均時(shí)間復(fù)雜度均為O(n㏒n)，但實(shí)驗(yàn)結(jié)果表明，就平均時(shí)間性能而言，快速排序是所有排序方法中最好的。遺憾的是，快速排序在最壞情況下的時(shí)間性能為O(n2)。堆排序和歸并排序的最壞時(shí)間復(fù)雜度仍為O(n㏒n)，當(dāng)n較大時(shí)，歸并排序的時(shí)間性能優(yōu)于堆排序，但它所需的輔助空間最多。

（3）可以將簡(jiǎn)單排序法與性能較好的排序方法結(jié)合使用。例如，在快速排序中，當(dāng)劃分子區(qū)間的長(zhǎng)度小于某值時(shí)，可以轉(zhuǎn)而調(diào)用直接插入排序法；或者先將待排序序列劃分成若干子序列，分別進(jìn)行直接插入排序，然后再利用歸并排序法，將有序子序列合并成一個(gè)完整的有序序列。

（4）基數(shù)排序的時(shí)間復(fù)雜度可以寫成O(d·n)。因此，它最適合于n值很大而關(guān)鍵字的位數(shù)d較小的序列。當(dāng)d遠(yuǎn)小于n時(shí)，其時(shí)間復(fù)雜度接近O(n)。

（5）從排序的穩(wěn)定性上來看，在所有簡(jiǎn)單排序法中，簡(jiǎn)單選擇排序是不穩(wěn)定的，其他各種簡(jiǎn)單排序法都是穩(wěn)定的。然而，在那些時(shí)間性能較好的排序方法中，希爾排序、快速排序、堆排序都是不穩(wěn)定的，只有歸并排序、基數(shù)排序是穩(wěn)定的。

常考的排序：選擇排序、折半插入、冒泡

總結(jié)

以上是生活随笔為你收集整理的数据结构中的各种排序---总结篇的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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