第10章排序排序的基本概念插入排序選擇排序交換排序歸并排序基數排序性能比較主要知識點10.1排序的基本概念排序是對數據元素序列建立某種有序排列的過程,是把一個數據元素序列整理成按關鍵字遞增（或遞減）排列的過程。關鍵字是要排序的數據元素集合中的一個域，排序是以關鍵字為基準進行的。主關鍵字:數據元素值不同時該關鍵字的值也一定不同，是能夠惟一區分各個不同數據元素的關鍵字;不滿足主關鍵字定義的關鍵字稱為次關鍵字。內部排序是把待排數據元素全部調入內存中進行的排序。外部排序是因數量太大，把數據元素分批導入內存，排好序后再分批導出到磁盤和磁帶外存介質上的排序方法。比較排序算法優劣的標準:(1)時間復雜度:它主要是分析記錄關鍵字的比較次數和記錄的 移動次數(2)空間復雜度:算法中使用的內存輔助空間的多少

(3)穩定性:若兩個記錄A和B的關鍵字值相等，但排序后A、B的 先后次序保持不變，則稱這種排序算法是穩定的10.2插入排序插入排序的基本思想是：每步將一個待排序的數據元素，按其關鍵碼大小，插入到前面已經排好序的一組數據元素的適當位置上，直到數據元素全部插入為止。1.直接插入排序常用的插入排序有直接插入排序和希爾排序兩種。其基本思想是：

順序地把待排序的數據元素按其關鍵字值的大小插入到已排序數據元素子集合的適當位置。算法如下：voidInsertSort(DataTypea[],intn)//用直接插入法對a[0]--a[n-1]排序{

inti,j;

DataTypetemp;

for(i=0;i<n-1;i++) {temp=a[i+1]; j=i;

while(j>-1&&temp.key<a[j].key) {a[j+1]=a[j]; j--; } a[j+1]=temp; }}算法分析:(1)空間效率：僅占用若干個臨時內存單元——O(1)(2)算法的穩定性：穩定(3)時間效率：

在最壞情況下（反序），所有元素的比較次數總和為（1＋2＋…＋n-1)→O(n2)。 平均時間復雜度也為O(n2)

但在最好情況下（正序），所有元素的比較次數總和為（1＋1＋…＋1)→O(n)。

分析：元素序列越接近有序，比較次數越少。時間復雜度越接近O(n)

。{64}789624{564}89624{5764}624{576489}24{5676489}{567246489}589624初始關鍵字序列:第一次排序:第二次排序:第三次排序:第四次排序:第五次排序:7直接插入排序過程2.希爾(shell)排序(又稱縮小增量排序)(1)基本思想：把整個待排序的數據元素分成若干個小組，對同一小組內的數據元素用直接插入法排序；小組的個數逐次縮小，當完成了所有數據元素都在一個組內的排序后排序過程結束。

(2)技巧：小組的構成不是簡單地“逐段分割”，而是將相隔某個增量dk的記錄組成一個小組,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。(3)優點：每次排序都采用直接插入排序法。當數據元素個數n較小時，盡量調整元素序列使之接近有序。這樣，當數據元素個數n為全部元素時，數據元素序列已比較接近有序。從而，整體的時間效率會好很多。算法如下：voidShellSort(DataTypea[],intn,intd[],int

numOfD)//用希爾排序法對元素a[0]--a[n-1]排序，d[0]--d[numOfD-1]為希爾增量值{inti,j,k,m,span;

DataTypetemp;

for(m=0;m<numOfD;m++) //共numOfD次循環 {span=d[m]; //取本次的增量值

for(k=0;k<span;k++) //共span個小組 { //組內是直接插入排序，區別是每次不是增1而是增span

for(i=k;i<n-span;i=i+span) {temp=a[i+span]; j=i;

while(j>-1&&temp.key<a[j].key) {a[j+span]=a[j]; j=j-span; }

a[j+span]=temp; } } }}653425871238564614779223563414771223654625879238結果序列d=6563414771223654625879238561214653423774625879238結果序列d=3561214653423774625879238121423253438465665778792結果序列d=1(a)(b)(c)希爾排序的排序過程10.3選擇排序基本思想是：每次從待排序的數據元素集合中選取關鍵字最小（或最大）的數據元素放到數據元素集合的某個位置，數據元素集合不斷縮小，當數據元素集合為空時選擇排序結束。常用的選擇排序算法：

