中山大學-數(shù)據(jù)結(jié)構-內(nèi)部排序

第十章內(nèi)部排序?qū)W習目標理解排序的定義和各種排序方法的特點，并能加以靈活應用。排序方法有不同的分類方法，基于“關鍵字間的比較”進行排序的方法可以按排序過程所依據(jù)的不同原則分為插入排序、快速（交換）排序、選擇排序、歸并排序和基數(shù)排序等五類。掌握各種排序方法的時間復雜度的分析方法。能從“關鍵字間的比較次數(shù)”分析排序算法的平均情況和最壞情況的時間性能。按平均時間復雜度劃分，內(nèi)部排序可分為三類：O(n2)的簡單排序方法，O(n·logn)的高效排序方法和O(d·n)的基數(shù)排序方法。理解排序方法“穩(wěn)定”或“不穩(wěn)定”的含義。2/3/20231重點和難點重點：希爾排序、快速排序、堆排序和歸并排序等高效方法難點：希爾排序、快速排序、堆排序和歸并排序等高效方法知識點排序、直接插入排序、折半插入排序、表插入排序、希爾排序、起泡排序、快速排序、簡單選擇排序、堆排序、2-路歸并排序、基數(shù)排序、排序方法的綜合比較。2/3/2023210.1概述排序假設含有n個記錄的序列為：{R1，R2，…，Rn}，

它們的關鍵字相應為{K1，K2，…，Kn}，

對記錄序列進行排序就是要確定序號1，2，…，n的一種排列P1，P2，…，Pn，使其相應的關鍵字滿足如下的非遞減（或非遞增）的關系：

Kp1<=Kp2<=…<=Kpn

使序列成為一個按關鍵字有序的序列

{Rp1，Rp2，…，Rpn}目的利用高效的查找方法，以提高查找效率。2/3/20233排序分類按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存。外部排序：排序過程中需對外存進行訪問的排序。按排序依據(jù)原則插入排序：直接插入排序、折半插入排序、希爾排序?？焖伲ń粨Q）排序：冒泡排序、快速排序。選擇排序：簡單選擇排序、堆排序。歸并排序：2-路歸并排序?；鶖?shù)排序2/3/20234穩(wěn)定若待排序文件中有關鍵字相等的記錄，排序后，其前后相對次序與排序前未發(fā)生變化，這種排序稱為“穩(wěn)定”排序；否則是“不穩(wěn)定”排序。穩(wěn)定排序與不穩(wěn)定排序只是表示所用的排序方法，并不說明哪種方法好與差。排序基本操作比較兩個關鍵字大??；將記錄從一個位置移動到另一個位置；就全面性能而言，很難提出一種被認為最好的方法，每種方法均有優(yōu)點和適用環(huán)境。2/3/20235本章討論中，待排記錄如下結(jié)構。#defineMAXSIZE20; //假設的順序表最大長度

typeint

KeyType; //定義關鍵字類型為整數(shù)類型typedef

struct{

KeyTypekey;

//關鍵字項

InfoType

otherinfo;

//其它數(shù)據(jù)項

}RcdType; //記錄類型typedef

struct{

RcdTyper[MAXSIZE+1];

//r[0]閑置或作為判別標志的“哨兵”單元

intlength;

//順序表長度

}SqList； //順序表類型2/3/2023610.2插入排序10.2.1直接插入排序基本思想整個排序過程為n-1趟插入，即先將序列中第1個記錄看成是一個有序子序列，然后從第2個記錄開始，逐個進行插入，直至整個序列有序。2/3/2023749386597761327i=2(49)386597761327i=3(3849)6597761327i=4

(384965)97761327i=5

(38496597)761327i=6

