分享種常見的排序算法

1、1. 冒泡排序已知一組無序數(shù)據(jù)a1、a2、an，需將其按升序排列。首先比較a1與a2的值，若a1大于a2則交換兩者的值，否則不變。再比較 a2與a3的值，若a2大于a3則交換兩者的值，否則不變。再比 較a3與a4，以此類推，最后比較 an-1與an的值。這樣處理一輪后，an的值一定是這組數(shù)據(jù)中最大 的。再對(duì) a1an-1 以相同方法處理一輪，則 an-1 的值一定是 a1an-1 中最大的。再對(duì) a1an-2 以 相同方法處理一輪，以此類推。共處理 n-1輪后a1、a2、an就以升序排列了。優(yōu)點(diǎn)：穩(wěn)定，比較次數(shù)已知；缺點(diǎn)：慢，每次只能移動(dòng)相鄰兩個(gè)數(shù)據(jù)，移動(dòng)數(shù)據(jù)的次數(shù)多。初始關(guān)鍵字 49 386

2、5 97 76 13 27 49第一趟排序后38 4965 76 13 27 49 97第二趟排序后38 4965 13 27 49 76 97第三趟排序后38 4913 27 49 65 76 97第四趟排序后38 1327 49 49 65 76 97第五趟排序后38 1327 49 49 65 76 97第六趟排序后13 2738 49 49 65 76 97第七趟排序后13 2738 49 49 65 76 97最后排序結(jié)果13 2738 49 49 76 76 97#include <iostream> using namespace std; void main()in

3、t i,j,k;int a8=49,38,65,97,76,13,27,49;for(i=7;i>=0;i-)for(j=0;j<i;j+)if(aj>aj+1)k=aj;aj=aj+1;aj+1=k;for(i=0;i<8;i+)cout<<a<<endl;2. 選擇排序 初始狀態(tài)：無序區(qū)為R仁n，有序區(qū)為空。 第 1 趟排序在無序區(qū)R1.n中選出關(guān)鍵字最小的記錄Rk，將它與無序區(qū)的第1個(gè)記錄R1交換，使R1.1和R2.n 分別變?yōu)橛涗泜€(gè)數(shù)增加 1 個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少 1 個(gè)的新無序區(qū)。 第 i 趟排序第i趟排序開始時(shí)，當(dāng)前有序區(qū)和無序

4、區(qū)分別為R1.i-1和Ri.n(1 wi-的n該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄 Rk，將它與無序區(qū)的第1個(gè)記錄R交換，使R1.i和Ri+1.n分別變?yōu)橛涗泜€(gè)數(shù)增加1 個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少 1 個(gè)的新無序區(qū) .這樣， n 個(gè)記錄的文件的直接選擇排序可經(jīng)過 n-1 趟直接 選擇排序得到有序結(jié)果。優(yōu)點(diǎn)：穩(wěn)定，比較次數(shù)與冒泡排序一樣；缺點(diǎn)：相對(duì)之下還是慢。初始關(guān)鍵字 49 3865 97 76 13 27 49第一趟排序后13 38 65 97 76 49 27 49第二趟排序后13 27 65 97 76 49 38 49第三趟排序后13 2738 97 76 49 65 49第四趟

5、排序后13 2738 49 49 97 65 76第五趟排序后13 2738 49 49 97 97 76第六趟排序后13 2738 49 49 76 76 97第七趟排序后13 2738 49 49 76 76 97最后排序結(jié)果13 2738 49 49 76 76 97#include <iostream> using namespace std;void main()int i,j,k,t;int R8=49,38,65,97,76,13,27,49;for(i=0;i<7;i+)k=i;for(j=i+1;j<8;j+)if(Rj<Rk)k=j;if(k!

6、=i)t=Rj;Rj=Rk;Rk=t;for(i=0;i<8;i+)cout<<R<<endl;3. 插入排序已知一組，一組無序數(shù)據(jù) b1、b2、bm，需將其變成一個(gè)升序數(shù)列。先創(chuàng)建一個(gè)變量a。首先將不b1與b2,如果b1大于b2則交換位置，否則不變；再比較 b2與b3，如果b3小于b2，則將b3 賦值給a，再將a與b1比較，如果a小于b1；則將b2，b1依次后移；在將a放在b1處以此類推， 直到排序結(jié)束。初始關(guān)鍵字 49 3865 97 76 13 27 59a b1 b2b3 b4 b5b6 b7 b81 49 49 > 38 65 97 76 13 2

7、7 59 38 49 4938 38 492 38 38 49 < 65 97 76 13 27 593 38 38 49 65 <97 76 13 27 594 38 38 49 65 97> 76 13 27 5976 38 4965 97 9776 38 49 65 76 97以此類推void insertSort(Type* arr,long len)long i=0,j=0;for(i=1;i<len;i+)j=i;tmpData=arrj;/tmpData 用來儲(chǔ)存數(shù)據(jù)while(tmpData<arrj-1&&j>0)arrj=

8、arrj-1;j-;arrj=tmpData;4. 縮小增量排序 (希爾排序 )由希爾在 1959 年提出，又稱希爾排序。已知一組無序數(shù)據(jù)a1、a2、an，需將其按升序排列。發(fā)現(xiàn)當(dāng)n不大時(shí)，插入排序的效果很好。首先取一增量d(d<n)，將a1、a1+d、a1+2d列為第一組，a2、a2+d、a2+2d列為第二組ad、a2d、a3d列為最后一組以次類推，在各組內(nèi)用插入排序，然后取d'<d，重復(fù)上述操作，直到d=1。增量d(1,3, 7,15, 31,-2是使用最廣泛的增量序列之一.優(yōu)點(diǎn)：快，數(shù)據(jù)移動(dòng)少；缺點(diǎn)：不穩(wěn)定， d 的取值是多少，應(yīng)取多少個(gè)不同的值，都無法確切知道，只能

