數據結構課程的內容1數據結構第10章內部排序共107頁，您現在瀏覽的是第1頁!10.1概述10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數排序第10章內部排序2數據結構第10章內部排序共107頁，您現在瀏覽的是第2頁!10.1概述1.什么是排序？將一組雜亂無章的數據按一定的規律順次排列起來。

2.排序的目的是什么？存放在數據表中按關鍵字排序3.排序算法的好壞如何衡量？時間效率—排序速度(即排序所花費的全部比較次數)空間效率—占內存輔助空間的大小穩定性—若兩個記錄A和B的關鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩定的。——便于查找！3數據結構第10章內部排序共107頁，您現在瀏覽的是第3頁!4.什么叫內部排序？什么叫外部排序？

——若待排序記錄都在內存中，稱為內部排序；——若待排序記錄一部分在內存，一部分在外存，則稱為外部排序。注：外部排序時，要將數據分批調入內存來排序，中間結果還要及時放入外存，顯然外部排序要復雜得多。

5.待排序記錄在內存中怎樣存儲和處理？①順序排序——排序時直接移動記錄；②鏈表排序——排序時只移動指針；③地址排序——排序時先移動地址，最后再移動記錄。注：地址排序中可以增設一維數組來專門存放記錄的地址。4數據結構第10章內部排序共107頁，您現在瀏覽的是第4頁!7.內部排序的算法有哪些？——按排序的規則不同，可分為5類：插入排序交換排序（重點是快速排序）選擇排序歸并排序基數排序d＝關鍵字的位數(長度)——按排序算法的時間復雜度不同，可分為3類：簡單的排序算法：時間效率低，O(n2)先進的排序算法:時間效率高，O(nlog2n)基數排序算算法：時間效率高，O(d×n)5數據結構第10章內部排序共107頁，您現在瀏覽的是第5頁!10.2插入排序插入排序有多種具體實現算法：1)直接插入排序2)折半插入排序3)表插入排序4)希爾排序簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。6數據結構第10章內部排序共107頁，您現在瀏覽的是第6頁!例2：關鍵字序列T=（21，25，49，25*，16，08），

請寫出直接插入排序的具體實現過程。*表示后一個25i=121254925*16080123456暫存21i=2i=3i=5i=4i=625252549494925*25*49161625*080849解：假設該序列已存入一維數組V[7]中，將V[0]作為緩沖或暫存單元（Temp）。則程序執行過程為：21254925*21初態：164925*25211608完成!時間效率：O(n2)——因為在最壞情況下，所有元素的比較次數總和為（0＋1＋…＋n-1)→O(n2)。其他情況下還要加上移動元素的次數。空間效率：O（1）——因為僅占用1個緩沖單元算法的穩定性：穩定——因為25*排序后仍然在25的后面。