(3849657697)1327i=1()i=7(133849657697)2727977665493827(13273849657697)排序結(jié)果：383849659797769776137665493813))))))))))))監(jiān)視哨r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]穩(wěn)定的排序方法2/3/20238voidInsertSort(SqList&L){

//對順序表L作直接插入排序

for(i=2;i<=L.length;++i)

if(LT(L.r[i].key,L.r[i-1].key)){

//將L.r[i]插入有序子表

L.r[0]=L.r[i]; //哨兵

for(j=i-1;LT(L.r[0].key,L.r[j].key;--j)

L.r[j+1]=L.r[j];

//記錄后移

L.r[j+1]=L.r[0];

//插入到正確位置

}//if

}//InsertSort直接插入排序的算法1

2

3

4

5

6

7

8時間復雜度T(n)=O(n2)2/3/20239算法評價時間復雜度若待排序記錄按關鍵字從小到大排列(正序)

關鍵字比較次數(shù)：若待排序記錄按關鍵字從大到小排列(逆序)

關鍵字比較次數(shù)：記錄移動次數(shù)：2/3/202310若待排序記錄是隨機的，取平均值。關鍵字比較次數(shù)：記錄移動次數(shù)：空間復雜度S(n)=O(1)2/3/20231110.2.2其它插入排序折半插入排序基本思想用折半查找方法確定插入位置的排序。i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…i=820(6133039427085)20ihi=820(613203039427085)hmimhm插入位置2/3/202312voidBInsertSort(SqList&L){

//對順序表L作折半插入排序

for(i=2;i<=L.length;++i){ L.r[0]=L.r[i];

//將L.r[i]暫存到L.r[0] low=1;high=i-1; while(low<=high){

//在r[low..high]中折半查找有序插入的位置

m=(low+high)/2;

//折半

if(LT(L.r[0].key，L.r[m].key))high=m-1;

//插入點在低半?yún)^(qū)

elselow=m+1;

//插入點在高半?yún)^(qū)

}//whilefor(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//記錄后移

L.r[high+1]=L.r[0];

//插入

}}//BInsertSort時間復雜度：T(n)=O(n2)2/3/202313算法評價時間復雜度：T(n)=O(n2)空間復雜度：S(n)=O(1)折半插入排序只能減少排序過程中關鍵字比較的時間，并不能減少記錄移動的時間。2/3/2023142-路插入排序基本思想

另設一個和L.r同類型的數(shù)組d，首先將L.r[1]賦給d[1]，并將d[1]看成是在排好序的序列中處于中間位置的記錄，然后從L.r中第2個記錄起依次插入到d[1]之前或之后的有序序列中。目的對折半插入排序的改進，減少記錄的移動次數(shù)。2/3/202315初始關鍵字4938659776132749i=1(49)firstfinali=2(49)(38)firstfinali=3(4965)(38)firstfinali=4(496597)(38)firstfinal2/3/202316初始關鍵字4938659776132749i=4(496597)(38)firstfinali=5(49657697)(38)firstfinali=6(49657697)(1338)firstfinali=7(49657697)(132738)firstfinal2/3/202317初始關鍵字4938659776132749i=7(49657697)(132738)firstfinali=8firstfinal(4949657697)(132738)

