数据结构中的各种排序---总结篇
轉(zhuǎn)載：http://blog.csdn.net/wzyhb123456789/article/details/5974790
一個月沒有寫文章，原因是一直在忙碌著，但是其實是有收獲的，下面就是我這前半個月最大的收獲：對于數(shù)據(jù)結(jié)構(gòu)中排序算法的總結(jié)，在我找工作的道路上幫助了我好多。如有錯誤，歡迎指正！
?
?
一、基本概念：
1、??排序：按照一定的關(guān)鍵字，將一個序列排列成想要得到的一個新的序列。
2、??內(nèi)部排序和外部排序：整個排序過程完全在內(nèi)存中進(jìn)行，叫做內(nèi)部排序。數(shù)據(jù)量較大需要借助外部存儲設(shè)備才能完成，叫做外部排序。
3、??主關(guān)鍵字和此關(guān)鍵字：
4、??排序的穩(wěn)定性：對于相同的元素來說，在排序之前和之后的書訊是一樣的，那么這種排序就是穩(wěn)定的排序，如果順序發(fā)生了變化，那么就是不穩(wěn)定排序。
二、插入類排序：
（一）???思想：在一個已經(jīng)排好序的序列中，將未被排進(jìn)的元素按照原先的規(guī)定插入到指定位置。
（二）???分類：
1、??直接插入排序：
①???思想：最基本的插入排序，將第i個插入到前i-1個中的適當(dāng)位置。
②???時間復(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 plaincopy2、??折半插入排序：
①???思想：因為是已經(jīng)確定了前部分是有序序列，所以在查找插入位置的時候可以用折半查找的方法進(jìn)行查找，提高效率。
②???時間復(fù)雜度：比較時的時間減為O(n㏒n)，但是移動元素的時間耗費未變，所以總是得時間復(fù)雜度還是O(n2)。
③???空間復(fù)雜度：S(n) = O(1)。
④???穩(wěn)定性：穩(wěn)定排序。
⑤???程序：
[cpp]?view plaincopy3、??希爾排序：
①???思想：又稱縮小增量排序法。把待排序序列分成若干較小的子序列，然后逐個使用直接插入排序法排序，最后再對一個較為有序的序列進(jìn)行一次排序，主要是為了減少移動的次數(shù)，提高效率。原理應(yīng)該就是從無序到漸漸有序，要比直接從無序到有序移動的次數(shù)會少一些。
②???時間復(fù)雜度：O(n的1.5次方)
③???空間復(fù)雜度：O(1)
④???穩(wěn)定性：不穩(wěn)定排序。{2,4,1,2}，2和1一組4和2一組，進(jìn)行希爾排序，第一個2和最后一個2會發(fā)生位置上的變化。
⑤???程序：
[cpp]?view plaincopy三、交換類排序：
（一）???思想：通過交換逆序元素進(jìn)行排序的方法。
（二）???分類：
1、??冒泡排序：
①???思想：反復(fù)掃描待排序序列，在掃描的過程中順次比較相鄰的兩個元素的大小，若逆序就交換位置。第一趟，從第一個數(shù)據(jù)開始，比較相鄰的兩個數(shù)據(jù)，（以升序為例）如果大就交換，得到一個最大數(shù)據(jù)在末尾；然后進(jìn)行第二趟，只掃描前n-1個元素，得到次大的放在倒數(shù)第二位。以此類推，最后得到升序序列。如果在掃描過程中，發(fā)現(xiàn)沒有交換，說明已經(jīng)排好序列，直接終止掃描。所以最多進(jìn)行n-1趟掃描。
②???時間復(fù)雜度：T(n) = O(n2)。
③???空間復(fù)雜度：S(n) = O(1)。
④???穩(wěn)定性：穩(wěn)定排序。
⑤???程序：
[cpp]?view plaincopy2、??快速排序：
①???思想：冒泡排序一次只能消除一個逆序，為了能一次消除多個逆序，采用快速排序。以一個關(guān)鍵字為軸，從左從右依次與其進(jìn)行對比，然后交換，第一趟結(jié)束后，可以把序列分為兩個子序列，然后再分段進(jìn)行快速排序，達(dá)到高效。
②???時間復(fù)雜度：平均T(n) = O(n㏒n)，最壞O(n2)。
③???空間復(fù)雜度：S(n) = O(㏒n)。
④???穩(wěn)定性：不穩(wěn)定排序。{3，?2，?2}
⑤???程序：
[cpp]?view plaincopy四、選擇類排序：
（一）???思想：每一趟在n – i + 1 ( i = 1,2,?…?, n - 1)個記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個記錄。
（二）???分類：
1、??簡單選擇排序：
①???思想：第一趟時，從第一個記錄開始，通過n – 1次關(guān)鍵字的比較，從n個記錄中選出關(guān)鍵字最小的記錄，并和第一個記錄進(jìn)行交換。第二趟從第二個記錄開始，選擇最小的和第二個記錄交換。以此類推，直至全部排序完畢。
②???時間復(fù)雜度：T(n) = O(n2)。
③???空間復(fù)雜度：S(n) = O(1)。
④???穩(wěn)定性：不穩(wěn)定排序，{3，?3，?2}。
⑤???程序：
[cpp]?view plaincopy2、??樹形選擇排序：
①???思想：為了減少比較次數(shù)，兩兩進(jìn)行比較，得出的較小的值再兩兩比較，直至得出最小的輸出，然后在原來位置上置為∞，再進(jìn)行比較。直至所有都輸出。
②???時間復(fù)雜度：T(n) = O(n㏒n)。
③???空間復(fù)雜度：較簡單選擇排序，增加了n-1個額外的存儲空間存放中間比較結(jié)果，就是樹形結(jié)構(gòu)的所有根節(jié)點。S(n) = O(n)。
④???穩(wěn)定性：穩(wěn)定排序。
⑤???程序：
3、??堆排序：
①???思想：把待排序記錄的關(guān)鍵字存放在數(shù)組r[1…n]中，將r看成是一刻完全二叉樹的順序表示，每個節(jié)點表示一個記錄，第一個記錄r[1]作為二叉樹的根，一下個記錄r[2…n]依次逐層從左到右順序排列，任意節(jié)點r[i]的左孩子是r[2i]，右孩子是r[2i+1]，雙親是r[i/2向下取整]。然后對這棵完全二叉樹進(jìn)行調(diào)整建堆。
②???時間復(fù)雜度：T(n) = O(n㏒n)。
③???空間復(fù)雜度：S(n) = O(1)。
④???穩(wěn)定性：不穩(wěn)定排序。{5，?5，?3}
⑤???程序：
(1)?????調(diào)整堆：
[cpp]?view plaincopy(2)?????建初堆：
[cpp]?view plaincopy(3)?????堆排序：
[cpp]?view plaincopy五、歸并排序：
（一）???思想：
（二）???分類：
1、??歸并排序：
①???思想：假設(shè)初始序列右n個記錄，首先將這n個記錄看成n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到n/2向上取整?個長度為2（n為奇數(shù)時，最后一個序列的長度為1）的有序子序列。在此基礎(chǔ)上，在對長度為2的有序子序列進(jìn)行兩兩歸并，得到若干個長度為4的有序子序列。如此重復(fù)，直至得到一個長度為n的有序序列為止。
②???時間復(fù)雜度：T(n) = O(n㏒n)。
③???空間復(fù)雜度：S(n) = O(n)。
④???穩(wěn)定性：穩(wěn)定排序。
⑤???程序：
[cpp]?view plaincopy六、分配類排序：
（一）???思想：分配類排序是利用分配和收集兩種基本操作。
（二）???分類：
1、??多關(guān)鍵字排序：
2、??鏈?zhǔn)交鶖?shù)排序：
①???思想：先分配，再收集，就是先按照一個次關(guān)鍵字收集一下，然后進(jìn)行收集（第一個排序），然后再換一個關(guān)鍵字把新序列分配一下，然后再收集起來，又完成一次排序，這樣所有關(guān)鍵字分配收集完后，就完成了排序。
②???時間復(fù)雜度：T(n) = O( d ( n + rd ) )。
③???空間復(fù)雜度：S(n) = O(rd)。
④???穩(wěn)定性：穩(wěn)定排序。
⑤???程序：
七、總結(jié)：
（1）簡單排序法一般只用于n較小的情況（例如n<30）。當(dāng)序列的記錄“基本有序”時，直接插入排序是最佳的排序方法。如果記錄中的數(shù)據(jù)較多，則應(yīng)采用移動次數(shù)較少的簡單選擇排序法。
（2）快速排序、堆排序和歸并排序的平均時間復(fù)雜度均為O(n㏒n)，但實驗結(jié)果表明，就平均時間性能而言，快速排序是所有排序方法中最好的。遺憾的是，快速排序在最壞情況下的時間性能為O(n2)。堆排序和歸并排序的最壞時間復(fù)雜度仍為O(n㏒n)，當(dāng)n較大時，歸并排序的時間性能優(yōu)于堆排序，但它所需的輔助空間最多。
（3）可以將簡單排序法與性能較好的排序方法結(jié)合使用。例如，在快速排序中，當(dāng)劃分子區(qū)間的長度小于某值時，可以轉(zhuǎn)而調(diào)用直接插入排序法；或者先將待排序序列劃分成若干子序列，分別進(jìn)行直接插入排序，然后再利用歸并排序法，將有序子序列合并成一個完整的有序序列。
（4）基數(shù)排序的時間復(fù)雜度可以寫成O(d·n)。因此，它最適合于n值很大而關(guān)鍵字的位數(shù)d較小的序列。當(dāng)d遠(yuǎn)小于n時，其時間復(fù)雜度接近O(n)。
（5）從排序的穩(wěn)定性上來看，在所有簡單排序法中，簡單選擇排序是不穩(wěn)定的，其他各種簡單排序法都是穩(wěn)定的。然而，在那些時間性能較好的排序方法中，希爾排序、快速排序、堆排序都是不穩(wěn)定的，只有歸并排序、基數(shù)排序是穩(wěn)定的。
常考的排序：選擇排序、折半插入、冒泡
總結(jié)
以上是生活随笔為你收集整理的数据结构中的各种排序---总结篇的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 字符串处理编程题
- 下一篇： 把字符串中的数字找出来并按照升序排序