7數據結構第10章內部排序共107頁，您現在瀏覽的是第7頁!直接插入排序算法描述如下:voidInserSort(SqList&L){//對順序表L作直接插入排序。for(i=2;i<=L.length;++i) if(LT(L.r[i].key,L.r[i-1].key)) {L.r[0]=L.r[i]; //復制為監視哨 for(j=i-1;LT(L.r[i].key,L.r[i-1].key);--j) L.r[j+1]=L.r[j]; //記錄后移 L.r[j+1]=L.r[0]; //插入到正確位置 }}//InsertSort8數據結構第10章內部排序共107頁，您現在瀏覽的是第8頁!最壞情況下，第i趟插入時，第i個對象必須與前面i-1個對象都做關鍵字比較，并且每做1次比較就要做1次數據移動。則總的關鍵字比較次數KCN和對象移動次數RMN分別為9數據結構第10章內部排序共107頁，您現在瀏覽的是第9頁!2）折半插入排序優點：比較的次數大大減少，全部元素比較次數僅為O(nlog2n)。時間效率：雖然比較次數大大減少，可惜移動次數并未減少，所以排序效率仍為O(n2)。空間效率：

O（1）穩定性：穩定當待排序記錄的數量n很小時，直接插入排序是一種簡便的方法；但當記錄數量n很大時，則不宜采用直接插入排序。由于插入排序的基本操作是在有序表R[1..i-1]中進行查找和插入的；則可以利用折半查找實現“在R[1..i-1]中查找R[i]的插入位置”，并在適當位置插入，把原來位置上的元素向后順移。如此實現的插入排序為折半插入排序。10數據結構第10章內部排序共107頁，您現在瀏覽的是第10頁!討論：若記錄是鏈表結構，用直接插入排序行否？折半插入排序呢？答：直接插入不僅可行，而且還無需移動元素，時間效率更高！折半插入排序的改進——2-路插入排序見教材P267。但鏈表無法“折半”！11數據結構第10章內部排序共107頁，您現在瀏覽的是第11頁!3）表插入排序基本思想：在順序存儲結構中，給每個記錄增開一個指針分量，在排序過程中將指針內容逐個修改為已經整理（排序）過的后繼記錄地址。優點：在排序過程中不移動元素，只修改指針。回憶：②鏈表排序——排序時只移動指針；③地址排序——排序時先移動地址，最后再移動記錄。此方法具有鏈表排序和地址排序的特點。12數據結構第10章內部排序共107頁，您現在瀏覽的是第12頁!表插入排序算法分析：①無需移動記錄，只需修改2n次指針值。但由于比較次數沒有減少，故時間效率仍為O(n2)。②空間效率肯定低，因為增開了指針分量（但在運算過程中沒有用到更多的輔助單元）。③穩定性：25和25*排序前后次序未變，穩定。討論：此算法得到的只是一個有序鏈表，查找記錄時只能滿足順序查找方式。改進：可以根據表中指針線索，很快對所有記錄重排，形成真正的有序表（順序存儲方式），從而能滿足折半查找方式。具體實現見教材P269。13數據結構第10章內部排序共107頁，您現在瀏覽的是第13頁!38例：關鍵字序列T=(49，38，65，97,76,13,27,49*，55,04），請寫出希爾排序的具體實現過程。0123456789104938659776132749*5504初態：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*9755760427386549*9755135576045513270427044949*4949*76387665659797551327044949*3876659713270449*7697算法分析：開始時dk

的值較大，子序列中的對象較少，排序速度較快；隨著排序進展，dk

值逐漸變小，子序列中對象個數逐漸變多，由于前面工作的基礎，大多數對象已基本有序，所以排序速度仍然很快。r[i]問題：第三趟(dk=1)的排序過程與在初態序列上直接進行dk=1排序是否相同？14數據結構第10章內部排序共107頁，您現在瀏覽的是第14頁!voidShellInsert(SqList&L，int

dk){

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

L.r[0]=L.r[i]；

for(j=i-dk;j>0&&(L.r[0].key<L.r[j].key);j=j-dk) L.r[j+dk]=L.r[j]；L.r[j+dk]=L.r[0]；}}希爾排序算法（其中某一趟的排序操作）參見教材P272//對順序表L進行一趟增量為dk的Shell排序，dk為步長因子//開始將r[i]插入有序增量子表//暫存在r[0]//關鍵字較大的記錄在子表中后移//在本趟結束時將r[i]插入到正確位置15數據結構第10章內部排序共107頁，您現在瀏覽的是第15頁!2.以關鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，分別寫出執行以下算法的各趟排序結束時，關鍵字序列的狀態，并說明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環鏈表）上實現？①直接插入排序②希爾排序（取dk=5,3,1）答：顯然，直接插入排序方法易于在鏈表上實現；但希爾排序方法因為是按增量選擇記錄，不易于在鏈表上實現。

兩種排序方法的中間狀態分別描述如后：16數據結構第10章內部排序共107頁，您現在瀏覽的是第16頁!原始序列：

256，301，751，129，937，863，742，694，076，438希爾排序(取dk=5,3,1)256，301，751，129，937，863，742，694，076，438256，301，751，129，937，863，742，694，076，438256，301，694，129，937，863，742，751，076，438256，301，694，076，937，863，742，751，129，438256，301，694，076，438，863，742，751，129，937第1趟dk=5第2趟dk=3第3趟dk=1256，301，694，076，438，863，742，751，129，937256，301，694，076，438，863，742，751，129，937076，301，694，256，438，863，742，751，129，937076，301，694，256，438，863，742，751，129，937076，301，694，256，438，863，742，751，129，937076，301，129，256，438，694，742，751，863，937076，301，129，256，438，694，742，751，863，937076，301，129，256，438，694，742，751，863，937076，129，256，301，438，694，742，751，863，93717數據結構第10章內部排序共107頁，您現在瀏覽的是第17頁!1)冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規則交換。優點：每趟結束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發生，還可以提前結束排序。前提：順序存儲結構

例：關鍵字序列T=(21，25，49，25*，16，08），請寫出冒泡排序的具體實現過程。(假設“前小后大”)21，25，49，25*，16，0821，25，25*，16，08，4921，25，16，08，25*，4921，16，08，25，

25*，4916，08，21，

25，

25*，4908，16，

21，

25，

25*，49初態：第1趟第2趟第3趟第4趟第5趟18數據結構第10章內部排序共107頁，您現在瀏覽的是第18頁!2）快速排序

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

19數據結構第10章內部排序共107頁，您現在瀏覽的是第19頁!1.這種不斷劃分子表的過程，計算機如何自動實現？編程時：①每一趟的子表的形成是采用從兩頭向中間交替式逼近法;②由于每趟中對各子表的操作都相似，主程序可采用遞歸算法。見教材P275intPartition(SqList&L,intlow,inthigh){//交換順序表L.r[low…high]的記錄，使樞軸記錄到位，并返回其位置。返回時，在樞軸之前的記錄均不大于它，樞軸之后的記錄均不小于它。

pivotkey=L.r[low].key;//取樞軸的關鍵字存入pivotkey變量（續下頁）一趟快速排序算法（針對一個子表的操作）20數據結構第10章內部排序共107頁，您現在瀏覽的是第20頁!Low=high=3，本趟停止，將支點定位并返回位置信息例2：關鍵字序列T=(21，25，49，25*，16，08），請寫出快速排序算法的一趟實現過程。r[i]0123456初態21254925*1608第1趟highlow210825164925*321pivotkey=2108251649(08

，16）21（25*，49，25）25*跑到了前面，不穩定！21數據結構第10章內部排序共107頁，您現在瀏覽的是第21頁!voidQSort(SqList&L,intlow,inthigh

){

if(low<high){

pivot=Partition(L,low,high);

QSort(L,low,pivot-1);

QSort(L,pivot+1,high);}}整個快速排序的遞歸算法：見教材P276//長度>1//對順序表L中的子序列r[low…high]

作快速排序//QSortvoidQuickSort(SqList&L){QSort(L,

1,L.length

);}對順序表L進行快速排序的操作函數為：22數據結構第10章內部排序共107頁，您現在瀏覽的是第22頁!快速排序算法詳細分析：快速排序是遞歸的，需要有一個棧存放每層遞歸調用時的指針和參數（新的low和high）。可以證明，函數quicksort的平均計算時間也是O(nlog2n)。實驗結果表明：就平均計算時間而言，快速排序是我們所討論的所有內排序方法中最好的一個。最大遞歸調用層次數與遞歸樹的深度一致，理想情況為log2(n+1)。因此，要求存儲開銷為o(log2n)。23數據結構第10章內部排序共107頁，您現在瀏覽的是第23頁!在最壞的情況，即待排序對象序列已經按其關鍵字從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個比上一次少一個對象的子序列。這樣，必須經過n-1趟才能把所有對象定位，而且第i趟需要經過n-i次關鍵字比較才能找到第