9、憑經(jīng)驗(yàn)來取。初始：d = 549 38 65 9776 13 27 49 55 44一趟結(jié)果1327 49 5544 49 38 65 97 76d=3|二趟結(jié)果13 44 49 3827 49 55 65 97 76d=1三趟結(jié)果1327 38 4449 49 55 65 76 97#include <iostream> using namespace std;#define MAX 16 void shell_sort(int *x, int n)inth, j, k, t;for(h=n/2;h>0; h=h/2) /* 控制增量 */for(j=h; j<n;

10、j+) /* 這個(gè)實(shí)際上就是上面的直接插入排序 */t= *(x+j);for(k=j-h; (k>=0 && t<*(x+k); k-=h)*(x+k+h)= *(x+k);*(x+k+h)= t;void main()int*p, i, aMAX;p= a;cout<<"InputMAX number for sorting :"<<endl;for(i=0; i<MAX; i+)cin>>*p+;p=a;shell_sort(p,MAX);for(p=a, i=0; i<MAX; i+)cou

11、t<<*p+<<endl;cout<<endl;5. 快速排序快速排序是冒泡排序的改進(jìn)版，是目前已知的最快的排序方法。已知一組無序數(shù)據(jù) a1、a2、an，需將其按升序排列。首先任取數(shù)據(jù)ax作為基準(zhǔn)。比較ax與其它數(shù)據(jù)并排序，使 ax 排在數(shù)據(jù)的第 k 位，并且使 a1ak-1 中的每一個(gè)數(shù)據(jù) <ax ， ak+1an 中的每一 個(gè)數(shù)據(jù) >ax ，然后采用分治的策略分別對(duì) a1ak-1 和 ak+1an兩組數(shù)據(jù)進(jìn)行快速排序。優(yōu)點(diǎn)：極快，數(shù)據(jù)移動(dòng)少；缺點(diǎn)：不穩(wěn)定。分段插入排序void QuickSort(int *pData, int left, i

12、ntright)int i, j;int middle,iTemp;i = left;j = right;middle =pData(left + right) / 2; / 求中間值dowhile(pData < middle) && (i < right) /從左掃描大于中值的數(shù)i+;while(pDataj > middle) && (j > left) / 從右掃描小于中值的數(shù) j-;if (i <=j) / 找到了一對(duì)值/交換iTemp =pData;pData =pDataj;pDataj =iTemp;i+;j-; w

13、hile (i<= j) ; / 如果兩邊掃描的下標(biāo)交錯(cuò)，就停止(完成一次) /當(dāng)左邊部分有值 (left<j) ，遞歸左半邊if(left<j)QuickSort(pData,left,j);/當(dāng)右邊部分有值 (right>i) ，遞歸右半邊if(right>i)QuickSort(pData,i,right);6. 歸并排序算法合并排序( MERGESORT )是又一類不同的排序方法，合并的含義就是將兩個(gè)或兩個(gè)以上的有序數(shù)據(jù)序列 合并成一個(gè)新的有序數(shù)據(jù)序列，因此它又叫歸并算法。它的基本思想就是假設(shè)數(shù)組 A 有 N 個(gè)元素，那么可 以看成數(shù)組 A 是又 N 個(gè)有

14、序的子序列組成， 每個(gè)子序列的長度為 1 ，然后再兩兩合并， 得到了一個(gè) N/2 個(gè) 長度為 2 或 1 的有序子序列，再兩兩合并，如此重復(fù)，值得得到一個(gè)長度為 N 的有序數(shù)據(jù)序列為止，這種 排序方法稱為 2 路合并排序。例如數(shù)組 A 有 7 個(gè)數(shù)據(jù)，分別是： 493865 97 7613圖7 所示：初始值 49 38659776 1327第一次合并之后38496597137627第二次合并之后38496597132776第三次合并之后1327384965769727，那么采用歸并排序算法的操作過程如合并算法的核心操作就是將一維數(shù)組中前后相鄰的兩個(gè)兩個(gè)有序序列合并成一個(gè)有序序列。合并算法也可

15、以采用遞歸算法來實(shí)現(xiàn)， 形式上較為簡單 ,但實(shí)用性很差。 合并算法的合并次數(shù)是一個(gè)非常重要的量 , 根據(jù)計(jì) 算當(dāng)數(shù)組中有 3 到 4 個(gè)元素時(shí) ,合并次數(shù)是 2 次 ,當(dāng)有 5 到 8 個(gè)元素時(shí) ,合并次數(shù)是 3 次 ,當(dāng)有 9 到 16 個(gè)元素 時(shí),合并次數(shù)是 4 次，按照這一規(guī)律 ,當(dāng)有 N 個(gè)子序列時(shí)可以推斷出合并的次數(shù)是 X(2 >=N, 符合此條件的最 小那個(gè) X) 。其時(shí)間復(fù)雜度為： O(nlogn). 所需輔助存儲(chǔ)空間為： O(n)歸并排序：#include <stdio.h> void merge(int a,int p,int q,int r) int n1

16、=q-p+1,n2=r-q,i,j,k;int l1002,R1002;for (i=1;i<=n1;i+)l=ap+i-1;for (j=1;j<=n2;j+)Rj=aq+j;Rn2+1=ln1+1=999999;i=j=1;for (k=p;k<=r;k+)if (l<=Rj)ak=l;i+;elseak=Rj;j+;void mergesort(int a,int p,int r)int q;if (p<r)q=(p+r)/2;mergesort(a,p,q);mergesort(a,q+1,r);merge(a,p,q,r);int main()int a

17、1001,t,n,i;scanf("%d",&t);while (t-)scanf("%d",&n);for(i=1;i<=n;i+)scanf("%d",&a);mergesort(a,1,n);for (i=1;i<=n;i+)printf("%d",a);if (i!=n)printf(" ");printf（"n"）;return 0;7. 堆排序根結(jié)點(diǎn)（亦稱為堆頂 ）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為小根堆。根結(jié)點(diǎn) （亦

18、稱為堆頂 ）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大根堆。n個(gè)關(guān)鍵字序列KI, K2 ,，Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)（簡稱為堆性質(zhì)）： ki < K2且 ki < K2i+1 或（2）Ki > K且 ki > K2i+1（1 <） <堆排序利用了大根堆 （或小根堆 ）堆頂記錄的關(guān)鍵字最大（或最小 ）這一特征，使得在當(dāng)前無序區(qū)中選取最大（或最小 ）關(guān)鍵字的記錄變得簡單。（1 ）用大根堆排序的基本思想 先將初始文件 R1.n 建成一個(gè)大根堆，此堆為初始的無序區(qū) 再將關(guān)鍵字最大的記錄 R1（即堆頂）和無序區(qū)的最后一個(gè)記錄Rn交換，由此得到新的無序區(qū)

