數(shù)據結構（C語言版）（第三版）（微課版）第8章 排序

第8章排序教學要求相關知識點排序的定義和基本術語各種內部排序方法的基本思想、算法特點、排序過程和它們的時間復雜度分析穩(wěn)定排序方法和不穩(wěn)定排序方法的定義及判斷學習重點簡單插入排序、折半插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序的排序方法、算法描述和性能分析；各種排序方法的比較目錄插入排序算法交換排序算法選擇排序算法3排序的基本概念124歸并排序算法5排序算法的比較6本章小結78.1排序的基本概念8.1排序的基本概念排序的基本概念1.排序

假設一組含有n個記錄的序列為{r0，r1，…，rn-1}，它們相應的關鍵字序列為{k0，k2，…，kn-1}，這些關鍵字相互之間可以進行比較，使得它們滿足以下的非遞減(或非遞增)的關系，即n個記錄的序列重新排列成一個按關鍵字有序的序列，上述操作即為排序。本章介紹的算法均以升序為例，降序方法類似，只需要將算法中的大于符號和小于符號互換即可。8.1排序的基本概念2.排序算法的穩(wěn)定性

如果在數(shù)據元素序列中有兩個數(shù)據元素ri和rj，它們的關鍵字ki==kj，且在排序之前，記錄ri排在rj前面。如果在排序之后，記錄ri仍在rj的前面,則稱這個排序方法是穩(wěn)定的,否則稱這個排序方法是不穩(wěn)定的。3.內排序與外排序內排序是指在排序期間數(shù)據元素全部存放在內存的排序；外排序是指在排序期間全部元素個數(shù)太多，不能同時存放在內存，必須根據排序過程的要求，不斷在內存與外存之間移動的排序。8.1排序的基本概念4.記錄存儲描述數(shù)據元素之間按照關鍵字的“大小”進行比較，并且這個“大小”的含義是廣義的，可以理解為關鍵字之間存在某種“領先”的關系。數(shù)據元素稱為“記錄”，可用C語言描述如下：typedefintKeyType;/*定義關鍵字類型為整型*/typedefstruct{

KeyTypekey; /*關鍵字項*/

InfoTypeotherinfo; /*其他數(shù)據項*/}RcdType; /*記錄類型*/8.2插入排序算法8.2插入排序算法插入排序（InsertionSort）的基本思想是，每次將一個待排序的記錄，按其關鍵字的大小插入到前面已經排好序的子序列中的適當位置，直到全部記錄插入完成為止。直接插入排序直接插入排序（StraightInsertionSort）的基本方法是將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。8.2插入排序算法直接插入排序為了減少排序過程中元素的比較次數(shù)，在插入排序算法中引入r[0]作為哨兵，其主要作用是：(1)在進入查找插入位置循環(huán)之前，它保存第i個記錄r[i]的副本，使不至于因記錄后移而丟失r[i]的內容。(2)在查找插入位置的過程中避免數(shù)組下標出界。一旦出界，因為r[0].key和自己相比較，循環(huán)判定條件不成立，使得查找插入位置的循環(huán)過程結束，從而避免了在該循環(huán)內每一次都要檢測數(shù)組下標是否越界。引入哨兵后使得測試查找循環(huán)條件的時間大約減少了一半，所以對于記錄數(shù)較大的序列所節(jié)約的時間就相當可觀了。8.2插入排序算法直接插入排序算法voidInsertSort(RecordTyper[],intn)//對表r中的第1到第n個記錄進行直接插入排序，r[0]為哨兵{ inti,j; for(i=2;i<=n;i++)

//初始r[1]為有序序列，i從2開始 {r[0]=r[i];/*設置監(jiān)視哨*/ j=i-1; while(r[0].key<r[j].key) {r[j+1]=r[j];j--;}/*記錄后移*/ r[j+1]=r[0];//把r[0]中原記錄插入正確位置 }}8.2插入排序算法直接插入排序算法【例8.1】已知序列{70，83，100，65，65}，給出采用直接插入排序算法做升序排列的排序過程（小括號內的是哨兵，方括號內的數(shù)據序列為有序序列）。初始時：(哨兵)[70] 83 100 65 65第1趟: (83) [70 83] 100 65 65第2趟: (100) [70 83 100] 65

