《程序設(shè)計教程：用C++語言編程》PPT-排序

第10章排序煙臺大學計算機學院孟佳娜基本概念

排序：是假設(shè)含n個記錄的序列為{R1,R2,…，Rn}，其相應(yīng)的關(guān)鍵字序列為{K1,K2,…，Kn}，這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系

Ks1≤Ks2≤…≤Ksn，按此固有關(guān)系將n個序列重新排列為{Rs1,Rs2,

…，Rsn}的操作稱作排序?；靖拍罘€(wěn)定的：若Ki為次關(guān)鍵字，則在待排序的記錄序列中可能有多個數(shù)據(jù)元素的關(guān)鍵字值相同。假設(shè)Ki=Kj（i≠j），且在排序前的序列中Ri領(lǐng)先于Rj。經(jīng)過排序后，Ri與Rj的相對次序保持不變（即Ri仍領(lǐng)先于Rj），則稱這種排序方法是穩(wěn)定的，否則稱之為不穩(wěn)定的內(nèi)部排序：若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序外部排序：若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序排序的類型定義#definen待排序記錄的個數(shù)typedef

struct{

int

key;AnyTypeother;∥記錄其他數(shù)據(jù)域}RecType;RecTypeR[n+1];

主要思想：不斷地將待排序的數(shù)值插入到有序序列中，使有序序列逐漸擴大，直至所有數(shù)值都進入有序序列中位置

插入排序插入排序種類：直接插入排序、折半插入排序、二路插入排序、表插入排序和希爾排序

直接插入排序基本思想為：將記錄R[i]插入到有序子序列R[1..i-1]中，使記錄的有序序列從R[1..i-1]變?yōu)镽[1..i]

示例初始關(guān)鍵字序列：[51]33629687172851／i=2(33)

[3351]629687172851／i=3(62)[335162]9687172851／i=4(96)[33516296]87172851／i=5(87)[3351628796]172851／i=6(17)

[173351628796]2851／i=7(28)[17283351628796]51／i=8(51／)[1728335151／628796]直接插入排序算法voidStrInsSort1(RecTypeR[]，intn){∥本算法是利用監(jiān)視哨對R[1..n]進行直接插入排序

for(i=2;i<=n;i++)∥假定第一個記錄有序

{R[0]=R[i];j=i-1;∥將待排序記錄放進監(jiān)視哨

∥從后向前查找插入位置，將大于待排序記錄向后移動

while(R[0].key<R[j].key){R[j+1]=R[j];j--;∥記錄后移

}∥whileR[j+1]=R[0];∥將待排序記錄放到合適位置}∥for}∥StrInsSort1

排序性能最好的情況比較次數(shù)為n－1次移動次數(shù)為2（n－1）次最壞的情況比較次數(shù)為=(n+2)(n-1)/2移動次數(shù)為=(n+4)(n-1)/2結(jié)論：最好情況的時間復雜度為O（n），最壞情況時間復雜度和平均時間復雜度為O（n2）。

折半插入排序主要思想：當?shù)趇個記錄要插入前i－1個有序記錄序列時，可利用折半查找（在查找章節(jié)介紹）方式確定插入位置，已減少比較次數(shù)

時間復雜度：O（n2）

折半插入排序算法voidBinsSort(RecTypeR[]，intn){∥對R[1..n]進行折半插入排序

for(i=2;i<=n;i++)∥假定第一個記錄有序

{R[0]=R[i];∥將待排記錄R[i]暫存到R[0]low=1;high=i-1;∥設(shè)置折半查找的范圍

∥在R[low..high]中折半查找有序插入位置

while(low<=high){m=(low+high)/2;∥折半if(R[0].key<R[m].key)high=m-1;∥插入點在低半?yún)^(qū)

elselow=m+1;∥插入點在高半?yún)^(qū)}∥while

for(j=i-1;j>=high+1;j--)R[j+1]=R[j];∥記錄后移

R[high+1]=R[0];∥插入}∥for}∥BinsSort

二路插入排序基本思想：另設(shè)一數(shù)組d，將R[1]賦值給d[1]，并將d[1]看作排好序的中間記錄，從第二個記錄起依次將關(guān)鍵字小于d[1]的記錄插入d[1]之前的有序序列，將關(guān)鍵字大于d[1]的記錄插入d[1]之后的有序序列?？山柚鷥蓚€變量first和final來指示排序過程中有序序列第一個記錄和最后一個記錄在d中的位置。

二路插入排序初始關(guān)鍵字序列：5133629687172851／

排序中數(shù)組d的狀態(tài)：i=1[51]fist↑↑finali=2[51]