i

個對象的安放位置，總的關鍵字比較次數將達到n2/2快速排序是一個不穩定的排序方法24數據結構第10章內部排序共107頁，您現在瀏覽的是第24頁!而且，每趟需要比較和移動的元素也呈指數下降，加上編程時使用了交替逼近技巧，更進一步減少了移動次數，所以速度特別快。教材P276有證明：快速排序的平均排序效率為O(nlog2n)；但最壞情況(例如已經有序)下仍為O(n2),改進措施見P277。25數據結構第10章內部排序共107頁，您現在瀏覽的是第25頁!10.4.1簡單選擇排序SimpleSelectionSort基本步驟為：i從1開始，直到n-1，進行n-1趟排序，第i趟的排序過程為：在一組對象r[i]～r[n](i=1,2,…,n-1)中選擇具有最小關鍵字的對象；并和第i個對象進行交換；26數據結構第10章內部排序共107頁，您現在瀏覽的是第26頁!21254925*16080123452125*i=1492516251608490825*4921i=2i=3081625*2521初始最小者08交換21,08最小者16交換25,16最小者21交換49,2127數據結構第10章內部排序共107頁，您現在瀏覽的是第27頁!算法分析

直接選擇排序的關鍵字比較次數KCN與對象的初始排列無關。第i趟選擇具有最小關鍵字對象所需的比較次數總是n-i-1次，此處假定整個待排序對象序列有n個對象。因此，總的關鍵字比較次數為時間復雜度？O（n2）28數據結構第10章內部排序共107頁，您現在瀏覽的是第28頁!10.4.2樹形選擇排序(錦標賽排序)它的思想與體育比賽時的淘汰賽類似。首先取得n個對象的關鍵字，進行兩兩比較，得到n/2個比較的優勝者(關鍵字小者)，作為步比較的結果保留下來。然后對這n/2個對象再進行關鍵字的兩兩比較，…，如此重復，直到選出一個關鍵字最小的對象為止。在圖例中，最下面是對象排列的初始狀態，相當于一棵滿二叉樹的葉結點，它存放的是所有參加排序的對象的關鍵字。29數據結構第10章內部排序共107頁，您現在瀏覽的是第29頁!勝者樹的概念每次兩兩比較的結果是把關鍵字小者作為優勝者上升到雙親結點，稱這種比賽樹為勝者樹。勝者樹最頂層是樹的根，表示最后選擇出來的具有最小關鍵字的對象。30數據結構第10章內部排序共107頁，您現在瀏覽的是第30頁!16Winner(勝者)2116166325*2121254925*1663輸出冠軍并調整勝者樹后樹的狀態a[1]關鍵字比較次數:231數據結構第10章內部排序共107頁，您現在瀏覽的是第31頁!25Winner(勝者)25636325*25254925*63輸出第三名并調整勝者樹后樹的狀態a[3]關鍵字比較次數:232數據結構第10章內部排序共107頁，您現在瀏覽的是第32頁!63Winner(勝者)636363全部比賽結果輸出時樹的狀態a[6]關鍵字比較次數:233數據結構第10章內部排序共107頁，您現在瀏覽的是第33頁!10.4.3堆排序(HeapSort)利用堆及其運算，可以很容易地實現選擇排序的思路。堆排序分為兩個步驟：步，根據初始輸入數據，利用堆的調整算法HeapAdjust()形成初始堆，第二步，通過一系列的對象交換和重新調整堆進行排序。給定一組關鍵字，初始態存儲時是一個完全二叉樹堆的建立對堆的篩選與建立的重復交替34數據結構第10章內部排序共107頁，您現在瀏覽的是第34頁!建立初始的最大堆212525*491608123456i212525*164908136542i21254925*1608初始關鍵字集合21254925*1608i=3時的局部調整35數據結構第10章內部排序共107頁，您現在瀏覽的是第35頁!最大堆的向下調整算法voidHeapAdjust(HeapType&H,ints,intm){ElemTyperc=H.r[s];for(intj=2*s;j<=m;j*=2){ if((j<m)&&(LT(H.r[j].key,H.r[j+1].key)))++j; if(!(LT(rc.key,H.r[j].key)))break; H.r[s].key=H.r[j].key;s=j;}H.r[s]=rc;}36數據結構第10章內部排序共107頁，您現在瀏覽的是第36頁!492525*211608123456082525*16214913654249252125*160808252125*1649交換1號與6號對象,6號對象就位初始最大堆37數據結構第10章內部排序共107頁，您現在瀏覽的是第37頁!25*1608212549123456081625*25214913654225*16210825