2路插入排序的移動記錄次數(shù)減少了，約為n2/8，但不能避免移動。2/3/20231810.2.3希爾(shell)排序基本思想是對插入排序的一個改進，也稱縮小增量排序。先將整個待排序記錄序列分割成若干個子序列，分別對這些子序列進行直接插入排序；待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。排序過程取一個正整數(shù)d1<n，把所有相隔d1的記錄放一組，組內(nèi)進行直接插入排序；然后取d2<d1，重復上述分組和排序操作；直至di=1，即所有記錄放進一個組中排序為止。2/3/202319初始關鍵字：49,38,65,97,76,13,27,49,55,4取d3=1三趟分組：三趟排序結(jié)果：一趟排序結(jié)果：二趟排序結(jié)果：取d1=5一趟分組：取d2=3二趟分組：493865977613274955413274955449386597761327495544938659776134493827495565977613449382749556597764132738494955657697不穩(wěn)定的排序方法2/3/202320一趟希爾排序算法10.4voidShellInsert(SqList&L，int

dk){

//對順序表L作一趟希爾插入排序。本算法是和一趟直接插入排序

//相比，作了如下修改：1.前后記錄位置的增量是dk，不是1；

//2.r[0]只是暫存單元，不是哨兵。當j<=0時，插入位置已找到。

for(i=dk+1;i<=L.length;++i) if(LT(L.r[i].key,L.r[i-dk].key)){

//需將L.r[i]插入有序增量子表

L.r[0]=L.r[i];for(j=i-dk;j>0&<(L.r[0].key,L.r[j].key);j-=dk)

L.r[j+dk]=L.r[j];//記錄后移，查找插入位置

L.r[j+dk]=L.r[0];

//插入

}//if}//ShellInsert2/3/202321希爾排序的算法10.5voidShellSort(SqList&L,int

dlta[],intt){

//按增量序列dlta[0..t-1]對順序表L作希爾排序

for(k=0;k<t;++t) //一趟增量為dlta[k]的插入排序

ShellInsert(L,dlta[k]);}//ShellSort希爾排序的時間復雜度和所取增量序列相關，例如已有學者證明，當增量序列為2t-k-1(k=0,1,…，t-1)時，希爾排序的時間復雜度為O(n3/2)。2/3/202322希爾排序特點子序列的構成不是簡單的“逐段分割”，而是將相隔某個增量的記錄組成一個子序列。希爾排序可提高排序速度，因為分組后n值減小，n2更小，而T(n)=O(n2),所以T(n)從總體上看是減小了；關鍵字較小的記錄跳躍式前移，在進行最后一趟增量為1的插入排序時，序列已基本有序。增量序列取法無除1以外的公因子；最后一個增量值必須為1；如……,9,5,3,2,1或……,31,15,7,3,1或……,40,13,4,1等。2/3/20232310.3交換排序起泡排序排序過程將第一個記錄的關鍵字與第二個記錄的關鍵字進行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止——第一趟冒泡排序，結(jié)果關鍵字最大的記錄被安置在最后一個記錄上。對前n-1個記錄進行第二趟冒泡排序，結(jié)果使關鍵字次大的記錄被安置在第n-1個記錄位置重復上述過程，直到“在一趟排序過程中沒有進行過交換記錄的操作”為止。2/3/202324381327

4949第四趟后49384913273065第三趟后4938496513273076第二趟后493849657613273097第一趟后494938659776132749初始關鍵字132738

49第五趟后497697139727979713767627136527656513134949273827383849497649132738第六趟后時間復雜度最好情況（正序）比較次數(shù)：n-1

移動次數(shù)：0最壞情況（逆序）

比較次數(shù)：空間復雜度：S(n)=O(1)移動次數(shù)：為什么是比較次數(shù)的3倍？2/3/202325快速排序?qū)ζ鹋莘ǖ囊环N改進?；舅枷胪ㄟ^一趟排序，將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄進行排序，以達到整個序列有序。2/3/202326排序過程對r[s……t]中記錄進行一趟快速排序，附設兩個指針i和j，設樞軸記錄rp=r[s]，x=rp.key，初始時令i=s,j=t；首先，從j所指位置向前搜索第一個關鍵字小于x的記錄，并和rp交換；再從i所指位置起向后搜索，找到第一個關鍵字大于x的記錄，和rp交換；重復上述兩步，直至i==j為止；再分別對兩個子序列進行快速排序，直到每個子序列只含有一個記錄為止。2/3/202327493865977613274927i初始關鍵字：jx49jii65j13i97jj494938659776132749初始關鍵字：完成一趟排序：2738134976976549一次劃分后：(273813)49(76976549)分別進行快速排序：(13)

27

(38)

49(4965)

76(97)

(13)

27

(38)

49

49(65)

76(97)快速排序結(jié)束：13

27

3849

4965

76

97不穩(wěn)定的排序方法2/3/202328一趟快速排序的算法10.6intPartition(SqList&L,intlow,inthigh){

//交換順序表L中子表r[low..high]中的記錄，樞軸記錄到位，并返回

//其所在位置，此時，在它之前（后）的記錄均不大（小）于它。

L.r[0]=L.r[low];

//用子表的第一個記錄作樞軸記錄

pivotkey=L.r[low].key;

//樞軸記錄關鍵字

while(low<high){

//從表的兩端交替地向中間掃描

while(low<high&&L.r[high].key>=pivotkey)--high;

L.r[low++]=L.r[high];

//將比樞軸記錄小的記錄移到低端

while(low<high&&L.r[low].key<=pivotkey)

++low;

L.r[high]=L.r[low];

//將比樞軸記錄大的記錄移到高端

}//while L.r[low]=L.r[0];

//樞軸記錄到位

returnlow;

//返回樞軸位置}//Partition2/3/202329快速排序算法10.7和10.8voidQsort(SqList&L,intlow,inthigh){

//對順序表L中的子序列L.r[low…h(huán)igh]作快速排序

if(low<high){ //長度大于1

pivotloc=Partition(L,low,high); //將L.r[low…h(huán)igh]劃分

Qsort(L,low,pivotloc-1); //對低子表排序

Qsort(L,pivotloc+1,high); //對高子表排序

}}//QsortvoidQuickSort(SqList&L){