19、R1.n-1和有序區(qū) Rn，且滿足 R1.n- 1.keys wRn.key 由于交換后新的根 R1可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無序區(qū)R1.n-1調(diào)整為堆。然后再次將R1.n-1中關(guān)鍵字最大的記錄 R1和該區(qū)間的最后一個(gè)記錄Rn-1交換，由此得到新的無序區(qū) R1.n-2和有序區(qū)Rn-1.n，且仍滿足關(guān)系 R1.n- 2.keys < R-n.n.keys，同樣要將 R1.n-2調(diào)整為堆。直到無序區(qū)只有一個(gè)元素為止。2 )大根堆排序算法的基本操作： 初始化操作：將 R1.n 構(gòu)造為初始堆； 每一趟排序的基本操作： 將當(dāng)前無序區(qū)的堆頂記錄 R1 和該區(qū)間的最后一個(gè)記錄交換， 然后將新的無序 區(qū)

20、調(diào)整為堆 ( 亦稱重建堆 ) 。注意：只需做 n-1 趟排序，選出較大的 n-1 個(gè)關(guān)鍵字即可以使得文件遞增有序。用小根堆排序與利用大根堆類似，只不過其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任 何時(shí)刻，堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴(kuò)大至整個(gè)向量為 止。3.具體算法template<class T>heapsort(T r,int n) /n 為文件的實(shí)際記錄數(shù)， r0 沒有使用int i,m;node x;for(i=/2;i>=1;i-)heappass(r,i,n);/ 初建堆/ 以下 for 語句為輸出堆頂元素、調(diào)整堆

21、操作for(m=n-1;m>=1;m-)/ 邏輯堆尾下標(biāo) m 不斷變小 cout<<r1.key<<"x=r1;r1=rm+1;rm+1=x; / 堆頂與堆尾元素對(duì)換heappass(r,1,m);/ 恢復(fù)堆cout<<r1.key<<endl;/heapsort4. 直接選擇排序中，為了從 R1.n 中選出關(guān)鍵字最小的記錄，必須進(jìn)行n-1 次比較，然后在 R2.n 中選出關(guān)鍵字最小的記錄，又需要做 n-2 次比較。事實(shí)上，后面的 n-2 次比較中，有許多比較可能在前面的 n-1 次比較中已經(jīng)做過，但由于前一趟排序時(shí)未保留這些比較

22、結(jié)果，所以后一趟排序時(shí)又重復(fù)執(zhí)行了這些比較 操作 .堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。八基數(shù)排序箱排序 (Bin Sort)1、箱排序的基本思想箱排序也稱桶排序(Bucket Sort)，其基本思想是：設(shè)置若干個(gè)箱子，依次掃描待排序的記錄 R0 , R1，Rn-1，把關(guān)鍵字等于k的記錄全都裝入到第k個(gè)箱子里(分配)，然后按序號(hào)依次將各非空的箱子首尾連接 起來 (收集 )?！纠恳獙⒁桓被煜吹?2張撲克牌按點(diǎn)數(shù) A<2<yJvQ<K 排序，需設(shè)置13個(gè)"箱子"，排序時(shí)依次將每張 牌按點(diǎn)數(shù)放入相應(yīng)的箱子里，然后依次將這些箱子首尾相接，就得到

23、了按點(diǎn)數(shù)遞增序排列的一副牌。2、箱排序中，箱子的個(gè)數(shù)取決于關(guān)鍵字的取值范圍。若 R0.n-1 中關(guān)鍵字的取值范圍是 0 到 m-1 的整數(shù)，則必須設(shè)置 m 個(gè)箱子。因此箱排序要求關(guān)鍵字的 類型是有限類型，否則可能要無限個(gè)箱子。箱排序?qū)嵱脙r(jià)值不大，僅適用于作為基數(shù)排序的一個(gè)中間步驟。桶排序箱排序的變種。為了區(qū)別于上述的箱排序，姑且稱它為桶排序(實(shí)際上箱排序和桶排序是同義詞)。1 、桶排序基本思想桶排序的思想是把 0， 1）劃分為 n 個(gè)大小相同的子區(qū)間，每一子區(qū)間是一個(gè)桶。然后將 n 個(gè)記錄分配到 各個(gè)桶中。因?yàn)殛P(guān)鍵字序列是均勻分布在0， 1）上的，所以一般不會(huì)有很多個(gè)記錄落入同一個(gè)桶中。由于同