（1）直接選擇排序

（2）堆排序1.直接選擇排序基本思想是：從待排序的數據元素集合中選取關鍵字最小的數據元素并將它與原始數據元素集合中的第一個數據元素交換位置；然后從不包括第一個位置上數據元素的集合中選取關鍵字最小的數據元素并將它與原始數據元素集合中的第二個數據元素交換位置；如此重復，直到數據元素集合中只剩一個數據元素為止。優點：實現簡單缺點：每趟只能確定一個元素，表長為n時需要n-1趟算法如下：voidSelectSort(DataTypea[],intn){

inti,j,small;

DataTypetemp;

for(i=0;i<n-1;i++) {small=i; //設第i個數據元素關鍵字最小

for(j=i+1;j<n;j++) //尋找關鍵字最小的數據元素

if(a[j].key<a[small].key)small=j;//記住最小元素的下標

if(small!=i) //當最小元素的下標不為i時交換位置 {

temp=a[i];

a[i]=a[small];

a[small]=temp; } }}645789624{5}64789624{56}7896424{567}896424{56724}6489{5672464}89初始關鍵字序列:第一次排序結果:第二次排序結果:第三次排序結果:第四次排序結果:第五次排序結果:{567246489}最后結果序列:直接選擇排序的排序過程算法分析時間效率：O(n2)——雖移動次數較少，但比較次數仍多。

空間效率：O(1)——僅用到若干個臨時變量。算法的穩定性：不穩定2.堆排序

基本思想:把待排序的數據元素集合構成一個完全二叉樹結構，則每次選擇出一個最大（或最小）的數據元素只需比較完全二叉樹的高度次，即log2n次，則排序算法的時間復雜度就是O(nlog2n)。一、堆的定義堆分為最大堆和最小堆兩種。定義如下：設數組a中存放了n個數據元素，數組下標從0開始，如果當數組下標2i+1<n時有:a[i].key≥a[2i+1].key(a[i].key≤a[2i+1].key)；如果當數組下標2i+2<n時有:a[i].key≥a[2i+2].key(a[i].key≤a[2i+2].key)，則這樣的數據結構稱為最大堆(最小堆)。1050325769408888764050109325(a)(b)(a)完全二叉樹(b)最大堆性質：（1）最大堆的根結點是堆中值最大的數據元素，最小堆的根結點是堆中值最小的數據元素，我們稱堆的根結點元素為堆頂元素。（2）對于最大堆，從根結點到每個葉結點的路徑上，數據元素組成的序列都是遞減有序的；對于最小堆，從根結點到每個葉結點的路徑上，數據元素組成的序列都是遞增有序的。二、創建堆

終端結點（即葉子）沒有任何子女，無需單獨調整步驟：從最后一個非終端結點開始往前逐步調整，讓每個雙親大于（或小于）子女，直到根結點為止。創建最大堆過程中要多次調用函數：調整完全二叉樹中某個非葉結點a[i]，使之滿足最大堆定義，前提條件是該結點的左孩子結點a[2i+1]和右孩子結點a[2i+2]都已是最大堆。函數設計如下：