[33]↑final

↑fisti=3[5162]

[33]

final↑

↑fisti=4[516296]

[33]

final↑

↑fisti=5[51628796]

[33]

final↑↑fisti=6[51628796][1733]final↑↑fisti=7[51628796][172833]final↑

↑fisti=8[5151／628796172833]

final↑

↑fist表插入排序基本思想：為了減少在排序過程中進行的“移動”記錄的操作，必須改變排序過程中采用的存儲結(jié)構(gòu)。利用靜態(tài)鏈表進行排序，并在排序完成之后，一次性地調(diào)整各個記錄相互之間的位置，即將每個記錄都調(diào)整到它們所應(yīng)該在的位置上。

時間復雜度：O（n2）。

表插入排序示例

012345678關(guān)鍵字MAXINT5133629687172851／指針初值10

i=2201

i=32310

i=423140

i=5231504

i=66315042

i=763150472

指針終值681504723希爾排序基本思想：將待排序的記錄劃分成幾組，從而減少參與直接插入排序的數(shù)據(jù)量，當經(jīng)過幾次分組排序后，記錄的排列已經(jīng)基本有序，這個時候再對所有的記錄實施直接插入排序。希爾排序示例二趟排序結(jié)果：171051／33285152629687三趟排序結(jié)果：1017283351／5152628796

初始關(guān)鍵字序列：5133629687172851／5210

一趟排序結(jié)果：172851／52105133629687希爾排序算法voidShellSort(RecTypeR[]，intn){∥以步長di/2分組的希爾排序，第一個步長取n/2，最后一個取1for(d=n/2;d>=1;d=d/2) {for(i=1+d;i<=n;i++)

∥將R[i]插入到所屬組的有序列段中 {R[0]=R[i];j=i-d;

while(j>0&&R[0].key<R[j].key) {R[j+d]=R[j];j=j-d;}∥while

R[j+d]=R[0];∥將第i個元素插入到合適位置}∥for}∥for}∥ShellSort

交換排序主要思路：在排序過程中，通過對待排序記錄序列中元素間關(guān)鍵字的比較，發(fā)現(xiàn)次序相反的，即將存儲位置交換來達到排序目的

交換排序種類：起泡排序和快速排序起泡排序基本思想：對所有相鄰記錄的關(guān)鍵字值進行比效，如果是逆順（a[j]>a[j+1]），則將其交換，最終達到有序化

起泡排序示例初始關(guān)鍵字序列：5133629687172851／第一趟排序結(jié)果：33516287172851／[96]第二趟排序結(jié)果：335162172851／[8796]第三趟排序結(jié)果：3351172851／[628796]第四趟排序結(jié)果：33172851[51／628796]第五趟排序結(jié)果：172833[5151／628796]第六趟排序結(jié)果：[1728335151／628796]起泡排序算法voidBubbleSort(RecTypeR[]，intn){∥對R[1..n]進行起泡排序

for(i=1；i<n；i++)∥最多n-1趟起泡{for(j=1;j<=n-i;j++)

if（R[j].key>R[j+1].key）{temp=R[j]；R[j]=R[j+1]；

R[j+1]=temp；∥逆序時交換}∥if}∥for}∥BubbleSort

在正序時，比較次數(shù)為n－1，交換次數(shù)為0；逆序時，比較次數(shù)和交換次數(shù)均為=（n-1）,

記錄的移動次數(shù)為n(n-1)，因此總的時間復雜度為O（n2）

快速排序基本思想：首先將待排序記錄序列中的所有記錄作為當前待排序區(qū)域，從中任選取一個記錄（通?？蛇x第一個記錄），以它的關(guān)鍵字作為樞軸（或支點）（pivot），凡其關(guān)鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關(guān)鍵字大于樞軸的記錄均移動至該記錄之后快速排序示例初始關(guān)鍵字序列：[51]33629687172851／R[0]=[51]

i↑(樞軸)↑jj向前掃描

i↑

↑j第一次交換之后：283362968717[]51／

i↑

↑ji向后掃描

i↑

↑j第二次交換之后：2833[]9687176251／

i↑

↑jj向前掃描i↑

↑j第三次交換之后：2833179687[]6251／i向后掃描i↑

↑j第四次交換之后：283317[]87966251／j向前掃描i↑↑j完成一趟排序：283317[51]87966251／

i↑↑j（a一趟快速排序過程）快速排序示例初始關(guān)鍵字序列：5133629687172851／一趟排序之后：[283317]

51

[87966251／]分別進行快速排序：[17]

28

[33]

結(jié)束結(jié)束[51／62]