24、一桶中的記錄其關(guān)鍵字不盡相同，所以必須采用關(guān)鍵字比較的排序方法（通常用插入排序 ） 對(duì)各個(gè)桶進(jìn)行排序，然后依次將各非空桶中的記錄連接（收集 ）起來即可。注意：這種排序思想基于以下假設(shè)：假設(shè)輸入的 n 個(gè)關(guān)鍵字序列是隨機(jī)分布在區(qū)間 0 ，1）之上。若關(guān)鍵字序列 的取值范圍不是該區(qū)間，只要其取值均非負(fù)，我們總能將所有關(guān)鍵字除以某一合適的數(shù)，將關(guān)鍵字映射到 該區(qū)間上。但要保證映射后的關(guān)鍵字是均勻分布在0，1） 上的?；鶖?shù)排序基數(shù)排序的基本思想是：從低位到高位依次對(duì)Kj（j=d-1 , d-2 ,，0）進(jìn)行箱排序。在d趟箱排序中，所需的箱子數(shù)就是基數(shù)rd，這就是”基數(shù)排序"名稱的由來。假設(shè)原

25、來有一串?dāng)?shù)值如下所示：73, 22, 93, 43, 55, 14, 28, 65, 39, 81 首先根據(jù)個(gè)位數(shù)的數(shù)值，在走訪數(shù)值時(shí)將它們分配至編號(hào) 0到9的桶子中：01 812 223 73 93 434 145 55 65678 289 39 接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：81, 22, 73, 93, 43, 14, 55, 65, 28, 39接著再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來分配：01 142 22 283 394 435 556 657 738 819 93 接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：14, 22, 28, 39, 43,

26、55, 65, 73, 81, 93 這時(shí)候整個(gè)數(shù)列已經(jīng)排序完畢； 如果排序的對(duì)象有三位數(shù)以上， 則持續(xù)進(jìn)行以上的動(dòng)作直至最高位數(shù)為止。 LSD 的基數(shù)排序適用于位數(shù)小的數(shù)列，如果位數(shù)多的話，使用 MSD 的效率會(huì)比較好， MSD 的方式恰與LSD 相反，是由高位數(shù)為基底開始進(jìn)行分配，其他的演算方式則都相同 實(shí)作* C#include <stdio.h> #include <stdlib.h> int main(void) int data10 = 73, 22, 93, 43, 55, 14, 28, 65, 39, 81; int temp1010 = ;int o

27、rder10 = ;int i, j, k, n, lsd; k = 0; n = 1;printf("n 排序前 : "); for(i = 0; i < 10; i+) printf("%d ", data); putchar('n');while(n <= 10) for(i = 0; i < 10; i+) lsd = (data / n) % 10); templsdorderlsd = data; orderlsd+;printf("n 重新排列 : "); for(i = 0; i &l

28、t; 10; i+) if(order != 0) for(j = 0; j < order; j+) datak = tempj; printf("%d ", datak); k+; order = 0; n *= 10;k = 0; putchar('n'); printf("n 排序后 : ");for(i = 0; i < 10; i+) printf("%d ", data);return 0;* Java public class RadixSort public static void sor

29、t(int number, int d) int k = 0;int n = 1;int temp = new intnumber.lengthnumber.length; int order = new intnumber.length;while(n <= d) for(int i = 0; i < number.length; i+) int lsd = (number / n) % 10); templsdorderlsd = number; orderlsd+;for(int i = 0; i < number.length; i+) if(order != 0)f

30、or(int j = 0; j < order; j+) numberk = tempj;k+; order = 0; n *= 10; k = 0;public static void main(String args) int data =73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100; RadixSort.sort(data, 100);for(int i = 0; i < data.length; i+) System.out.print(data + " "); 按平均時(shí)間將排序分為四類：(1) 平方階

31、(O(n2) 排序 一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；(2 )線性對(duì)數(shù)階 (O(nlgn) 排序 如快速、堆和歸并排序；(3) 0(n1+ £ )階排序£是介于0和1之間的常數(shù)，即0< £ <1，如希爾排序;4 )線性階 (O(n) 排序如桶、箱和基數(shù)排序。各種排序方法比較簡單排序中直接插入最好，快速排序最快，當(dāng)文件為正序時(shí)，直接插入和冒泡均最佳。影響排序效果的因素因?yàn)椴煌呐判蚍椒ㄟm應(yīng)不同的應(yīng)用環(huán)境和要求，所以選擇合適的排序方法應(yīng)綜合考慮下列因素： 待排序的記錄數(shù)目 n ； 記錄的大小 (規(guī)模 )； 關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)； 對(duì)穩(wěn)

32、定性的要求； 語言工具的條件； 存儲(chǔ)結(jié)構(gòu)； 時(shí)間和輔助空間復(fù)雜度等。不同條件下，排序方法的選擇(1) 若n較小(如nw 50),可采用直接插入或直接選擇排序。當(dāng)記錄規(guī)模較小時(shí)，直接插入排序較好；否則因?yàn)橹苯舆x擇移動(dòng)的記錄數(shù)少于直接插人，應(yīng)選直接選擇 排序?yàn)橐恕?2) 若文件初始狀態(tài)基本有序 (指正序 ),則應(yīng)選用直接插人、冒泡或隨機(jī)的快速排序?yàn)橐耍?3) 若 n 較大,則應(yīng)采用時(shí)間復(fù)雜度為 O(nlgn) 的排序方法：快速排序、堆排序或歸并排序?？焖倥判蚴悄壳盎诒容^的內(nèi)部排序中被認(rèn)為是最好的方法,當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí),快速排 序的平均時(shí)間最短；堆排序所需的輔助空間少于快速排序,并且不

33、會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不 穩(wěn)定的。若要求排序穩(wěn)定, 則可選用歸并排序。 但本章介紹的從單個(gè)記錄起進(jìn)行兩兩歸并的 排序算法并不值得提 倡,通?？梢詫⑺椭苯硬迦肱判蚪Y(jié)合在一起使用。先利用直接插入排序求得較長的有序子文件,然后再 兩兩歸并之。因?yàn)橹苯硬迦肱判蚴欠€(wěn)定的,所以改進(jìn)后的歸并排序仍是穩(wěn)定的。4)在基于比較的排序方法中,每次比較兩個(gè)關(guān)鍵字的大小之后,僅僅出現(xiàn)兩種可能的轉(zhuǎn)移,因此可以用一 棵二叉樹來描述比較判定過程。當(dāng)文件的 n 個(gè)關(guān)鍵字隨機(jī)分布時(shí),任何借助于 "比較 "的排序算法,至少需要 O(nlgn) 的時(shí)間。 箱排序和基數(shù)排序只需一步就會(huì)引