voidCreatHeap(DataTypea[],intn,inth){

inti,j,flag;

DataTypetemp;

i=h; //i為要建堆的二叉樹根結點下標

j=2*i+1; //j為i的左孩子結點的下標

temp=a[i]; flag=0;

while(j<n&&flag!=1) {//尋找左右孩子結點中的較大者,j為其下標

if(j<n-1&&a[j].key<a[j+1].key)j++;

if(temp.key>a[j].key) //a[i].key>a[j].key flag=1; //標記結束篩選條件

else //否則把a[j]上移 {a[i]=a[j]; i=j; j=2*i+1; } }

a[i]=temp; //把最初的a[i]賦予最后的a[j]}初始化創建最大堆算法如下：voidInitCreatHeap(DataTypea[],intn) {

inti;

for(i=(n-2)/2;i>=0;i--)

CreatHeap(a,n,i);}堆排序的基本思想是：循環執行如下過程直到數組為空：（1）把堆頂a[0]元素（為最大元素）和當前最大堆的最后一個元素交換；（2）最大堆元素個數減1；（3）由于第（1）步后根結點不再滿足最大堆的定義，所以調整根結點使之滿足最大堆的定義。三、堆排序算法1050325769408810503257694088數組1050328876940510503288769405數組1050408876932510504088769325數組1088405076932510884050769325數組8876405010932588764050109325數組(a)初始狀態

(b)調整結點5后(c)調整結點32后(d)調整結點50后(e)調整結點10后完全二叉樹調整為最大堆的過程堆排序算法如下：voidHeapSort(DataTypea[],intn){inti;

DataTypetemp;

InitCreatHeap(a,n); //初始化創建最大堆

for(i=n-1;i>0;i--) //當前最大堆個數每次遞減1{//把堆頂a[0]元素和當前最大堆的最后一個元素交換temp=a[0]; a[0]=a[i];

a[i]=temp;

CreatHeap(a,i,0); //調整根結點滿足最大堆}}堆排序算法的排序過程

算法分析：時間效率：O(nlog2n)。因為整個排序過程中需要調用n-1次堆頂點的調整，而每次堆排序算法本身耗時為log2n；空間效率：O(1)。僅用到若干個臨時變量。穩定性：

不穩定。優點：對小文件效果不明顯，但對大文件有效。10.4交換排序

交換排序的基本思想是：利用交換數據元素的位置進行排序的方法。交換排序的主要算法有：1)冒泡排序2)快速排序1.冒泡排序基本思想：每趟不斷將數據元素兩兩比較，并按“前小后大”（或“前大后小”）規則交換。優點：每趟結束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發生，還可以提前結束排序。算法核心語句如下：

flag=1;for(i=1;i<n&&flag==1;i++){ flag=0;

for(j=0;j<n-i;j++) {

if(a[j].key>a[j+1].key)

{

flag=1; temp=a[j];

a[j]=a[j+1]; a[j+1]=temp; } }}初始關鍵字序列:第一次排序結果:第二次排序結果:第三次排序結果:第四次排序結果:第五次排序結果:最后結果序列:38519264997166519263849166[97]5192638149[6697]51926138[496697]519126[38496697]5119[2638496697]15[192638496697]1[5192638496697]15192638496697第六次排序結果:第七次排序結果:冒泡排序算法的排序過程算法分析：最好情況：初始排列已經有序，只執行一趟起泡，做n-1次關鍵碼比較，不移動數據元素。最壞情形：初始排列逆序，算法要執行n-1趟起泡，第i趟(1

i

n)做了n-i次關鍵碼比較，執行了n-i次數據元素交換。此時的比較總次數和記錄移動次數為：2.快速排序

基本思想：從待排序列中任取一個元素(例如取第一個)作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表；然后再對各子表重新選擇中心元素并依此規則調整，直到每個子表的元素只剩一個。此時便為有序序列了。優點：因為每趟可以確定不止一個元素的位置，而且呈指數增加，所以特別快。因此：時間效率：O（n2)

—考慮最壞情況空間效率：O（1）

—僅用到若干個臨時變量穩定性：穩定的算法核心語句如下： while(i<j&&temp.key<=a[j].key)j--;//在數組的右端掃描

if(i<j) {

a[i]=a[j]; i++; }

while(i<j&&a[i].key<temp.key)i++;//在數組的左端掃描