87

[96]

51／

[62]

結(jié)束

結(jié)束有序序列：1728335151／628796（b快速排序全過程）快速排序算法int

Partition(RecTypeR[]，intl，inth){∥交換記錄子序列R[l..h]中的記錄，使樞軸記錄到位并返回其所在位置，∥此時，在它之前（后）的記錄均不大（?。┯谒黫nti=l;j=h;∥用變量i,j記錄待排序記錄首尾位置

R[0]=R[i];∥以子表的第一個記錄作樞軸，將其暫存到記錄R[0]中

x=R[i].key;∥用變量x存放樞軸記錄的關(guān)鍵字

while(i<j){∥從表的兩端交替地向中間掃描

while(i<j&&R[j].key>=x)j--;R[i]=R[j];∥將比樞軸小的記錄移到低端

while(i<j&&R[i].key<=x)i++;R[j]=R[i];∥將比樞軸大的記錄移到高端}∥whileR[i]=R[0];∥樞軸記錄到位

returni;∥返回樞軸位置}∥Partition

快速排序算法voidQuickSort(RecTypeR[]，ints，intt){∥對記錄序列R[s..t]進行快速排序

if(s<t){k=Partition(R,s,t);QuickSort(R,s,k-1);QuickSort(R,k+1,t);}∥if}∥QuickSort

快速排序的平均時間復雜度為O（nlog2n）

選擇排序基本思想：依次從待排序記錄序列中選擇出關(guān)鍵字值最?。ɑ蜃畲螅┑挠涗?、關(guān)鍵字值次之的記錄、……，并分別將它們定位到序列左側(cè)（或右側(cè)）的第1個位置、第二個位置、……，從而使待排序的記錄序列成為按關(guān)鍵字值由小到大（或由大到小）排列的有序序列。

選擇排序種類：直接選擇排序，樹形選擇排序和堆排序

直接選擇排序待排記錄序列的狀態(tài)為：有序序列R[1..i-1]無序序列R[i..n]

并且有序序列中所有記錄的關(guān)鍵字均小于無序序列中記錄的關(guān)鍵字，則第i趟直接選擇排序是，從無序序列R[i..n]的n-i+1記錄中選出關(guān)鍵字最小的記錄加入有序序列

直接選擇排序示例初始關(guān)鍵字序列：5133629687172851／

↑↑第一趟排序后：[17]33629687512851／↑↑第二趟排序后：[1728]

629687513351／↑↑第三趟排序后：[1728

33]

9687516251／第四趟排序后：[1728

3351]

87966251／第五趟排序后：[1728

3351

51／]966287第六趟排序后：[1728

3351

51／

62]

9687第七趟排序后：[1728

3351

51／

62

87

96]直接選擇排序算法voidSelectSort(RecTypeR[]，intn){∥對記錄序列R[1..n]作直接選擇排序。

for(i=1;i<n;i++){∥選擇第i小的記錄，并交換到位k=i;∥假定第i個元素的關(guān)鍵字最小

for(j=i+1;j<=n;j++)∥找最小元素的下標

if(R[j].key<R[k].key)k=j;if(i!=k)R[i]←→R[k];∥與第i個記錄交換}∥for}∥SelectSort

直接選擇排序的平均時間復雜度為O（n2）

樹形選擇排序基本思想：首先對n個待排序記錄的關(guān)鍵字進行兩兩比較，從中選出n/2個較小者再兩兩比較，直到選出關(guān)鍵字最小的記錄為止，此為一趟排序。我們將一趟選出的關(guān)鍵字最小的記錄稱為“冠軍”，而“亞軍”是從與“冠軍”比較失敗的記錄中找出，具體做法為：輸出“冠軍”后，將其葉子結(jié)點關(guān)鍵字改為最大，繼續(xù)進行錦標賽排序，直到選出關(guān)鍵字次小的記錄為止，如此循環(huán)直到輸出全部有序序列

樹型選擇排序示例時間復雜度為O（nlog2n）

堆的定義：堆是滿足下列性質(zhì)的數(shù)列{K1,K2,…,Kn}：

堆排序或（i=1,2,…,

n/2）

若上述數(shù)列是堆，則K1必是數(shù)列中的最小值或最大值，分別稱作小頂堆或大頂堆（小堆或大堆）。

96，51，87，33，28，62，51／，17是大頂堆

例如：17，28，51，33，62，96，87，51／是小頂堆堆排序示例建立二叉樹基本思想：先建一個堆，即先選得一個關(guān)鍵字最大或最小的記錄，然后與序列中最后一個記錄交換，之后將序列中前n－1記錄重新調(diào)整為一個堆（調(diào)堆的過程稱為“篩選”），再將堆頂記錄和第n－1個記錄交換，如此反復直至排序結(jié)束。