34、起 m 種可能的轉(zhuǎn)移,即把一個(gè)記錄裝入 m 個(gè)箱子之一,因此在一般 情況下，箱排序和基數(shù)排序可能在 O(n)時(shí)間內(nèi)完成對(duì)n個(gè)記錄的排序。但是，箱排序和基數(shù)排序只適用于 像字符串和整數(shù)這類有明顯結(jié)構(gòu)特征的關(guān)鍵字, 而當(dāng)關(guān)鍵字的取值范圍屬于某個(gè)無窮集合 (例如實(shí)數(shù)型關(guān)鍵 字)時(shí)，無法使用箱排序和基數(shù)排序，這時(shí)只有借助于"比較"的方法來排序。若 n 很大，記錄的關(guān)鍵字位數(shù)較少且可以分解時(shí)，采用基數(shù)排序較好。雖然桶排序?qū)﹃P(guān)鍵字的結(jié)構(gòu)無要 求，但它也只有在關(guān)鍵字是隨機(jī)分布時(shí)才能使平均時(shí)間達(dá)到線性階，否則為平方階。同時(shí)要注意，箱、桶、 基數(shù)這三種分配排序均假定了關(guān)鍵字若為數(shù)字時(shí)，則其值

35、均是非負(fù)的，否則將其映射到箱(桶)號(hào)時(shí)，又要增加相應(yīng)的時(shí)間。(5)有的語言 (如 Fortran ， Cobol 或 Basic 等)沒有提供指針及遞歸， 導(dǎo)致實(shí)現(xiàn)歸并、 快速 (它們用遞歸實(shí)現(xiàn)較 簡單)和基數(shù) (使用了指針 )等排序算法變得復(fù)雜。此時(shí)可考慮用其它排序。(6)本章給出的排序算法，輸人數(shù)據(jù)均是存儲(chǔ)在一個(gè)向量中。當(dāng)記錄的規(guī)模較大時(shí)，為避免耗費(fèi)大量的時(shí)間 去移動(dòng)記錄，可以用鏈表作為存儲(chǔ)結(jié)構(gòu)。譬如插入排序、歸并排序、基數(shù)排序都易于在鏈表上實(shí)現(xiàn)，使之 減少記錄的移動(dòng)次數(shù)。但有的排序方法，如快速排序和堆排序，在鏈表上卻難于實(shí)現(xiàn)，在這種情況下，可 以提取關(guān)鍵字建立索引表，然后對(duì)索引表進(jìn)行排序

36、。然而更為簡單的方法是：引人一個(gè)整型向量 t 作為輔 助表，排序前令t=i(O vi<n)若排序算法中要求交換 R和Rj，則只需交換t和tj即可；排序結(jié)束后，向量 t就 指示了記錄之間的順序關(guān)系：RtO.key < Rt1.keyV 胡Rei若要求最終結(jié)果是：R0.key V R1.key V V-Rkey則可以在排序結(jié)束后，再按輔助表所規(guī)定的次序重排各記錄，完成這種重排的時(shí)間是O(n)265,301,751,127,937,863,742,694,76,438這十個(gè)數(shù)字進(jìn)行：直接插入，希爾（ SHELL ），冒泡，直接選擇，歸并排序，記數(shù)排序，要求寫出第一趟排序結(jié)果，例如快排第一

37、趟為：76 127 265 751 937 863 742 694 301 438， /*265 作為基 */；做出其他的直接插入 :265 301751 127 937 863 742 694 76 438希爾 :265 742 69476 438 863 901 751 129 937 以 5 為距離冒泡 : 265 301127 751 863 742 694 76 438 937直接選擇 :76 301751 265 937 863 742 694 127 438歸并排序 :265 301127 751 863 937 694 742 301 438記數(shù)排序 :301 127937 4

38、38 742 751 76 265 863 694 以 100 為基距大小二復(fù)雜度同一問題可用不同算法解決，而一個(gè)算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于 選擇合適算法和改進(jìn)算法。一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮。1、時(shí)間復(fù)雜度(1)時(shí)間頻度 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒 有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且 一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。 一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或