if(i<j) {

a[j]=a[i]; j--; }6055483710908436365548371090849090365548371090843655483710908436554837109084365548371090843655483710908436554837108436554837106084iiiiiiiijjjjjjjjij初始關鍵字序列:(1)(2)(3)(4)(5)(6)(7)(8)快速排序算法一次快速排序過程圖中標有下劃橫線的數據元素為本次快速排序選取的標準元素。快速排序算法各次快速排序過程初始關鍵字序列:(1)(2){6055483710908436{3655483710}60{90}{10}36{3755}6084{}(3){10}36{}48{}608490最后結果1036374855608490{37}48558490時間效率：O(nlog2n)

—因為每趟確定的元素呈指數增加空間效率：O(log2n)—因為遞歸要用堆棧穩定性：不穩定

—因為有跳躍式交換。算法分析：10.5歸并排序歸并排序主要是二路歸并排序,基本思想是：可以把一個長度為n的無序序列看成是

n個長度為1的有序子序列，首先做兩兩歸并，得到n/2個長度為2的有序子序列；再做兩兩歸并，…，如此重復，直到最后得到一個長度為n的有序序列。

一次二路歸并排序算法如下：voidMerge(DataTypea[],intn,DataTypeswap[],intk)//k為子數組長度，一次二路歸并排序后的子序列存于數組swap中{intm=0,u1,l2,i,j,u2;

intl1=0; //第一個有序子數組下界為0

while(l1+k<=n-1) {l2=l1+k; //第二個有序子數組下界

u1=l2-1; //第一個有序子數組上界

u2=(l2+k-1<=n-1)?l2+k-1:n-1;//第二個子數組上界//兩個有序子數組合并

for(i=l1,j=l2;i<=u1&&j<=u2;m++) {

if(a[i].key<=a[j].key) {swap[m]=a[i];i++;} else {swap[m]=a[j];j++;} }

//子數組2已完，將子數組1中剩余的元素存放到swap

while(i<=u1) {swap[m]=a[i];m++;i++; } //子數組1已完，將子數組2中剩余的元素存放到swap

while(j<=u2) {swap[m]=a[j];m++;j++; }

l1=u2+1;}

//將原始數組中只夠一組的數據元素順序存放到數組swap

for(i=l1;i<n;i++,m++)swap[m]=a[i];}二路歸并排序算法分析時間效率：

O(nlog2n)因為在遞歸的歸并排序算法中，遞歸調用函數Merge()約為log2n

次，而每次歸并要執行比較約為n次，所以算法總的時間復雜度為O(nlog2n)。空間效率：

O(n)

因為需要一個與原始序列同樣大小的輔助序列。這是此算法的缺點。穩定性：穩定10.6基數排序基數排序也稱作桶排序，是一種當關鍵字為整數類型時非常高效的排序方法。

其基本思想是：設待排序的數據元素關鍵字是m位d進制整數（不足m位的關鍵字在高位補0），設置d個桶，令其編號分別為0,1,2,…,d-1。首先按關鍵字最低位的數值依次把各數據元素放到相應的桶中，然后按照桶號從小到大和進入桶中數據元素的先后次序收集分配在各桶中的數據元素，這樣就形成了數據元素集合的一個新的排列，我們稱這樣的一次排序過程為一次基數排序；

再對一次基數排序得到的數據元素序列按關鍵字次低位的數值依次把各數據元素放到相應的桶中，然后按照桶號從小到大和進入桶中數據元素的先后次序收集分配在各桶中的數據元素；這樣的過程重復進行，當完成了第m次基數排序后，就得到了排好序的數據元素序列。數據元素的關鍵字序列為{710,342,045,686,006,841,429,134,068,264}排序過程如下8411342231342644045568600667068871004299710841342134264045686006068429收集后的新序列:放置7101429213438413420454526406867686800609006710429134841342045264068686收集后的新序列:放置1341264234234294568667107841800604506809006045068134264342429686710841收集后的新序列:放置(a)初始狀態

(b)第一次基數排序

(c)第二次基數排序基數排序算法進出桶中的數據元素序列滿足先進先出的原則，桶實際就是隊列。實現基數排序算法時，有基于順序隊列和基于鏈式隊列兩種不同的實現方法。在基于鏈式隊列的基數排序算法中，可以把d個隊列設計成一個隊列數組（設隊列數組名為tub），隊列數組的每個元素中包括兩個域：front域和rear域。front域用于指示隊頭，rear域用于指示隊尾。當第i（i=0,1,2,…,d-1）個隊列中有數據元素要放入時，就在隊列數組的相應元素tub[i]中的隊尾位置插入一個結點。基于鏈式隊列基數排序算法的存儲結構示意圖如下圖所示。......rearfrontdatanext∧

012d-1...tub∧

一個十進制關鍵字K的第i位數值Ki的計算公式為：基于鏈式隊列的基數排序算法:

#include"LQueue.h"

void

RadixSort(DataTypea[],intn,intm,intd)

{

inti,j,k,power=1;

LQueue*tub; //把d個隊列定義為動態數組

tub=(LQueue*)malloc(sizeof(LQueue)*d);

for(i=0;i<