//對順序表L作快速排序

Qsort(L,1,L.length);}//QuickSort時間復雜度T(n)=O(n2)2/3/202330算法分析時間復雜度最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n2)為防止最差情況的出現(xiàn)，一般采取“三者取中”法來確定樞軸。即在第一個記錄和最后一個記錄，以及中間位置的記錄中，選取值為中間的那個來作樞軸，這樣就能防止最差情況的出現(xiàn)?？臻g復雜度：需?？臻g以實現(xiàn)遞歸最壞情況：S(n)=O(n)一般情況：S(n)=O(log2n)對隨機的關鍵字序列，快速排序是目前被認為是最好的排序方法。2/3/20233110.4選擇排序基本思想每一趟在n-i+1（i=1,2,…,n-1）個記錄中選取關鍵字最小的記錄，并將它和第i個記錄進行互換，從而使其成為有序序列中第i個記錄。10.4.1簡單選擇排序排序過程首先，通過n-1次關鍵字比較，從n個記錄中找出關鍵字最小的記錄，將它與第一個記錄交換；再通過n-2次比較，從剩余的n-1個記錄中找出關鍵字次小的記錄，將它與第二個記錄交換；重復上述操作，共進行n-1趟排序后，排序結(jié)束。2/3/202332

13(38659776492749)初始：(4938659776132749)i=11349i=22738i=3i=4i=5i=61327(659776493849)3865132738(9776496549)499713273849(76976549)49761327384976(9765)49766597132738497697(97)497665767697排序結(jié)束13273849769765()497676976576穩(wěn)定的排序方法2/3/202333簡單選擇排序算法10.9voidSelectSort(SqList&L){

//對順序表L作簡單選擇排序

for(i=1;i<L.length;++i){

//選擇第i小的記錄，并交換到位

j=i; for(k=i+1;k<=L.length;k++)

//在L.r[i..L.length]中選擇關鍵字最小的記錄

if(LT(L.r[k].key,L.r[j].key))j=k; if(i!=j)L.r[j]L.r[i];

//與第i個記錄互換

}//for}//SelectSort時間復雜度T(n)=O(n2)2/3/202334算法評價時間復雜度記錄移動次數(shù)最好情況：0最壞情況：3(n-1)比較次數(shù)：空間復雜度：S(n)=O(1)2/3/20233510.4.3堆排序堆的定義n個元素的序列(k1,k2,……kn)，當且僅當滿足下列關系時，稱之為堆?；蛉魧⒋诵蛄袑囊痪S數(shù)組看成是一個完全二叉樹，則ki為二叉樹的根結(jié)點，k2i和k2i+1分別為ki的“左子樹根”和“右子樹根”。2/3/202336（96，83，27，38，11，9）（13，38，27，50，76，65，49，97）962791138831327384965765097大頂堆小頂堆2/3/202337堆排序?qū)o序序列建成一個堆，得到關鍵字最?。ɑ蜃畲螅┑挠涗?；輸出堆頂?shù)淖钚。ù螅┲岛螅故Ｓ嗟膎-1個元素重又建成一個堆，則可得到n個元素的次小值；重復執(zhí)行，得到一個有序序列的過程。堆排序需解決的兩個問題：如何由一個無序序列建成一個堆？(初始建堆)如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個新的堆？2/3/202338第二個問題解決方法——篩選（以小頂堆為例）輸出堆頂元素之后，以堆中最后一個元素替代之；然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較，并與其中小者進行交換；重復上述操作，直至葉子結(jié)點，將得到新的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選”。2/3/20233913273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13,273849502765769713輸出：13,276549502738769713輸出：13,27,382/3/2023404965502738769713輸出：13,27,387665502738499713輸出：13,27,38,495065762738499713輸出：13,27,38,499765762738495013輸出：13,27,38,49,506597762738495013輸出：13,27,38,49,509765762738495013輸出：13,27,38,49,50,652/3/2023417665972738495013輸出：13,27,38,49,50,659765762738495013輸出：13,27,38,49,50,65,769765762738495013輸出：13,27,38,49,50,65,76,972/3/202342篩選算法10.10voidHeapAdjust(SqList&H,ints,intm){

//已知H.r[s..m]中記錄的關鍵字除H.r[s].key之外均滿足堆的定義，//本函數(shù)調(diào)整H.r[s]的關鍵字，使H.r[s..m]成為一個大頂堆（對其中

//記錄的關鍵字而言）

rc=H.r[s];

//暫存根結(jié)點的記錄

for(j=2*s;j<=m;j*=2){

//沿關鍵字較大的孩子結(jié)點向下篩選

if(j<m&<(H.r[j].key,H.r[j+1].key))++j;

//j為關鍵字較大的孩子記錄的下標

if(!LT(rc.key,H.r[j].key))break;

//不需要調(diào)整，跳出循環(huán)

H.r[s]=H.r[j];s=j;//將大關鍵字記錄往上調(diào)

}//for H.r[s]=rc;

//回移篩選下來的記錄}//HeapAdjust若改為小頂堆，該如何修改語句？j<m&<(H.r[j+1].key,H.r[j].key)LT(rc.key,H.r[j].key)2/3/202343第一個問題解決方法從無序序列的第n/2個元素（即此無序序列對應的完全二叉樹的最后一個非終端結(jié)點）起，至第一個元素止，進行反復篩選。496538271376975049653827137650974913382765765097例如：含8個元素的無序序列（49，38，65，97，76，13，27，50）2/3/20234449133827657650971327384965765097496538271376975049653827137650974913382765765097例如：含8個元素的無序序列（49，38，65，97，76，13，27，50）2/3/202345堆排序算法10.11voidHeapSort(SqList&H){

//對順序表H進行堆排序

for(i=H.length/2;i>0;--i)

//將H.r[1..H.length]建成大頂堆

HeapAdjust(H,i,H.length); for(i=H.length;i>1;--i){

H.r[1]H.r[i]; //將堆頂記錄和當前未經(jīng)排

//序的子序列H.r[1..i]中最

//后一個記錄互相交換

HeapAdjust(H,1,i-1); //將H.r[1..i-1]重新調(diào)整為

//大頂堆

}//for}//HeapSort2/3/202346算法評價時間復雜度：最壞情況下T(n)=O(nlogn)篩選算法：最多從第1層篩到最底層，為完全二叉樹的深度

log2n+1;初始建堆：調(diào)用篩選算法n/2次；重建堆：調(diào)用篩選算法n-1次?？臻g復雜度：S(n)=O(1)記錄較少時，不提倡使用。不穩(wěn)定的排序方法2/3/20234710.5歸并排序歸并將兩個或兩個以上的有序表組合成一個新的有序表。2-路歸并排序排序過程設初始序列含有n個記錄，則可看成n個有序的子序列，每個子序列長度為1；兩兩合并，得到n/2個長度為2或1的有序子序列；再兩兩合并，……如此重復，直至得到一個長度為n的有序序列為止。2/3/202348初始關鍵字：[49][38][65][97][76][13][27]一趟歸并后：[3849][6597][1376][27]二趟歸并后：[38496597][132776]三趟歸并后：[13273849657697]穩(wěn)定的排序方法2/3/202349兩個有序序列歸并為一個有序序列的算法10.12voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){

//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n] for(j=m+1,k=i;i<=m&&j<=n;++k){

//將SR中記錄按關鍵字從小到大地復制到TR中

if(LQ(SR[i].key,SR[j].key))TR[k]=SR[i++];

elseTR[k]=SR[j++];

} while(i<=m)TR[k++]=SR[i++];//將剩余的SR[i..m]復制到TR while(j<=n)TR[k++]=SR[j++];//將剩余的SR[j..n]復制到TR}//Merge2/3/202350算法評價時間復雜度：T(n)=O(nlog2n)每趟兩兩歸并需調(diào)用merge算法n/2h次（h為有序段長度）；整個歸并要進行l(wèi)og2n趟?？臻g復雜度：S(n)=O(n)2/3/20235110.6基數(shù)排序10.6.1多關鍵字的排序多關鍵字排序例對52張撲克牌按以下次序排序：兩個關鍵字：花色（<<<）