39、時(shí)間頻度。記為T(n) 。(2)時(shí)間復(fù)雜度 在剛才提到的時(shí)間頻度中， n 稱為問題的規(guī)模，當(dāng) n 不斷變化時(shí)，時(shí)間頻度 T(n) 也會(huì)不斷變化。但有時(shí)我 們想知道它變化時(shí)呈現(xiàn)什么規(guī)律。為此，我們引入時(shí)間復(fù)雜度概念。一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模 n 的某個(gè)函數(shù)，用 T(n) 表示，若有某個(gè)輔助函數(shù) f(n),使得當(dāng)n趨近于無窮大時(shí)，T (n)/f (n)的極限值為不等于零的常數(shù)，則稱 f(n)是T(n)的同數(shù)量級(jí)函數(shù)。 記作T(n)= O (f(n),稱O (f(n)為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。在各種不同算法中， 若算法中語句執(zhí)行次數(shù)為一個(gè)常數(shù)， 則時(shí)間復(fù)雜度為

40、 O(1), 另外，在時(shí)間頻度不相同時(shí)， 時(shí)間復(fù)雜度有可能相同，如T(n)=nA2+3n+4與T(n)=4nA2+2n+1它們的頻度不同，但時(shí)間復(fù)雜度相同，都為 O(nA2) o按數(shù)量級(jí)遞增排列，常見的時(shí)間復(fù)雜度有：常數(shù)階0(1),對(duì)數(shù)階O(log2n),線性階0(n),線性對(duì)數(shù)階O(nlog2n),平方階02)，立方階0(nT),，k次 方階O(nk),指數(shù)階0(2n)。隨著問題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。介紹選擇排序是說，每次從數(shù)列中找出一個(gè)最小的數(shù)放到最前面來，再從剩下的n-1 個(gè)數(shù)中選擇一個(gè)最小的，不斷做下去。插入排序是，每次從數(shù)列中取一個(gè)還沒有取出過

41、的數(shù)，并按照大小關(guān)系插入到已經(jīng)取出的數(shù)中使得已經(jīng)取 出的數(shù)仍然有序。冒泡排序分為若干趟進(jìn)行，每一趟排序從前往后比較每兩個(gè)相鄰的元素的大小并在前面的那個(gè)數(shù)比緊接它 后的數(shù)大時(shí)交換位置；進(jìn)行足夠多趟直到某一趟跑完后發(fā)現(xiàn)這一趟沒有進(jìn)行任何交換操作.事實(shí)上，在第一趟冒泡結(jié)束后，最后面那個(gè)數(shù)肯定是最大的了，于是第二次只需要對(duì)前面n-1個(gè)數(shù)排序，這又將把這n-1個(gè)數(shù)中最大的數(shù)放到整個(gè)數(shù)列的倒數(shù)第二個(gè)位置。 這樣下去，冒泡排序第 i 趟結(jié)束后后面 i 個(gè)數(shù)都已經(jīng)到位了，第 i+1 趟實(shí)際上只考慮前 n-i 個(gè)數(shù).我們來算一下最壞情況下三種算法各需要多少次比較和賦值操作。選擇排序在第 i 次選擇時(shí)賦值和比較都

42、需要 n-i 次(在 n-i+1 個(gè)數(shù)中選一個(gè)出來作為當(dāng)前最小值，其余 n-i 個(gè)數(shù)與當(dāng)前最小值比較并不斷更新當(dāng)前最小值)，然后需要一次賦值操作?？偣残枰猲(n-1)/2次比較與n(n-1)/2+n 次賦值。插入排序在第i次尋找插入位置時(shí)需要最多i-1次比較（從后往前找到第一個(gè)比待插入的數(shù)小的數(shù)，最壞情況發(fā)生在這個(gè)數(shù)是所有已經(jīng)取出的數(shù)中最小的一個(gè)的時(shí)候） ，在已有數(shù)列中給新的數(shù)騰出位置需要 i-1 次賦 值操作來實(shí)現(xiàn)， 還需要兩次賦值借助臨時(shí)變量把新取出的數(shù)搬進(jìn)搬出。 也就是說， 最壞情況下比較需要 n（n -1）/2 次，賦值需要 n（n-1）/2+2n 次。冒泡排序第 i 趟排序需要比較

43、n-i 次， n-1 趟排序總共比較 n（n-1）/2 次。給出的序列逆序排列是最壞的情況， 這時(shí)每一次比較都要進(jìn)行交換操作。一次交換操作需要 3 次賦值實(shí)現(xiàn)，因此冒泡排序最壞情況下需要賦值 3n（n-1）/2 次。按照漸進(jìn)復(fù)雜度理論，忽略所有的常數(shù)，三種排序的最壞情況下復(fù)雜度都是一樣的05人2）。但實(shí)際應(yīng)用中三種排序的效率并不相同。實(shí)踐證明，插入排序是最快的，因?yàn)槊恳淮尾迦霑r(shí)尋找插入的位置多數(shù)情況只 需要與已有數(shù)的一部分進(jìn)行比較。你或許會(huì)說冒泡排序也可以在半路上完成，還沒有跑到第n-1 趟就已經(jīng)有序。但冒泡排序的交換操作更費(fèi)時(shí)，而插入排序中找到了插入的位置后移動(dòng)操作只需要用賦值就能完成 （你

44、可能知道這還能用 move ）。但大家想過嗎，這只是最壞情況下的。在很多時(shí)候，復(fù)雜度沒有這么大，因?yàn)椴迦牒兔芭菰跀?shù)列已經(jīng)比較有序的情況下需要的操作遠(yuǎn)遠(yuǎn)低于nA2次（最好情況下甚至是線性的）。拋開選擇排序不說（因?yàn)樗膹?fù)雜度是“死”的，對(duì)于選擇排序沒有什么 “好”的情況），我們下面探討插入排序和冒泡排序在特定數(shù)據(jù)和平均情 況下的復(fù)雜度。你會(huì)發(fā)現(xiàn)，如果把插入排序中的移動(dòng)賦值操作看作是把當(dāng)前取出的元素與前面取出的且比它大的數(shù)逐一交 換，那插入排序和冒泡排序?qū)?shù)據(jù)的變動(dòng)其實(shí)都是相鄰元素的交換操作。下面我們說明，若只能對(duì)數(shù)列中 相鄰的數(shù)進(jìn)行交換操作，如何計(jì)算使得 n 個(gè)數(shù)變得有序最少需要的交換次數(shù)。我們