4908162125*

25

49交換1號與4號對象,4號對象就位從1號到4號重新調整為最大堆38數據結構第10章內部排序共107頁，您現在瀏覽的是第38頁!160825*212549123456081625*25214913654216082125*

25

490816

21

25*

25

49交換1號與2號對象,2號對象就位從1號到2號重新調整為最大堆39數據結構第10章內部排序共107頁，您現在瀏覽的是第39頁!算法分析若設堆中有n個結點，且2k-1

n

2k，則對應的完全二叉樹有k層。在第i層上的結點數2i-1(i=1,…,k)。在個形成初始堆的for循環中對每一個非葉結點調用了一次堆調整算法HeapAdjust()，因此該循環所用的計算時間為：其中，i是層序號，2i-1是第i層的最大結點數，(k-i-1)是第i層結點能夠移動的最大距離。40數據結構第10章內部排序共107頁，您現在瀏覽的是第40頁!10.5歸并排序基本思想：將一個具有n個待排序記錄的序列看成是n個長度為1的有序列，然后進行兩兩歸并，得到「n/2個長度為2的有序序列，再進行兩兩歸并，得到「n/4個長度為4的有序序列，如此重復，直至得到一個長度為n的有序序列為止41數據結構第10章內部排序共107頁，您現在瀏覽的是第41頁!歸并排序示例42數據結構第10章內部排序共107頁，您現在瀏覽的是第42頁!10.6基數排序(RadixSort)基數排序是采用“分配”與“收集”的辦法，用對多關鍵字進行排序的思想實現對單關鍵字進行排序的方法。10.6.1多關鍵字排序以撲克牌排序為例。每張撲克牌有兩個“關鍵字”：花色和面值。其有序關系為：

花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A如果我們把所有撲克牌排成以下次序：2,…,A,2,…,A,2,…,A,2,…,A43數據結構第10章內部排序共107頁，您現在瀏覽的是第43頁!則稱序列對關鍵字(K1,K2,…,Kd)有序。其中，K1稱為最高位關鍵字，Kd稱為最低位關鍵字。如果關鍵字是由多個數據項組成的數據項組，則依據它進行排序時就需要利用多關鍵字排序。實現多關鍵字排序有兩種常用的方法最高位優先MSD(MostSignificantDigitfirst)最低位優先LSD(LeastSignificantDigitfirst)最高位優先法通常是一個遞歸的過程：

先根據最高位關鍵字K1排序,得到若干對象組，對象組中每個對象都有相同關鍵字K1。44數據結構第10章內部排序共107頁，您現在瀏覽的是第44頁!最低位優先法首先依據最低位關鍵字Kd對所有對象進行一趟排序，再依據次低位關鍵字Kd-1對上一趟排序的結果再排序，依次重復，直到依據關鍵字K1最后一趟排序完成，就可以得到一個有序的序列。使用這種排序方法對每一個關鍵字進行排序時，不需要再分組，而是整個對象組都參加排序。45數據結構第10章內部排序共107頁，您現在瀏覽的是第45頁!基數排序是典型的LSD排序方法，利用“分配”和“收集”兩種運算對單關鍵字進行排序。在這種方法中，把單關鍵字Ki