調(diào)整堆示例2851336287961751(a)堆2851336287965117(b)17與51／交換后的情景調(diào)整堆示例5151876228963317(d)28與87交換后調(diào)成的新堆3351516287962817(c)調(diào)整后的新堆建堆示例初始關(guān)鍵字序列：51，33，62，96，87，17，28，51／為例，其初始建大頂堆過程

3362968728175151(a)4..8是堆，不調(diào)整3362968728175151(b)3..8是堆，不調(diào)整建堆示例3362968728175151(c)2..8不是堆，進行篩選9662518728175133(d)1..8不是堆，進行篩選建堆示例8762515128179633(e)建成的大頂堆堆排序算法voidSift(RecTypeR[]，inti，intm){∥假設(shè)R[i+1..m]中各元素滿足堆的定義，本算法調(diào)整R[i]使序列∥R[i..m]中各元素滿足堆的性質(zhì)R[0]=R[i];∥暫存“根”記錄R[i]for(j=2*i;j<=m;j*=2)∥j<=m時，R[2i]是R[i]的左孩子{∥若R[i]的右孩子存在，且關(guān)鍵字大于左孩子，j指向R[i]的右孩子if(j<m&&R[j].key<R[j+l].key)j++;if(R[0].key<R[j].key)∥孩子結(jié)點關(guān)鍵字較大{R[i]=R[j];∥將R[j]換到雙親位置上

i=j;∥修改當前被調(diào)整結(jié)點}

elsebreak;∥調(diào)整完畢，退出循環(huán)

}∥forR[i]=R[0];∥最初被調(diào)整結(jié)點放入正確位置}∥Sift

堆排序算法voidHeapSort(RecTypeR[]，intn){∥對記錄序列R[1..n]進行堆排序。

for(i=n/2;i>0;i--)∥把R[1..n]建成大頂堆

Sift(R,i,n);

for(i=n;i>1;i--){∥將堆頂記錄和當前未經(jīng)排序子序列R[1..i]中最后一個記

∥錄相互交換

R[1]←→R[i];Sift(R,1,i-1);

∥將R[1..i-1]重新調(diào)整為大頂堆}∥for}∥HeapSort

堆排序的時間復雜度為O（nlog2n）

歸并排序基本思想：將一個具有n個待排序記錄的序列看成是n個長度為1的有序列，然后進行兩兩歸并，得到「n/2個長度為2的有序序列，再進行兩兩歸并，得到「n/4個長度為4的有序序列，如此重復，直至得到一個長度為n的有序序列為止

歸并排序示例二趟歸并排序后：[33516296]

[1728

87]

初始關(guān)鍵字序列：[51]

[33]

[62]

[96]

[87]

[17]

[28]

一趟歸并排序后：[3351]

[6296]

[1787]

[28]

三趟歸并排序后：[17

28335162

8796]歸并排序算法voidMerge(RecTypeR[],RecTypeR1[],inti,intl,inth){∥將有序的R[i..l]和R[l+1..h]歸并為有序的R1[i..h]

for(j=l+1,k=i;i<=l&&j<=h;k++){∥將R中記錄由小到大地并入R1if(R[i].key<=R[j].key)R1[k]=R[i++];elseR1[k]=R[j++];}∥forif(i<=l)R1[k..h]=R[i..l];∥將剩余的R[i..l]復制到R1

if(j<=h)R1[k..h]=R[j..h];

∥將剩余的R[j..h]復制到R1}∥Merge歸并排序算法voidMsort(RecTypeR[],RecTypeR1[],ints,intt){∥將R[s..t]進行2-路歸并排序為R1[s..t]if(s==t)R1[s]=R[s];

else{m=(s+t)/2;∥將R[s..t]平分為R[s..m]和R[m+1..t]Msort(R,R2,s,m);∥遞歸地將R[s..m]歸并為有序的R2[s..m]Msort(R,R2,m+1,t);

∥遞歸地R[m+1..t]歸并為有序的R2[m+1..t]Merge(R2,R1,s,m,t);

∥將R2[s..m]和R2[m+1..t]歸并到R1[s..t]}∥if}∥MSort

voidMergeSort(RecTypeR[],intn){∥對記錄序列R[1..n]作2-路歸并排序。

MSort(R,R,1,n);}∥MergeSort

二路歸并排序的時間復雜度為O（nlog2n），所需空間為O（n）