45、定義逆序?qū)Φ母拍?。假設(shè)我們要把數(shù)列從小到大排序，一個(gè)逆序?qū)κ侵傅脑谠瓟?shù)列中，左邊的某個(gè)數(shù)比右邊的大。也就是說，如果找到了某個(gè)i和j使得i<j且Ai>Aj，我們就說我們找到了一個(gè)逆序?qū)?。比如說，數(shù)列 3,1,4,2 中有三個(gè)逆序?qū)Γ?而一個(gè)已經(jīng)有序的數(shù)列逆序?qū)€(gè)數(shù)為 0。我們發(fā)現(xiàn)， 交換兩個(gè)相鄰的數(shù) 最多消除一個(gè)逆序?qū)?，且冒泡排序（或插入排序）中的一次交換恰好能消除一個(gè)逆序?qū)?。那么顯然，原數(shù) 列中有多少個(gè)逆序?qū)γ芭菖判颍ɑ虿迦肱判颍┚托枰嗌俅谓粨Q操作，這個(gè)操作次數(shù)不可能再少。若給出的n個(gè)數(shù)中有m個(gè)逆序?qū)Γ迦肱判虻臅r(shí)間復(fù)雜度可以說是O（m+n）的，而冒泡排序不能這么說，因?yàn)槊芭菖判?/p>

46、有很多 “無用 ”的比較（比較后沒有交換） ，這些無用的比較超過了 O（m+n） 個(gè)。從這個(gè)意義上 說，插入排序仍然更為優(yōu)秀，因?yàn)槊芭菖判虻膹?fù)雜度要受到它跑的趟數(shù)的制約。一個(gè)典型的例子是這樣的 數(shù)列：8, 2, 3, 4, 5, 6, 7, 1 。在這樣的輸入數(shù)據(jù)下插入排序的優(yōu)勢(shì)非常明顯， 冒泡排序只能哭著喊上天不公。然而， 我們并不想計(jì)算排序算法對(duì)于某個(gè)特定數(shù)據(jù)的效率。 我們真正關(guān)心的是， 對(duì)于所有可能出現(xiàn)的數(shù)據(jù)， 算法的平均復(fù)雜度是多少。不O(nA2)的用激動(dòng)了，平均復(fù)雜度并不會(huì)低于平方。下面證明，兩種算法的平均復(fù)雜度仍然是我們僅僅證明算法需要的交換次數(shù)平均為0(nA2)就足夠了。前面已經(jīng)

47、說過，它們需要的交換次數(shù)與逆序?qū)Φ膫€(gè)數(shù)相同。我們將證明， n 個(gè)數(shù)的數(shù)列中逆序?qū)€(gè)數(shù)平均 O(nA2) 個(gè)。計(jì)算的方法是十分巧妙的。 如果把給出的數(shù)列反過來 (從后往前倒過來寫) ，你會(huì)發(fā)現(xiàn)原來的逆序?qū)ΜF(xiàn)在變 成順序的了，而原來所有的非逆序?qū)ΜF(xiàn)在都成逆序了。正 反兩個(gè)數(shù)列的逆序?qū)€(gè)數(shù)加起來正好就是數(shù)列所有數(shù)對(duì)的個(gè)數(shù)，它等于 n(n-1)/2 。于是，平均每個(gè)數(shù)列有 n(n-1)/4個(gè)逆序?qū)?。忽略常?shù)，逆序?qū)ζ?均個(gè)數(shù) O(nA2) 。上面的討論啟示我們，要想搞出一個(gè)復(fù)雜度低于平方級(jí)別的排序算法，我們需要想辦法能把離得老遠(yuǎn)的兩 個(gè)數(shù)進(jìn)行操作。人們想啊想啊想啊， 怎么都想不出怎樣才能搞出復(fù)雜度低于

48、平方的算法。 后來， 英雄出現(xiàn)了， Donald Shell 發(fā)明了一種新的算法，我們將證明它的復(fù)雜度最壞情況下也沒有 O(nA2) (似乎有人不喜歡研究正確性和復(fù)雜度的證明，我會(huì)用實(shí)例告 訴大家，這些證明是非常有意思的) 。他把這種算法叫做 Shell 增量排序算法(大家常說的希爾排 序)。Shell 排序算法依賴一種稱之為 “排序增量 ”的數(shù)列，不同的增量將導(dǎo)致不同的效率。假如我們對(duì) 20 個(gè)數(shù)進(jìn) 行排序，使用的增量為 1,3,7。那么，我們首先對(duì)這 20個(gè)數(shù)進(jìn)行“7非序”(7sortedness)。所謂7-排序，就是按照位置除以7的余數(shù)分組進(jìn)行排序。具體地 說，我們將把在1、8、15 三

49、個(gè)位置上的數(shù)進(jìn)行排序，將第2、9、16 個(gè)數(shù)進(jìn)行排序，依此類推。這樣，對(duì)于任意一個(gè)數(shù)字 k，單看 A(k),A(k+7), A(k+14),這些數(shù)是有序的。 7-排序后，我們接著又進(jìn)行一趟 3-排序(別忘了我們使用的排序增量為 1,3,7)。最后進(jìn) 行 1- 排序(即普通的排序)后整個(gè)Shell 算法完成?？纯次覀兊睦樱? 8 1500 1 1 2 2 3 3 4 4 5 6 5 6 8 7 7 9 8 9 <- 3-排序后00 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 <- 1-排序后(完成)在每一趟、每一組的排序中我們總是使用插入排序。仔細(xì)觀察上