看成是一個d元組：其中的每一個分量(1

jd)也可看成是一個關鍵字。10.6.2鏈式基數排序46數據結構第10章內部排序共107頁，您現在瀏覽的是第46頁!如果對于所有對象的關鍵字K0,K1,…,Kn-1，依次對各位的分量，讓j=d,d-1,…,1，分別用這種“分配”、“收集”的運算逐趟進行排序，在最后一趟“分配”、“收集”完成后，所有對象就按其關鍵字的值從小到大排好序了。各隊列采用鏈式隊列結構，分配到同一隊列的關鍵字用鏈接指針鏈接起來。每一隊列設置兩個隊列指針：intfront[radix]指示隊頭，intrear[radix]指向隊尾。47數據結構第10章內部排序共107頁，您現在瀏覽的是第47頁!例1初始狀態：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一趟收集：靜態鏈表基數排序的“分配”與“收集”過程趟48數據結構第10章內部排序共107頁，您現在瀏覽的是第48頁!008063083109184269278505589930三趟收集：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二趟收集：靜態鏈表基數排序的“分配”與“收集”過程第三趟49數據結構第10章內部排序共107頁，您現在瀏覽的是第49頁!靜態鏈表基數排序的“分配”與“收集”過程第二趟614921485637738101215530790306第二趟分配（按次低位i=2）re[0]re[1]re[2]re[3]re[4]re[5]re[6]re[7]re[8]re[9]614738921485637101215530790306fr[0]fr[1]fr[2]fr[3]fr[4]fr[5]fr[6]fr[7]fr[8]fr[9]第二趟收集53079092110161448521530663773850數據結構第10章內部排序共107頁，您現在瀏覽的是第50頁!算法分析若每個關鍵字有d位，需要重復執行d趟“分配”與“收集”。每趟對n個對象進行“分配”，對radix個隊列進行“收集”。總時間復雜度為O(d(n+radix))。若基數radix相同，對于對象個數較多而關鍵字位數較少的情況，使用鏈式基數排序較好。基數排序需要增加n+2radix個附加鏈接指針。基數排序是穩定的排序方法。51數據結構第10章內部排序共107頁，您現在瀏覽的是第51頁!f[0]=0e[0]=0f[1]=0e[1]=0f[2]=0e[2]=0f[3]=0e[3]=0f[4]=0e[4]=0f[5]=0e[5]=0f[6]=0e[6]=0f[7]=0e[7]=0f[8]=0e[8]=0f[9]=0e[9]=01344779104930063083184505278008109589269^3106719258一趟收集：310162587505008109930063269278083184589^9243811065二趟收集：動態鏈表基數排序的“分配”與“收集”過程第二趟52數據結構第10章內部排序共107頁，您現在瀏覽的是第52頁!小結需要復習的知識點排序的基本概念排序的基本概念關鍵字、初始關鍵字排列關鍵字比較次數、數據移動次數穩定性附加存儲插入排序直接插入排序和折半插入排序、希爾排序的算法用例子說明直接插入排序、折半插入排序、希爾排序的過程排序的性能分析

53數據結構第10章內部排序共107頁，您現在瀏覽的是第53頁!三種選擇排序的性能分析

用簡單選擇排序在一個待排序區間中選出最小的數據時，與區間個數據對調，不是順次后移。這導致方法不穩定。

當在n個數據（n很大）中選出最小的58個數據時，樹形選擇最快。樹形選擇排序算法將待排序數據個數n補足到2的k次冪

2k-1<n

2k在堆排序中將待排序的數據組織成完全二叉樹的順序存儲。54數據結構第10章內部排序共107頁，您現在瀏覽的是第54頁!歸并排序對待排序關鍵字的初始排列不敏感，故排序速度較穩定。55數據結構第10章內部排序共107頁，您現在瀏覽的是第55頁!注：大多數排序算法都是針對順序表結構的(便于直接移動元素)6.順序存儲（順序表）的抽象數據類型如何表示？Typedefstruct{//定義每個記錄（數據元素）的結構KeyTypekey;//關鍵字

InfoTypeotherinfo;//其它數據項}RecordType;#defineMAXSIZE20//設記錄不超過20個typedefintKeyType;//設關鍵字為整型量（int型）Typedefstruct{//定義順序表的結構RecordTyper[MAXSIZE+1];//存儲順序表的向量，r[0]一般作哨兵或緩沖區intlength;//順序表的長度}SqList;56數據結構第10章內部排序共107頁，您現在瀏覽的是第56頁!10.2插入排序插入排序的基本思想是：每步將一個待排序的對象，按其關鍵字大小，插入到前面已經排好序的一組對象的適當位置上，直到對象全部插入為止。插入排序的基本操作：

將記錄R[i]插入到有序子序列R[1..i-1]中，使記錄的有序序列從R[1..i-1]變為R[1..i]。顯然，完成這個“插入”需分三步進行：1．查找R[i]的插入位置j+1；2．將R[j+1..i-1]中的記錄后移一個位置；3．將R[i]復制到R[j+1]的位置上。57數據結構第10章內部排序共107頁，您現在瀏覽的是第57頁!1)直接插入排序新元素插入到哪里？例1：關鍵字序列T=(13，6，3，31，9，27，5，11)，請寫出直接插入排序的中間過程序列。【13】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】

在已形成的有序表中線性查找，并在適當位置插入，把原來位置上的元素向后順移。最簡單的排序法！58數據結構第10章內部排序共107頁，您現在瀏覽的是第58頁!直接插入排序算法的三個要點：1．從R[i-1]起向前順序查找，監視哨設置在R[0]R[0]=R[i];//設置“哨兵”for(j=i-1;R[0].key<R[j].key;--j);//從后往前找returnj+1;//返回R[i]的插入位置為j+12．對于在查找過程中找到的關鍵字不小于R[i].key的記錄，在查找的同時實現記錄向后移動；for(j=i-1;R[0].key<R[j].key;--j)R[j+1]=R[j]3．i=2，3，…,n,實現整個序列的排序。59數據結構第10章內部排序共107頁，您現在瀏覽的是第59頁!若設待排序的對象個數為n，則算法需要進行n-1次插入。最好情況下，排序前對象已經按關鍵字大小從小到大有序，每趟只需與前面的有序對象序列的最后一個對象的關鍵字比較1次。因此，總的關鍵字比較次數為n-1。直接插入排序的算法分析60數據結構第10章內部排序共107頁，您現在瀏覽的是第60頁!若待排序對象序列中出現各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關鍵字比較次數和對象移動次數約為n2/4。因此，直接插入排序的時間復雜度為o(n2)。直接插入排序是一種穩定的排序方法。61數據結構第10章內部排序共107頁，您現在瀏覽的是第61頁!折半插入排序算法描述如下:voidBInserSort(SqList&L){//對順序表L作折半插入排序。for(i=2;i<=L.length;++i){L.r[0]=L.r[i];while(low<=high) {m=(low+high)/2; if(LT(L.r[0].key,L.r[m].key))high=m-1;