65第3趟: (65) [65 70 83 100] 65第4趟: (65) [65 65 70 83 100]8.2插入排序算法算法分析設待排序元素個數(shù)為n,則該算法的主程序執(zhí)行n-1趟。排序關鍵字比較次數(shù)和元素移動次數(shù)與元素排序關鍵字的初始排列有關。最好情況下,初始排序關鍵字已經有序，for循環(huán)進行一輪關鍵字比較，內循環(huán)中while的條件均不滿足，因此共比較n-1次，移動0次，算法的時間復雜度為O(n)。8.2插入排序算法最壞情況下，待排序序列完全逆序，for循環(huán)共運行n-1次，while循環(huán)總的比較次數(shù)為：2+3+…+n=(n+2)(n-1)/2。因為待排序序列完全逆序，故需要移動i-1步，這樣總的移動次數(shù)為：1+2+3+…+n-1=n(n-1)/2。平均情況下，比較和移動次數(shù)為(n(n-1)/2+(n-1)(n+2)/2)/2=((n-1)(2n+2)/2)/2=(n2-1)/2次。直接插入排序的時間復雜度為o(n2)。當待排序記錄數(shù)較少且已基本有序時，使用直接插入排序速度較快。直接插入排序是一種穩(wěn)定的排序方法。8.2插入排序算法折半插入排序當待排序的記錄數(shù)很大時，不宜再用直接插入排序，需要使用更快的排序算法。直接插入排序有兩個基本操作，比較記錄的關鍵字和移動記錄。折半插入排序對比較記錄關鍵字的整個基本操作進行了改進。在直接插入排序算法中查找插入位置時，采用的是順序查找。折半插入排序就是用折半查找方法來代替直接插入算法中順序查找方法。8.2插入排序算法算法8.2折半插入排序算法voidBinarySort(RecordTyper[],intn) /*對順序表L進行折半插入排序*/{inti,j; intlow,high,m; for(i=1;i<=n;i++) {r[0]=r[i]; /*將要插入的元素置于r[0]中*/ low=1; high=i-1; while(low<=high)/*在有序段中查找*/ {m=(low+high)/2; /*使用折半查找*/8.2插入排序算法if(r[0].key<r[m].key) /*與有序段前半段的最大值相比較*/ high=m-1; elselow=m+1; } for(j=i-1;j>=high+1;--j)/*移動元素*/ r[j+1]=r[j]; r[high+1]=r[0]; }}8.2插入排序算法【例8.2】對數(shù)據序列{70，83，100，65，65}給出折半插入排序的操作過程。初始值：[70]，83，100，65，65第1趟：[70，83]，100，65，65第2趟：[70，83，100]，65，65第3趟：[65，70，83，100]，650第4趟：[65，65，70，83，100]8.2插入排序算法算法8.2折半插入排序算法折半插入排序所需的存儲空間和直接插入排序一樣與直接插入排序唯一不同的就是在有序段搜索插入位置時，使用折半查找方法，關鍵字之間的比較次數(shù)減少了，但是記錄的移動次數(shù)不變，故算法的時間復雜度同樣為O(n2)。折半插入排序法也是一種穩(wěn)定的排序方法。8.2插入排序算法希爾排序希爾排序（ShellSort）又稱為縮小增量排序。希爾排序的基本思想(1)將整個待排記錄序列按下標的一定增量分成若干個子序列，n=n1+n2+……nk；(2)分別對每個子序列進行直接插入排序，使得整個序列基本有序；(3)將增量縮小，劃分子序列，分別進行直接插入排序；(4)如此重復進行，最后對整個序列進行一次直接插入排序。8.2插入排序算法算法8.3希爾排序算法voidShellSort(RecordTyper[],intn)//對表r中第1到第n個記錄進行希爾排序，r[0]為哨兵{inti,j,d; for(d=n/2;d>0;d=d/2)/*初始增量為n/2，每次縮小增量值為d/2*/{for(i=d+1;i<=n;i++) {r[0]=r[i]; j=i-d;//前后記錄位置的增量是d,而不是1/*將r[i]插入有序增量子表*/8.2插入排序算法while(j>=0&&r[0].key<r[j].key)//將r[i]插入有序子表 {r[j+d]=r[j];j=j-d;}//查找插入位置r[j+d]=r[0];/*插入*/}}}8.2插入排序算法對序列{70，83，100，65，10，32，7，65，9}按增量序列{3，2，1}進行希爾排序的過程。8.2插入排序算法希爾排序希爾排序算法的分析是一個復雜的問題，因為它的時間是所取“增量”序列的函數(shù)。到目前為止尚未有人求得一種最好的增量序列，但大量的研究已得出一些局部結論。注意：增量序列的取法應使增量序列中的值沒有除1之外的公因子，并且最后一個增量值必須等于1。希爾排序算法在空間上只需要一個輔助單元，所以空間復雜度S(n)=O(1)。希爾排序比較適合處理大批量的雜亂無章的數(shù)據序列。希爾排序算法是不穩(wěn)定的。8.3交換排序算法8.3交換排序算法冒泡排序算法的基本思想：在n個元素中，將從頭開始相鄰的兩個記錄的關鍵字進行比較，若大小順序與要求的順序正好相反(即逆序)，則將兩個記錄交換位置，然后向下移動一個記錄，再依次比較下兩個相鄰記錄的關鍵字。以此類推，直至最后兩個相鄰記錄的關鍵字進行比較為止。上述過程稱作第一趟冒泡排序，結果使關鍵字最大(當要求升序排序時)的記錄被安置到最后一個記錄的位置上。然后進行第二趟冒泡排序。整個排序過程需要進行k(1≤k<n)趟冒泡排序，判斷冒泡排序結束的條件是“在一趟排序過程中沒有進行過交換記錄的操作”。8.3交換排序算法算法8.4冒泡排序算法voidBubble_sort(RecordTyper[],intn)/*對表r第1個到第n個記錄進行冒泡排序，r[0]為臨時交換空間*/{inti,j;intisExcheng;/*交換標志*/