50、面的例子你會(huì)發(fā)現(xiàn)是什么導(dǎo)致了 Shell 排 序的高效。對(duì)，每一趟排序?qū)⑹沟脭?shù)列部分有序，從而使得以后的插入排序很快找到插入位置。我們下面將緊緊圍繞這一點(diǎn)來證明 Shell 排序算法的時(shí)間復(fù)雜度上界。只要排序增量的第一個(gè)數(shù)是1 ，Shell 排序算法就是正確的。但是不同的增量將導(dǎo)致不同的時(shí)間復(fù)雜度。我們上面例子中的增量 (1, 3, 7,15, 31,2Ak1)是使用最廣泛的增量序列之一，可以證明使用這個(gè)增量的時(shí)間復(fù)雜度為0(n"n)這個(gè)證明很簡單，大家可以參看一些其它的資料，我們今天不證明它。今天我們證明，使用增量1,2, 3, 4, 6, 8, 9,12,16,，2*3,時(shí)間復(fù)雜

51、度為 O(n*(log n)A2)很顯然，任何一個(gè)大于 1的正整數(shù)都可以表示為 2x+3y，其中x和y是非負(fù)整數(shù)。于是，如果一個(gè)數(shù)列已 經(jīng)是 2-排序的且是 3 -排序的，那么對(duì)于此時(shí)數(shù)列中的每一個(gè)數(shù)A(i)，它的左邊比它大的只有可能是A(i-1)A2絕對(duì)不可能比A12大，因?yàn)?0可以表示為兩個(gè) 2 和兩個(gè) 3的和，則A2<A4<A6<A9<A12 。那么， 在這個(gè)增量中的 1-排序時(shí)每個(gè)數(shù)找插入位置只需要比較一次。 一共有 n 個(gè)數(shù)， 所 以1-排序是O(n)的。事實(shí)上，這個(gè)增量中的2-排序也是0(n)，因?yàn)樵?-排序之前，這個(gè)數(shù)列已經(jīng)是4-排序且6-排序過的，只看數(shù)

52、列的奇數(shù)項(xiàng)或者 偶數(shù)項(xiàng)(即單看每一組)的話就又成了剛才的樣子。這個(gè)增量序列巧妙就巧妙在，如果我們要進(jìn)行h-排序，那么它一定是 2h-排序過且3h-排序過，于是處理 每個(gè)數(shù)A(i)的插入時(shí)就只需要和A(i-h)進(jìn)行比較。這個(gè)結(jié)論對(duì)于最開始幾次(h值較大時(shí))的h-排序同樣成立，當(dāng)2h、3h大于 n 時(shí)，按照定義，我 們也可以認(rèn)為數(shù)列是2h-排序和3h-排序的，這并不影響上述結(jié)論的正確性(你也可以認(rèn)為h太大以致于排序時(shí)每一組里的數(shù)字不超過 3 個(gè)，屬于常數(shù)級(jí)) 。現(xiàn) 在，這個(gè)增量中的每一趟排序都是 O(n) 的，我們只需要數(shù)一下一共跑了多少趟。也就是說，我們現(xiàn)在只需要知 道小于 n 的數(shù)中有多少個(gè)數(shù)

53、具有2Ap*3Aq的形式。要想2Ap*3Aq不超過n , p的取值最多O(log n)個(gè)，q的取值最多也是 O(log n)個(gè)，兩兩 組合的話共有 O(logn*logn) 種情況。于是，這樣的增量排序需要跑O(lognF2)趟，每一趟的復(fù)雜度O(n)，總的復(fù)雜度為 O(n*(log n)A2)。早就說過了，證明時(shí)間復(fù)雜度其實(shí)很有意思。我們自然會(huì)想，有沒有能使復(fù)雜度降到 O(nlogn) 甚至更低的增量序列。很遺憾，現(xiàn)在沒有任何跡象表明存 在 O(nlogn) 的增量排序。但事實(shí)上，很多時(shí)候 Shell 排序的實(shí)際效率超過了 O(nlogn) 的排序算法。對(duì)于 O(nlogn) 的排序算法，我

54、們?cè)敿?xì)介紹歸并排序并證明歸并排序的時(shí)間復(fù)雜度，然后簡單介紹堆排序， 之后給出快速排 序的基本思想和復(fù)雜度證明。最后我們將證明， O(nlogn) 在理論上已經(jīng)達(dá)到了最優(yōu)。為了保持系列文章的完整性，我還是花時(shí) 間寫了一下。首先考慮一個(gè)簡單的問題：如何在線性的時(shí)間內(nèi)將兩個(gè)有序隊(duì)列合并為一個(gè)有序隊(duì)列(并輸出)？A 隊(duì)列： 1 3 5 7 9B 隊(duì)列： 1 2 7 8 9看上面的例子， AB 兩個(gè)序列都是已經(jīng)有序的了。 在給出數(shù)據(jù)已經(jīng)有序的情況下， 我們會(huì)發(fā)現(xiàn)很多神奇的事， 比如，我們將要輸出的第一個(gè)數(shù)一定來自于這兩個(gè)序列各自最前面的那個(gè)數(shù)。兩個(gè)數(shù)都是 1，那么我們隨便取出一個(gè)(比如 A 隊(duì)列的那 個(gè)

55、 1 )并輸出：A 隊(duì)列： 1 3 5 7 9B 隊(duì)列： 1 2 7 8 9輸出： 1注意，我們?nèi)〕隽艘粋€(gè)數(shù)，在原數(shù)列中刪除這個(gè)數(shù)。刪除操作是通過移動(dòng)隊(duì)首指針實(shí)現(xiàn)的，否則復(fù)雜度就高了。現(xiàn)在，A隊(duì)列打頭的數(shù)變成 3 了，B隊(duì)列的隊(duì)首仍然是1。此時(shí)，我們?cè)俦容^ 3和1哪個(gè)大并輸出小的那個(gè)數(shù)：A 隊(duì)列：1 3 5 7 9B 隊(duì)列： 1 2 7 8 9輸出： 1 1接下來的幾步如下：A 隊(duì)列： 1 3 5 7 9 A 隊(duì)列： 1 3 5 7 9 A 隊(duì)列： 1 3 5 7 9 A 隊(duì)列： 1 3 5 7 9B 隊(duì)列：1 2 7 8 9 => B 隊(duì)列：1 2 7 8 9 => B 隊(duì)列：1 2 7 8 9 => B 隊(duì)列：1 2 7 8 9輸出： 1 1 2 輸出： 1 1 2 3 輸出： 1 1 2 3 5 輸出： 1 1 2 3 5 7我希望你明白了這是怎么做的。這個(gè)做法顯然是正確的，復(fù)雜度顯然是線性。O(nlogn)歸并排序(Merge Sort)將會(huì)用到