elselow=m+1;

} //whilefor(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j]; //記錄后移L.r[j+1]=L.r[0]; //插入}//for}//BInsertSort62數據結構第10章內部排序共107頁，您現在瀏覽的是第62頁!折半插入排序的算法分析折半查找比順序查找快，所以折半插入排序就平均性能來說比直接插入排序要快。在插入第i

個對象時，需要經過log2i+1次關鍵字比較，才能確定它應插入的位置。因此，將n

個對象用折半插入排序所進行的關鍵字比較次數為：n*log2n折半插入排序是一個穩定的排序方法。63數據結構第10章內部排序共107頁，您現在瀏覽的是第63頁!1例：關鍵字序列T=(21，25，49，25*，16，08)，請寫出表插入排序的具體實現過程。解：假設該序列（結構類型)已存入有序鏈表SL[7]中，將SL[0]作為表頭結點。則算法執行過程為：i關鍵字SL[i].key指針SL[i].next0MaxInt121225349425*516608指向第1個元素指向頭結點初態i=1i=2i=3i=4i=5i=603456503102*表示后一個25靜態鏈表64數據結構第10章內部排序共107頁，您現在瀏覽的是第64頁!4）希爾（shell）排序（又稱縮小增量排序）基本思想：先將整個待排記錄序列分割成若干子序列,分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。技巧：子序列的構成不是簡單地“逐段分割”，而是將相隔某個增量dk的記錄組成一個子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。優點：讓關鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。65數據結構第10章內部排序共107頁，您現在瀏覽的是第65頁!voidShellSort(SqList&L，intdlta[]，intt){

//按增量序列dlta[0…t-1]對順序表L作Shell排序for(k=0；k<t；++k)

ShellInsert(L，dlta[k])；

//增量為dlta[k]的一趟插入排序}//ShellSort時間效率：空間效率：O（1）—因為僅占用1個緩沖單元算法的穩定性：不穩定—因為49*排序后卻到了49的前面希爾排序算法（主程序）參見教材P272O(n1.3）—經驗公式dk值依次裝在dlta[t]中66數據結構第10章內部排序共107頁，您現在瀏覽的是第66頁!課堂練習：1.欲將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關鍵字按字母升序重排，則初始步長為4的希爾排序一趟的結果是？答：原始序列：

Q,H,C,Y,P,A,M,S,R,D,F,X

shell一趟后：P,Q,R,A,D,H,C,F,M,S,X,Y67數據結構第10章內部排序共107頁，您現在瀏覽的是第67頁!原始序列：

256，301，751，129，937，863，742，694，076，438[256，301]，751，129，937，863，742，694，076，438[256，301，751]，129，937，863，742，694，076，438[129，256，301，751]，937，863，742，694，076，438[129，256，301，751，937]，863，742，694，076，438[129，256，301，751，863，937]，742，694，076，438[129，256，301，742，751，863，937]，694，076，438[129，256，301，694，742，751，863，937]，076，438[076，129，256，301，694，742，751，863，937]，438[076，129，256，301，438，694，742，751，863，937]直接插入排序第1趟第2趟第3趟第4趟第5趟第6趟第7趟第8趟第9趟68數據結構第10章內部排序共107頁，您現在瀏覽的是第68頁!10.3快速排序

兩兩比較待排序記錄的關鍵字，如果發生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序為止。快速排序的主要算法有：1)冒泡排序2)快速排序快速排序的基本思想是：69數據結構第10章內部排序共107頁，您現在瀏覽的是第69頁!冒泡排序的算法分析時間效率：O（n2)—因為要考慮最壞情況空間效率：O（1）—只在交換時用到一個緩沖單元穩定性：穩定—25和25*在排序前后的次序未改變詳細分析：最好情況：初始排列已經有序，只執行一趟起泡，做n-1次關鍵字比較，不移動對象。最壞情形：初始排列逆序，算法要執行n-1趟起泡，第i趟(1

i

n)做了n-i

次關鍵字比較，執行了n-i