分配排序基本思想：利用關(guān)鍵字的結(jié)構(gòu)，通過“分配”和“收集”的辦法來實現(xiàn)排序

分配排序可分為桶排序和基數(shù)排序兩類

桶排序桶排序（BucketSort）也稱箱排序（BinSort），其基本思想是：設(shè)置若干個桶，依次掃描待排序記錄R[1..n]，把關(guān)鍵字等于k的記錄全部都裝到第k個桶里（分配），然后，按序號依次將各非空的桶首尾連接起來（收集）。

基數(shù)排序基數(shù)排序就是一種借助“多關(guān)鍵字排序”的思想來實現(xiàn)“單關(guān)鍵字排序”的算法。假設(shè)有n個記錄待排序序列{R1,R2,…，Rn}，每個記錄Ri中含有d個關(guān)鍵字(Ki0,Ki1,

…,Kid-1),則稱上述記錄序列對關(guān)鍵字(Ki0,Ki1,

…,Kid-1)有序是指：對于序列中任意兩個記錄Ri和Rj(1≤i<j≤n)都滿足下列(詞典)有序關(guān)系：(Ki0,Ki1,

…,Kid-1)<(Kj0,Kj1,

…,Kjd-1)其中K0被稱為“最主”位關(guān)鍵字，Kd-1被稱為

“最次”位關(guān)鍵字。實現(xiàn)多關(guān)鍵字排序通常有兩種作法:最高位優(yōu)先MSD法：先對K0進行排序，并按K0的不同值將記錄序列分成若干子序列之后，分別對K1進行排序，…，依次類推，直至最后對最次位關(guān)鍵字排序完成為止。最低位優(yōu)先LSD法：先對Kd-1進行排序，然后對Kd-2進行排序，依次類推，直至對最主位關(guān)鍵字K0排序完成為止。排序過程中不需要根據(jù)“前一個”關(guān)鍵字的排序結(jié)果，將記錄序列分割成若干個(“前一個”關(guān)鍵字不同的)子序列。

基數(shù)排序示例p→369→367→167→239→237→138→230→139第一次分配得到B[0].f→230←B[0].eB[7].f→367→167→237←B[7].eB[8].f→138←B[8].eB[9].f→369→239→139←B[9].e第一次收集得到p→230→367→167→237→138→369→239→139基數(shù)排序示例第二次分配得到B[3].f→230→237→138→239→139←B[3].eB[6].f→367→167→369←B[6].e第二次收集得到p→230→237→138→239→139→367→167→369基數(shù)排序示例第三次分配得到B[1].f→138→139→167←B[1].eB[2].f→230→237→239←B[2].eB[3].f→367→369←B[3].e第三次收集之后便得到記錄的有序序列p→138→139→167→230→237→239→367→369

內(nèi)部排序方法的比較排序方法平均時間最壞情況輔助空間穩(wěn)定性直接插入排序O（n2）O（n2）O（1）穩(wěn)定折半插入排序O（n2）O（n2）O（1）穩(wěn)定二路插入排序O（n2）O（n2）O（n）穩(wěn)定表插入排序O（n2）O（n2）O（1）穩(wěn)定起泡排序O（n2）O（n2）O（1）穩(wěn)定直接選擇排序O（n2）O（n2）O（1）不穩(wěn)定希爾排序O（n1.3）O（n1.3）O（1）不穩(wěn)定快速排序O（nlog2n）O（n2）O（log2n）不穩(wěn)定堆排序O（nlog2n）O（nlog2n）O（1）不穩(wěn)定2-路歸并排序O（nlog2n）O（nlog2n）O（n）穩(wěn)定基數(shù)排序O(d*(rd+n))O(d*(rd+n))O(rd)穩(wěn)定外部排序外部排序也叫文件排序，通常的方法是合并，經(jīng)兩個獨立的階段而完成。第一階段，根據(jù)內(nèi)存大小，每次把文件中一部分記錄讀入內(nèi)存，用有效的內(nèi)部排序方法（如快速排序、堆排序等）將其排成有序段，有序段又稱歸并段或順串。每產(chǎn)生一個順串，就把它寫回外存。這一階段稱初始順串生成階段。第二階段是歸并階段，每次讀入一些順串到內(nèi)存中，通過合并操作，將它們合并成更長的順串。

外部排序外部排序所需總時間T=m*tI

+d*tI/O+s*ntm其中tI是構(gòu)造一個初始歸并段所需內(nèi)部排序的平均時間；tI/O是進行一次外存讀/寫的平均時間；tm是對一個記錄進行內(nèi)部歸并所需時間；n為記錄個數(shù)；