面值（2<3<……<A）

并且“花色”地位高于“面值”2<3<……<A<2<3<……<A<

2<3<……<A<2<3<……<A2/3/202352多關鍵字排序方法最高位優(yōu)先法（MSD)：

先對最高位關鍵字k1排序，將序列分成若干子序列，每個子序列有相同的k1值；然后讓每個子序列對次關鍵字k2（如面值）排序，又分成若干更小的子序列；依次重復，直至就每個子序列對最低位關鍵字kd排序；最后將所有子序列依次連接在一起成為一個有序序列。最低位優(yōu)先法(LSD)：

從最低位關鍵字kd起進行排序，然后再對高一位的關鍵字排序，……依次重復，直至對最高位關鍵字k1排序后，便成為一個有序序列。2/3/202353MSD與LSD不同特點按MSD排序，必須將序列逐層分割成若干子序列，然后對各子序列分別排序。按LSD排序，不必分成子序列，對每個關鍵字都是整個序列參加排序；并且可不通過關鍵字比較，而通過若干次分配與收集實現(xiàn)排序。2/3/20235410.6.2鏈式基數(shù)排序基數(shù)排序一種借助"多關鍵字排序"的思想來實現(xiàn)"單邏輯關鍵字排序"的內(nèi)部排序算法?；鶖?shù)排序的步驟設置10個隊列，f[i]和e[i]分別為第i個隊列的頭指針和尾指針；第一趟分配對最低位關鍵字（個位）進行，改變記錄的指針值，將鏈表中記錄分配至10個鏈隊列中，每個隊列記錄的關鍵字的個位相同；第一趟收集是改變所有非空隊列的隊尾記錄的指針域，令其指向下一個非空隊列的隊頭記錄，重新將10個隊列鏈成一個鏈表；重復上述兩步，進行第二趟、第三趟分配和收集，分別對十位、百位進行，最后得到一個有序序列。2/3/202355初始狀態(tài)：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：2/3/202356505008109930063269278083184589二趟收集：083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集：2/3/202357008063083109184269278505589930三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589二趟收集：穩(wěn)定的排序方法2/3/202358算法評價時間復雜度：分配：T(n)=O(n)收集：T(n)=O(rd)T(n)=O(d(n+rd))其中：n——記錄數(shù)