次對象交換。此時的比較總次數KCN和記錄移動次數RMN為：70數據結構第10章內部排序共107頁，您現在瀏覽的是第70頁!()，設以首元素為樞軸中心例1：關鍵字序列T=(21，25，49，25*，16，08），請寫出快速排序的算法步驟。21，25，49，25*，16，08初態：第1趟：第2趟：第3趟：討論：1.這種不斷劃分子表的過程，計算機如何自動實現？2.“快速排序”是否真的比任何排序算法都快？08，16，21，25，

25*，(49)2116，08，()25，25*，49(08)，16，21，25，(25*，49)71數據結構第10章內部排序共107頁，您現在瀏覽的是第71頁!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];//將比樞軸大的記錄交換到高端

} returnlow;//返回樞軸記錄所在位置。}//Partition72數據結構第10章內部排序共107頁，您現在瀏覽的是第72頁!j從高端掃描尋找小于pivot的元素i從低端掃描尋找大于pivot的元素i=low;j=high;r[0]=r[low];pivot=r[low].key;i<ji<j&&r[j].key>=pivot--j;r[i]=r[j];i<j&&r[i].key<=pivot--i;r[j]=r[i];r[i]=r[0];returnok;YYYNNN一趟快速排序算法流程圖73數據結構第10章內部排序共107頁，您現在瀏覽的是第73頁!例3：以關鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執行快速算法的各趟排序結束時，關鍵字序列的狀態。原始序列：

256，301，751，129，937，863，742，694，076，438快速排序第1趟第2趟第3趟第4趟256，301，751，129，937，863，742，694，076，438076，129，256，751，937，863，742，694，301，438要求模擬算法實現步驟256076301129751256076，129，256，438，301，694，742，694，863，937751076，129，256，438，301，694，742，751，863，937076，129，256，301，301，694，742，751，863，937438076，129，256，301，438，694，742，751，863，937時間效率：O(nlog2n)—因為每趟確定的元素呈指數增加空間效率：O（log2n）—因為算法的遞歸性，要用到棧空間穩定性：不穩定—因為可選任一元素為樞軸。74數據結構第10章內部排序共107頁，您現在瀏覽的是第74頁!如果每次劃分對一個對象定位后，該對象的左側子序列與右側子序列的長度相同，則下一步將是對兩個長度減半的子序列進行排序，這是最理想的情況。此時，快速排序的趟數最少。75數據結構第10章內部排序共107頁，您現在瀏覽的是第75頁!討論2.“快速排序”是否真的比任何排序算法都快？設每個子表的支點都在中間（比較均衡），則：第1趟比較，可以確定1個元素的位置；第2趟比較（2個子表），可以再確定2個元素的位置；第3趟比較（4個子表），可以再確定4個元素的位置；第4趟比較（8個子表），可以再確定8個元素的位置；……只需log2n＋1趟便可排好序。——基本上是！因為每趟可以確定的數據元素是呈指數增加的！76數據結構第10章內部排序共107頁，您現在瀏覽的是第76頁!

選擇排序的基本思想是：每一趟(例如第i趟，i=1,…,n-1)在后面的n-i+1個待排序對象中選出關鍵字最小的對象,作為有序對象序列的第i個對象。待到第n-1趟作完，待排序對象只剩下1個，就不用再選了。10.4選擇排序(SelectionSort)10.4.1簡單選擇排序

10.4.2樹形選擇排序10.4.3

堆排序77數據結構第10章內部排序共107頁，您現在瀏覽的是第77頁!簡單選擇排序的算法voidSelectSort(SqList&L){for(inti=1;i<L.length;++i)

{ j=SelectMinKey(L,i);//在L.r[i..L.length]中選擇key最小的記錄 if(i!=j)L.r[i]←→L.r[j];//與第i個記錄交換

}}78數據結構第10章內部排序共107頁，您現在瀏覽的是第78頁!4925*01234525*i=52516084925*4921結果i=408162521最小者25*無交換最小者25無交換25211608各趟排序后的結果79數據結構第10章內部排序共107頁，您現在瀏覽的是第79頁!對象的移動次數與對象序列的初始排列有關。當這組對象的初始狀態是按其關鍵字從小到大有序的時候，對象的移動次數RMN=0，達到最少。最壞情況是每一趟都要進行交換，總的對象移動次數為RMN=3(n-1)。直接選擇排序是一種不穩定的排序方法。80數據結構第10章內部排序共107頁，您現在瀏覽的是第80頁!08Winner2108086325*2121254925*16086381數據結構第10章內部排序共107頁，您現在瀏覽的是第81頁!08Winner(勝者)2108086325*2121254925*160863