for(i=1;i<n;i++){isExcheng=0;/*isExcheng=0為未交換*/

for(j=1;j<=n-i;j++){if(r[j].key>r[j+1].key)//如前者大于后，交換{r[0]=r[j+1];r[j+1]=r[j];r[j]=r[0];

isExcheng=1;/*isExcheng=1為發(fā)生交換*/}}if(isExcheng==0)break;/*未交換，排序結束*/}}8.3交換排序算法【例8.4】給出對序列{70，83，100，65，65}進行冒泡排序的過程。初始時

70 83 100 65 65第1趟 70 83 65 65

100第2趟 70 65 65

83第3趟 65 65

70第4趟 65 658.3交換排序算法冒泡排序若初始序列為“正序”序列，則只需進行一趟排序，在排序過程中進行n-1次關鍵字間的比較，且不移動記錄；反之，若初始序列為“逆序”序列，則需進行n-1趟排序，需進行次比較，并作等量級的記錄移動?？偟臅r間復雜度為T(n)=O(n2)。該算法僅需要一個交換記錄的存儲空間，因此算法的空間復雜度為S(n)=O(1)。冒泡排序是穩(wěn)定的。8.3交換排序算法快速排序(1)快速排序的基本思想任取待排序的n個記錄中的某個記錄作為基準，通過一趟排序，將待排序記錄分成左右兩個子序列，左子序列記錄的關鍵字均小于或等于該基準記錄的關鍵字，右子序列記錄的關鍵字均大于或等于該基準記錄的關鍵字，從而得到該記錄最終排序的位置，然后該記錄不再參加排序，此一趟排序稱為第一趟快速排序。然后對所分的左右子序列分別重復上述方法，直到所有的記錄都處在它們的最終位置，此時排序完成。8.3交換排序算法(2)快速排序的過程設待排序序列為r[s]到r[t]，為了實現(xiàn)一次劃分，可設置兩個指針low和high，它們的初值分別為s和t。以r[s]為基準，在劃分的過程中：①