d——關鍵字數(shù)

rd——關鍵字取值范圍空間復雜度：S(n)=2rd個隊列指針+n個指針域空間2/3/20235910.7各種內(nèi)部排序方法的比較討論時間性能按平均的時間性能來分，有三類排序方法：時間復雜度為O(nlogn)

的方法有：快速排序、堆排序和歸并排序，其中快速排序目前被認為是最快的一種排序方法，后兩者之比較，在n值較大的情況下，歸并排序較堆排序更快；時間復雜度為O(n2)

的有：插入排序、起泡排序和選擇排序，其中以插入排序為最常用，特別是對于已按關鍵字基本有序排列的記錄序列尤為如此，選擇排序過程中記錄移動次數(shù)最少；時間復雜度為O(n)

的排序方法基數(shù)排序。2/3/202360當待排記錄序列按關鍵字順序有序時，插入排序和起泡排序能達到O(n)的時間復雜度；而對于快速排序而言，這是最不好的情況，此時的時間性能蛻化為O(n2)，因此應盡量避免。選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關鍵字的分布而改變。以上對排序的時間復雜度的討論主要考慮排序過程中所需進行的關鍵字間的比較次數(shù)，當待排序記錄中其它各數(shù)據(jù)項比關鍵字占有更大的數(shù)據(jù)量時，還應考慮到排序過程中移動記錄的操作時間，有時這種操作的時間在整個排序過程中占的比例更大，從這個觀點考慮，簡單排序的