形成初始勝者樹（最小關鍵字上升到根）a[0]關鍵字比較次數:682數據結構第10章內部排序共107頁，您現在瀏覽的是第82頁!21Winner(勝者)21636325*2121254925*63輸出亞軍并調整勝者樹后樹的狀態a[2]關鍵字比較次數:283數據結構第10章內部排序共107頁，您現在瀏覽的是第83頁!25*Winner(勝者)25*636325*4925*63輸出第四名并調整勝者樹后樹的狀態a[4]關鍵字比較次數:284數據結構第10章內部排序共107頁，您現在瀏覽的是第84頁!算法分析錦標賽排序構成的樹是滿的完全二叉樹，其深度為log2(n+1)，其中n為待排序元素個數。除次選擇具有最小關鍵字的對象需要進行n-1次關鍵字比較外，重構勝者樹選擇具有次小、再次小關鍵字對象所需的關鍵字比較次數均為O(log2n)。總關鍵字比較次數為O(nlog2n)。對象的移動次數不超過關鍵字的比較次數，所以錦標賽排序總的時間復雜度為O(nlog2n)。這種排序方法雖然減少了許多排序時間，但是使用了較多的附加存儲。錦標賽排序是一個穩定的排序方法。85數據結構第10章內部排序共107頁，您現在瀏覽的是第85頁!堆排序(HeapSort)給定一組關鍵字，初始態存儲時是一個完全二叉樹小頂堆的建立：對n/21,的元素依次進行篩選：若ki<=k2i且ki<=k2i+1，則不換若ki>k2i(k2i+1)且ki<=k2i+1(k2i)，則ki與k2i（k2i+1）交換若ki>k2i且ki>k2i+1，則ki與較小的哪個交換若(k2i=k2i+1)<ki,則ki與k2i交換（大頂堆剛好相反）對堆的篩選與建立的重復交替86數據結構第10章內部排序共107頁，您現在瀏覽的是第86頁!212525*491608123456i492525*16210813654221254925*160849252125*1608i=1時的局部調整形成大頂堆i=2時的局部調整87數據結構第10章內部排序共107頁，您現在瀏覽的是第87頁!基于初始堆進行堆排序最大堆的個對象r[1]具有最大的關鍵字，將r[1]與r[n]對調，把具有最大關鍵字的對象交換到最后，再對前面的n-1個對象，使用堆的調整算法HeapAdjust(1,n-1)，重新建立最大堆。結果具有次最大關鍵字的對象又上浮到堆頂，即r[1]位置。再對調r[1]和r[n-1]，調用HeapAdjust(1,n-2)，對前n-2個對象重新調整，…。如此反復執行，最后得到全部排序好的對象序列。這個算法即堆排序算法。88數據結構第10章內部排序共107頁，您現在瀏覽的是第88頁!2525*082116491234561625*082521491365422525*210816491625*210825

49交換1號與5號對象,5號對象就位從1號到5號重新調整為最大堆89數據結構第10章內部排序共107頁，您現在瀏覽的是第89頁!211625*082549123456081625*25214913654221160825*

25

49081621

25*

25

49交換1號與3號對象,3號對象就位從1號到3號重新調整為最大堆90數據結構第10章內部排序共107頁，您現在瀏覽的是第90頁!堆排序的算法voidHeapSort(HeapType&H){ElemTypetemp;for(inti=H.length/2;i>0;--i) HeapAdjust(H,i,H.length);for(i=H.length;i>1;--i){ temp=H.r[1]; H.r[1]=H.r[i]; H.r[i]=temp; HeapAdjust(H,1,i-1);}}91數據結構第10章內部排序共107頁，您現在瀏覽的是第91頁!在第二個for循環中，調用了n-1次HeapAdjust()算法，該循環的計算時間為O(nlog2n)。因此，堆排序的時間復雜性為O(nlog2n)。該算法的附加存儲主要是在第二個for循環中用來執行對象交換時所用的一個臨時對象。因此，該算法的空間復雜性為O(1)。堆排序是一個不穩定的排序方法。92數據結構第10章內部排序共107頁，您現在瀏覽的是第92頁!歸并排序示例二趟歸并排序后：[33516296][172887]

初始關鍵字序列：[51]

[33]

[62]

[96]

[87]

[17][28]一趟歸并排序后：[3351]

[6296]

[1787][28]三趟歸并排序后：[1728335162

8796]

93數據結構第10章內部排序共107頁，您現在瀏覽的是第93頁!算法分析在歸并排序算法中，對象關鍵字的比較次數為O(nlog2n)。算法總的時間復雜度為O(nlog2n)。歸并排序占用附加存儲較多，需要另外一個與原待排序對象數組同樣大小的輔助數組。這是這個算法的缺點。歸并排序是一個穩定的排序方法。94數據結構第10章內部排序共107頁，您現在瀏覽的是第94頁!這就是多關鍵字排序。排序后形成的有序序列叫做詞典有序序列。對于上例兩關鍵字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。一般情況下，假定有一個n個對象的序列{V0,V1,…,Vn-1}，且每個對象Vi中含有d個關鍵字如果對于序列中任意兩個對象Vi和Vj(0

i<j

n-1)都滿足：95數據結構第10章內部排序共107頁，您現在瀏覽的是第95頁!再分別對每組中對象根據關鍵字K2進行排序，按K2值的不同，再分成若干個更小的子組，每個子組中的對象具有相同的K1和K2值。依此重復，直到對關鍵字Kd完成排序為止。最后，把所有子組中的對象依次連接起來，就得到一個有序的對象序列。96數據結構第10章內部排序共107頁，您現在瀏覽的是第96頁!LSD和MSD方法也可應用于對一個關鍵字進行的排序。此時可將單關鍵字Ki看作是一個子關鍵字組：97數據結構第10章內部排序共107頁，您現在瀏覽的是第97頁!分量(1

j

d)有radix種取值，則稱radix為基數。例如，關鍵字984可以看成是一個3元組(9,8,4)，每一位有0,1,…,9等10種取值，基數radix=10。關鍵字‘data’可以看成是一個4元組(d,a,t,a)，每一位有‘a’,‘b’,…,‘z’等26種取值，radix=26。針對d元組中的每一位分量，把對象序列中的所有對象,按的取值，