首先從high端開始，依次向前掃描，并將掃描到的每一個記錄的關鍵字同基準記錄r[s]的關鍵字進行比較，直到r[high].key<r[s].key時，將r[high]賦值到low所指的位置；②

然后從low端開始依次向后掃描，并將掃描到的每一個記錄的關鍵字同r[s]的關鍵字進行比較，直到r[low].key>r[s].key時，將r[low]賦值到high所指的位置;8.3交換排序算法③如此交替改變掃描方向，重復第①和②兩個步驟，從兩端各自向中間位置靠攏，直到low等于或大于high。經過此次劃分后得到的左右兩個子序列分別為r[s]到r[low-1]和r[low+1]到r[t]。排序首先從r[1..n]開始，按上述方法劃分為r[s]到r[low-1]、r[low]和r[low+1]到r[t]三個序列，然后對r[s]到r[low-1]和r[low+1]到r[t]分別按上述方法進行再次劃分，依次重復，直到每個序列只剩一個元素為止。8.3交換排序算法(3)快速排序算法任意子系列r[low]到r[high]的一趟劃分算法intPartition(RecordTyper[],intlow,inthigh)/*對表r中的第low到第high個記錄進行一次快速排序的劃分，把關鍵字小于r[low].key的記錄放在r[low]前面，大于r[low].key的記錄放在r[low]后面*/{r[0]=r[low];/*把r[low]放在r[0]*/while(low<high)/*用r[low]進行一趟劃分*/{//在high端,尋找比r[low].key小的記錄放入lowwhile(low<high&&r[high].key>=r[0].key)--high;8.3交換排序算法r[low]=r[high];//在low端,尋找比r[low].key大的記錄放入highwhile(low<high&&r[low].key<=r[0].key)++low;r[high]=r[low];}r[low]=r[0];returnlow;//返回劃分后的基準記錄的位置}8.3交換排序算法/*快速排序算法*/voidQuicksort(RecordTyper[],intlow,inthigh){intloc;

if(low<high){//對第low個到第high個記錄進行一次劃分loc=Partition(r,low,high);Quicksort(r,low,loc-1);//劃分前半區(qū)Quicksort(r,loc+1,high);//劃分后半區(qū)}}8.3交換排序算法【例8.5】對序列{70，83，100，65，65}進行快速排序的過程。8.3交換排序算法8.3交換排序算法在一趟快速排序中，關鍵字比較的次數(shù)和記錄移動的次數(shù)均不超過n，時間復雜度主要取決于遞歸的深度，而深度與記錄初始序列有關。最壞情況是初始序列已基本有序，則遞歸的深度接近于n，算法時間復雜度T(n)=O(n2)。最好情況是初始序列非常均勻，則遞歸的深度接近于n個節(jié)點的完全二叉樹的深度log2n+1算法的時間復雜度T(n)=O(nlog2n)?？臻g上，因為是用遞歸實現(xiàn)的，所以也要看遞歸的深度。最好情況下S(n)=O(log2n)，最壞情況下S(n)=O(n2)。8.3交換排序算法快速排序算法主要適合于關鍵字大小分布比較均勻的記錄序列。就平均時間而言，快速排序是目前被認為是最好的一種內部排序方法。由于關鍵字相同的記錄可能會交換位置，因此快速排序算法是不穩(wěn)定的排序方法。8.4選擇排序算法8.4選擇排序算法選擇排序主要是每一趟從待排序記錄序列中選取一個關鍵字最小的記錄，依次放在已排序記錄序列的最后，直至全部記錄排完為止。直接選擇排序

1.基本思想設A={a1a2.........an}A’={}每次從A中選一個最小元素，放入A’尾端，直到A為空集。8.4選擇排序算法2.排序過程設待排序列為:a1a2.........an

首次在a1..an

中找最小值記錄與a1交換。第二次在a2..an

中找最小值記錄與a2交換；第i次在ai..an

中找最小值記錄與ai交換；第n-1次在an-1..an

中找最小值記錄與an-1交換。8.4選擇排序算法算法8.6直接選擇排序算法voidSelectsort(RecordTyper[],intn)/*對表r中的第1個到第n個記錄進行簡單選擇排序，r[0]為臨時交換空間*/{ inti,j,min;

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

{min=i;//在i到n范圍內尋找一個最小元素并放入r[i]中

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

if(r[min].key>r[j].key)min=j;8.4選擇排序算法if(min!=i)

{r[0]=r[min];r[min]=r[i];r[i]=r[0];}}

}8.4選擇排序算法【例8.6】給出對整數(shù)序列{70，83，100，65，65}進行直接選擇排序的過程。8.4選擇排序算法直接選擇排序在直接選擇排序中，第一次排序要進行n-1次比較，第二次排序要進行n-2次比較，第n-1次要進行1次比較，所以總的比較次數(shù)為n(n-1)/2。當待排序記錄序列為正序時，不需要移動記錄；當待排序記錄序列為逆序時，需要n-1次交換操作，而每次交換操作需移動數(shù)據3次，所以需要3(n-1)次數(shù)據移動操作。所以直接選擇排序算法的時間復雜度T(n)=O(n2)。直接選擇排序只需要一個輔助空間用于交換記錄，對于儲存空間沒有過高的要求，空間復雜度S(n)=O(1)。另外，直接選擇排序是一種穩(wěn)定的排序方法。8.4選擇排序算法堆排序堆排序是J.Willioms在1964年提出的一種選擇排序方法。堆排序是將記錄序列存儲在一個一維數(shù)組空間中，并將該序列看成一棵完全二叉樹中的節(jié)點序列{r1，r2，…，rn}，若編號分別滿足如下要求：

則稱該結構分別為小(頂)堆和大(頂)堆。由此，若上述數(shù)列是堆，則r1必是數(shù)列中的最小值或最大值，故分別稱為小(頂)堆或大(頂)堆。8.4選擇排序算法根據完全二叉樹的性質，當n個結點的完全二叉樹的結點由上至下，從左至右編號后，編號為i的結點其左孩子結點編號為2i（2i≤n），其右孩子編號為2i+1（2i+1≤n）。因此，可以借助完全二叉樹來描述堆：若完全二叉樹中任一非葉結點的值均小于等于（或大于等于）其左、右孩子結點的值，則從根結點開始按結點編號排列所得的結點序列就是一個堆。8.4選擇排序算法1.堆排序基本思想(1)先建立一個小頂堆，即先選得一個關鍵字為最小的記錄，然后與序列中的最后一個記錄交換，即若a1，a2，…，an為堆，則a1最小，將a1和an交換；(2)再對序列中的前n-1個記錄進行“篩選”，重新將它調整成為一個小頂堆，再將堆頂記錄和第n-1個記錄交換。即將剩余的a1，a2，…，an-1當作新的序列，調整為堆；(3)重復(1)和(2)，直到所有記錄都調整完為止。8.4選擇排序算法2.建堆的方法(1)將給定序列看成是一棵完全二叉樹；(2)從第i=n/2個節(jié)點開始，與子樹節(jié)點相比較，若直接子節(jié)點中較小者小于節(jié)點i，則交換，直到葉節(jié)點或不再交換；(3)i=i-1，重復(2)直到i=1。8.4選擇排序算法算法8.7調整建堆算法voidCreatheap(RecordTyper[],intm,intn)/*對表r中的結點編號為m到n的元素進行建堆，r[0]為臨時交換空間*/{ inti,j,flag=0; i=m; j=2*i;/*j為i的左孩子*/ r[0]=r[i]; while(j<=n&&flag!=1)/*沿值小的分支篩選*/ { if(j<n&&r[j].key>r[j+1].key) j++;/*選取孩子中值較小的分支*/8.4選擇排序算法 if(r[0].key<r[j].key)flag=1; else{r[i]=r[j];i=j;j=2*i;/*繼續(xù)向下篩選*/r[i]=r[0];} }}8.4選擇排序算法算法8.8堆排序算法voidHeapsort(RecordTypex[],intn)/*對表r中的第1到第n個記錄進行堆排序，r[0]為臨時交換空間*/{ inti; for(i=n/2;i>=1;i--) Creatheap(x,i,n);/*初始化堆*/ printf("Outputx[]:"); /*輸出堆頂元素，并將最后一個元素放到堆頂位置，重新建堆*/

8.4選擇排序算法 for(i=n;i>=1;i--) { printf("%4d",x[1]);/*輸出堆頂元素*/ x[1]=x[i];/*將堆尾元素移至堆頂*/ Creatheap(x,1,i);/*整理堆*/ } printf("\n");}8.4選擇排序算法【例8.7】給出對整數(shù)序列{70，83，100，65，65}進行堆排序的過程。8.4選擇排序算法堆排序對深度為k的堆，篩選進行的比較次數(shù)至多為2(k-1)；對n個關鍵字要建立深度為log2n+1的堆進行的比較的次數(shù)至多為4n；調整堆頂n-1次，總共進行的比較的次數(shù)不超過2(log2n-1+log2n-2+…+log22)<2n(log2n)因此，堆排序的時間復雜度T(n)+O(nlog2n)。空間上只需要一個記錄的輔助空間，因此空間復雜度S(n)+O(1)。堆排序比較適合于排序數(shù)據量大且無序的記錄序列，而不適合于小的記錄序列。堆排序算法是不穩(wěn)定的排序方法。8.5歸并排序算法8.5歸并排序算法歸并排序的基本思想把待排序的記錄序列分成若干個子序列，先將每個子序列的記錄排序，再將已排序的子序列合并，得到完全排序的記錄序列。歸并排序可分為多路歸并排序和兩路歸并排序。這里僅對兩路歸并排序進行討論。兩路歸并排序算法的基本思想對任意長度為n的序列,首先看成是n個長度為1的有序序列，然后兩兩歸并為n/2個有序表；再對n/2個有序表兩兩歸并，直到得到一長度為n的有序表。8.5歸并排序算法給出對整數(shù)序列{70，83，100，65，65}歸并排序的過程。1234570831006565[7083100][6565][7083][100][6565]【70】【83】[100][6565]【7083】【100】[6565]【7083100】[6565]【7083100】【65】【65】【7083100】【6565】【65657083100】8.5歸并排序算法算法8.9二路歸并算法voidMerge(RecordTypea[],RecordTypeb[],inti,intm,intn)//將有序表a[i..m]、a[m+1..n]有序歸并到b[i..m]{intla,lb,lc;la=i;lb=m+1;

lc=i;//序列l(wèi)a,lb,lc的始點

while(la<=m&&lb<=n)

if(a[la].key<a[lb].key)

b[lc++].key=a[la++].key;//有序合并

elseb[lc++].key=a[lb++].key;8.5歸并排序算法while(la<=m)b[lc++].key=a[la++].key;

while(lb<=n)b[lc++].key=a[lb++].key;}

8.5歸并排序算法voidMergesort(RecordTypea[],RecordTypeb[],ints,intt)/*將有序表a[s..t]有序歸并排序到b[s..t]中*/{intm;

RecordTypec[MAXSIZE+1];

if(s==t)b[s].key=a[s].key;else

{m=(s+t)/2;

Mergesort(a,c,s,m);

Mergesort(a,c,m+1,t);

Merge(c,b,s,m,t);}}8.5歸并排序算法由于二路歸并排序算法需要劃分有序段，且遞歸的深度恰好與n個節(jié)點的完全二叉樹的深度相同，每個有序段的長度均不超過n，因此兩個有序段的合并算法時間復雜度不會超過O(n)。對n個記錄進行歸并排序的時間復雜度T(n)=O(