第10章-排序數(shù)據(jù)結(jié)構(gòu)課件

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容110.1概述10.2插入排序10.3交換排序10.4選擇排序10.5歸并排序10.6基數(shù)排序第10章內(nèi)部排序210.1概述第10章內(nèi)部排序210.1概述1.什么是排序？將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。

2.排序的目的是什么？存放在數(shù)據(jù)表中按關(guān)鍵字排序3.排序算法的好壞如何衡量？時間效率——排序速度（即排序所花費(fèi)的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小穩(wěn)定性

A和B的關(guān)鍵字——若兩個記錄值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的?！阌诓檎?！310.1概述1.什么是排序？2.排序的目的是什么？4.什么叫內(nèi)部排序？什么叫外部排序？

——若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；——若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。注：外部排序時，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時放入外存，顯然外部排序要復(fù)雜得多。

5.待排序記錄在內(nèi)存中怎樣存儲和處理？①順序排序——排序時直接移動記錄；②鏈表排序——排序時只移動指針；③地址排序——排序時先移動地址，最后再移動記錄。注：地址排序中可以增設(shè)一維數(shù)組來專門存放記錄的地址。44.什么叫內(nèi)部排序？什么叫外部排序？——若待排序記錄都在注：大多數(shù)排序算法都是針對順序表結(jié)構(gòu)的(便于直接移動元素)6.順序存儲（順序表）的抽象數(shù)據(jù)類型如何表示？Typedefstruct{//定義每個記錄（數(shù)據(jù)元素）的結(jié)構(gòu)KeyTypekey;//關(guān)鍵字

InfoTypeotherinfo;//其它數(shù)據(jù)項(xiàng)}RecordType;Typedefstruct{//定義順序表的結(jié)構(gòu)RecordTyper[MAXSIZE+1];//存儲順序表的向量

//r[0]一般作哨兵或緩沖區(qū)intlength;//順序表的長度}SqList;#defineMAXSIZE20//設(shè)記錄不超過20個typedefintKeyType;//設(shè)關(guān)鍵字為整型量（int型）5注：大多數(shù)排序算法都是針對順序表結(jié)構(gòu)的(便于直接移動元素)67.內(nèi)部排序的算法有哪些？——按排序的規(guī)則不同，可分為5類：插入排序交換排序（重點(diǎn)是快速排序）選擇排序歸并排序基數(shù)排序d＝關(guān)鍵字的位數(shù)(長度)——按排序算法的時間復(fù)雜度不同，可分為3類：簡單的排序算法：時間效率低，O(n2)先進(jìn)的排序算法:時間效率高，O(nlog2n)基數(shù)排序算算法：時間效率高，O(d×n)67.內(nèi)部排序的算法有哪些？——按排序的規(guī)則不同，可分為510.2插入排序插入排序的基本思想是：插入排序有多種具體實(shí)現(xiàn)算法：1)直接插入排序2)折半插入排序3)表插入排序4)希爾排序每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。710.2插入排序插入排序的基本思想是：插入排序有多種具體實(shí)1)直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列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】

在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。最簡單的排序法！81)直接插入排序新元素插入到哪里？例1：關(guān)鍵字序列T=（直接插入排序算法

VoidInsertSort(SqList&L){for(i=2;i<=L.length;++i){L.r[0]=L.r[i];//設(shè)定監(jiān)視哨

j=i-1;if(LT(L.r[i].key,L.r[i-1].key))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];//插入記錄}9直接插入排序算法

VoidInsertSort(SqLis例2：關(guān)鍵字序列T=（21，25，49，25*，16，08），

請寫出直接插入排序的具體實(shí)現(xiàn)過程。*表示后一個25i=121254925*16080123456暫存21i=2i=3i=5i=4i=625252549494925*25*49161625*080849解：假設(shè)該序列已存入一維數(shù)組V[7]中，將V[0]作為緩沖或暫存單元（Temp）。則程序執(zhí)行過程為：21254925*21初態(tài)：164925*25211608完成!時間效率：O(n2)——因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為（0＋1＋…＋n-1)→O(n2)。其他情況下還要加上移動元素的次數(shù)?？臻g效率：O（1）——因?yàn)閮H占用1個緩沖單元算法的穩(wěn)定性：穩(wěn)定——因?yàn)?5*排序后仍然在25的后面。10例2：關(guān)鍵字序列T=（21，25，49，25*，16，08若設(shè)待排序的對象個數(shù)為n，則算法需要進(jìn)行n-1次插入。最好情況下，排序前對象已經(jīng)按關(guān)鍵碼大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械淖詈笠粋€對象的關(guān)鍵碼比較1次，移動2次對象。因此，總的關(guān)鍵碼比較次數(shù)為n-1，對象移動次數(shù)為2(n-1)。直接插入排序的算法分析11若設(shè)待排序的對象個數(shù)為n，則算法需要進(jìn)行n-1次插入。直接插最壞情況下，第i趟插入時，第i個對象必須與前面i-1個對象都做關(guān)鍵碼比較，并且每做1次比較就要做1次數(shù)據(jù)移動。則總的關(guān)鍵碼比較次數(shù)KCN和對象移動次數(shù)RMN分別為12最壞情況下，第i趟插入時，第i個對象必須與前面i-1個對象都若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵碼比較次數(shù)和對象移動次數(shù)約為n2/4。因此，直接插入排序的時間復(fù)雜度為o(n2)。直接插入排序是一種穩(wěn)定的排序方法。13若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好2）折半插入排序優(yōu)點(diǎn)：比較的次數(shù)大大減少，全部元素比較次數(shù)僅為O(nlog2n)。時間效率：雖然比較次數(shù)大大減少，可惜移動次數(shù)并未減少，所以排序效率仍為O(n2)?？臻g效率：

O（1）穩(wěn)定性：穩(wěn)定對應(yīng)程序見教材P267（僅用于順序表）新元素插入到哪里？討論：若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？折半插入排序呢？答：直接插入不僅可行，而且還無需移動元素，時間效率更高！折半插入排序的改進(jìn)——2-路插入排序267在已形成的有序表中折半查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。但鏈表無法“折半”！142）折半插入排序優(yōu)點(diǎn)：比較的次數(shù)大大減少，全部元素比較次數(shù)折半插入排序的算法分析折半查找比順序查找快，所以折半插入排序就平均性能來說比直接插入排序要快。在插入第i

個對象時，需要經(jīng)過log2i+1次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置。因此，將n

個對象用折半插入排序所進(jìn)行的關(guān)鍵碼比較次數(shù)為：n*log2n折半插入排序是一個穩(wěn)定的排序方法。15折半插入排序的算法分析折半查找比順序查找快，所以折半插入排序3）表插入排序基本思想：在順序存儲結(jié)構(gòu)中，給每個記錄增開一個指針分量，在排序過程中將指針內(nèi)容逐個修改為已經(jīng)整理（排序）過的后繼記錄地址。優(yōu)點(diǎn)：在排序過程中不移動元素，只修改指針?；貞洠孩阪湵砼判颉判驎r只移動指針；③地址排序——排序時先移動地址，最后再移動記錄。此方法具有鏈表排序和地址排序的特點(diǎn)。163）表插入排序基本思想：在順序存儲結(jié)構(gòu)中，給每個記錄增開一個1例：關(guān)鍵字序列T=(21，25，49，25*，16，08），

請寫出表插入排序的具體實(shí)現(xiàn)過程。解：假設(shè)該序列（結(jié)構(gòu)類型)已存入一維數(shù)組V[7]中，將V[0]作為表頭結(jié)點(diǎn)。則算法執(zhí)行過程為：指向第1個元素指向頭結(jié)點(diǎn)初態(tài)i=1i=2i=3i=4i=5i=603456503102*表示后一個25171例：關(guān)鍵字序列T=(21，25，49，25*，16，08intLinkInsertSort(staticlinklis<Type>&list){

list.v[0].Key=MaxNum;

list.v[0].Link=1;

list.v[1].Link=0; //形成循環(huán)鏈表表插入排序的算法for(inti=2;i<=list.length;i++)

{

int

current=list.v[0].Link;//current=當(dāng)前記錄指針intpre=0; //pre=當(dāng)前記錄current的前驅(qū)指針while(list.v[current].Key<=list.v[i].Key){

pre=current;//current指針準(zhǔn)備后移,pre跟上；

current=list.v[current].Link;}

//找插入位置(即p=p->link)list.v[i].Link=current;//新記錄v[i]找到合適序位開始插入

list.v[pre].Link=i;//在pre與current之間鏈入

}}18intLinkInsertSort(staticlin表插入排序算法分析：①無需移動記錄，只需修改2n次指針值。但由于比較次數(shù)沒有減少，故時間效率仍為O(n2)。②空間效率肯定低，因?yàn)樵鲩_了指針分量（但在運(yùn)算過程中沒有用到更多的輔助單元）。③穩(wěn)定性：25和25*排序前后次序未變，穩(wěn)定。討論：此算法得到的只是一個有序鏈表，查找記錄時只能滿足順序查找方式。改進(jìn)：可以根據(jù)表中指針線索，很快對所有記錄重排，形成真正的有序表（順序存儲方式），從而能滿足折半查找方式。具體實(shí)現(xiàn)見教材P269。19表插入排序算法分析：①無需移動記錄，只需修改2n次指針值。4）希爾（shell）排序（又稱縮小增量排序）基本思想：先將整個待排記錄序列分割成若干子序列,分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進(jìn)行一次直接插入排序。技巧：子序列的構(gòu)成不是簡單地“逐段分割”，而是將相隔某個增量dk的記錄組成一個子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有序時，再用直接插入排序處理，時間效率會高很多。204）希爾（shell）排序（又稱縮小增量排序）基本思想：先將38例：關(guān)鍵字序列T=(49，38，65，97,76,13,27,49*，55,04），請寫出希爾排序的具體實(shí)現(xiàn)過程。初態(tài)：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*975576042738

65

49*9755135576045513270427044949*4949*76387665659797551327044949*3876659713270449*7697算法分析：開始時dk

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

值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。r[i]2138例：關(guān)鍵字序列T=(49，38，65，97,76,voidShellSort(SqList&L，intdlta[]，intt){

//按增量序列dlta[0…t-1]對順序表L作Shell排序for(k=0；k<t；++k)ShellSort(L，dlta[k])；//增量為dlta[k]的一趟插入排序}//ShellSort時間效率：空間效率：O（1）——因?yàn)閮H占用1個緩沖單元算法的穩(wěn)定性：不穩(wěn)定——因?yàn)?9*排序后卻到了49的前面希爾排序算法（主程序）參見教材P272O(n1.25）～O（1.6n1.25）——經(jīng)驗(yàn)公式dk值依次裝在dlta[t]中22voidShellSort(SqList&L，int附：希爾排序算法分析對特定的待排序?qū)ο笮蛄校梢詼?zhǔn)確地估算關(guān)鍵碼的比較次數(shù)和對象移動次數(shù)。但想要弄清關(guān)鍵碼比較次數(shù)和對象移動次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整的數(shù)學(xué)分析，還沒有人能夠做到。Knuth利用大量的實(shí)驗(yàn)統(tǒng)計資料得出，當(dāng)n很大時，關(guān)鍵碼平均比較次數(shù)和對象平均移動次數(shù)大約在n1.25

到1.6n1.25

的范圍內(nèi)。這是在利用直接插入排序作為子序列排序方法的情況下得到的。23附：希爾排序算法分析對特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算關(guān)voidShellInsert(SqList&L，int

dk){

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

r[0]=r[i]；

for(j=i-dk;j>0&&(r[0].key<r[j].key);j=j-dk) r[j+dk]=r[j]；r[j+dk]=r[0]；}}希爾排序算法（其中某一趟的排序操作）參見教材P272//對順序表L進(jìn)行一趟增量為dk的Shell排序，dk為步長因子//開始將r[i]插入有序增量子表//暫存在r[0]//關(guān)鍵字較大的記錄在子表中后移//在本趟結(jié)束時將r[i]插入到正確位置24voidShellInsert(SqList&L，i課堂練習(xí)：1.欲將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關(guān)鍵碼按字母升序重排，則初始步長為4的希爾排序一趟的結(jié)果是？答：原始序列：Q,H,C,Y,P,A,M,S,R,D,F,X

shell一趟后：2.以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，分別寫出執(zhí)行以下算法的各趟排序結(jié)束時，關(guān)鍵字序列的狀態(tài)，并說明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實(shí)現(xiàn)？①直接插入排序②希爾排序（取dk=5,3,1）P,Q,R,A,D,H,C,F,M,S,X,Y答：顯然，直接插入排序方法易于在鏈表上實(shí)現(xiàn)；但希爾排序方法因?yàn)槭前丛隽窟x擇記錄，不易于在鏈表上實(shí)現(xiàn)。

兩種排序方法的中間狀態(tài)分別描述如后：25課堂練習(xí)：1.欲將序列（Q,H,C,Y,P,A原始序列：

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趟26原始序列：256，301，751，129，937，863，原始序列：

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，93727原始序列：256，301，751，129，937，863，10.3交換排序兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序?yàn)橹?。交換排序的主要算法有：1)冒泡排序2)快速排序交換排序的基本思想是：2810.3交換排序1)冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點(diǎn)：每趟結(jié)束時，不僅能擠出一個最大值到最后面位置，還能同時部分理順其他元素；一旦下趟沒有交換發(fā)生，還可以提前結(jié)束排序。前提：順序存儲結(jié)構(gòu)

例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請寫出冒泡排序的具體實(shí)現(xiàn)過程。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初態(tài)：第1趟第2趟第3趟第4趟第5趟291)冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前冒泡排序的算法分析時間效率：O（n2)—因?yàn)橐紤]最壞情況空間效率：O（1）—只在交換時用到一個緩沖單元穩(wěn)定性：

穩(wěn)定—25和25*在排序前后的次序未改變詳細(xì)分析：最好情況：初始排列已經(jīng)有序，只執(zhí)行一趟起泡，做n-1次關(guān)鍵碼比較，不移動對象。最壞情形：初始排列逆序，算法要執(zhí)行n-1趟起泡，第i趟(1

i

n)做了n-i

次關(guān)鍵碼比較，執(zhí)行了n-i

次對象交換。此時的比較總次數(shù)KCN和記錄移動次數(shù)RMN為：30冒泡排序的算法分析時間效率：O（n2)—因?yàn)橐紤]最壞情況2）快速排序從待排序列中任取一個元素(例如取第一個)作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個子表；然后再對各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個子表的元素只剩一個。此時便為有序序列了?；舅枷耄簝?yōu)點(diǎn)：因?yàn)槊刻丝梢源_定不止一個元素的位置，而且呈指數(shù)增加，所以特別快！前提：順序存儲結(jié)構(gòu)

312）快速排序從待排序列中任取一個元素(()，設(shè)以首元素為樞軸中心例1：關(guān)鍵字序列T=(21，25，49，25*，16，08），請寫出快速排序的算法步驟。21，25，49，25*，16，08初態(tài)：第1趟：第2趟：第3趟：討論：1.這種不斷劃分子表的過程，計算機(jī)如何自動實(shí)現(xiàn)？2.“快速排序”是否真的比任何排序算法都快？08，16，21，25，

25*，(49)2116，08，()25，25*，49(08)，16，21，25，(25*，49)32()，設(shè)以首元素為樞軸中心例1.這種不斷劃分子表的過程，計算機(jī)如何自動實(shí)現(xiàn)？編程時：①每一趟的子表的形成是采用從兩頭向中間交替式逼近法；②由于每趟中對各子表的操作都相似，主程序可采用遞歸算法。見教材P275intPartition(SqList&L,intlow,inthigh){//一趟快排//交換子表r[low…h(huán)igh]的記錄，使支點(diǎn)（樞軸）記錄到位，并返回其位置。返回時，在支點(diǎn)之前的記錄均不大于它，支點(diǎn)之后的記錄均不小于它。

r[0]=r[low];//以子表的首記錄作為支點(diǎn)記錄，放入r[0]單元（續(xù)下頁）一趟快速排序算法（針對一個子表的操作）331.這種不斷劃分子表的過程，計算機(jī)如何自動實(shí)現(xiàn)？編程時：見教pivotkey=r[low].key;//取支點(diǎn)的關(guān)鍵碼存入pivotkey變量while(low<high){

//從表的兩端交替地向中間掃描 while(low<high&&r[high].key>=pivotkey)--high; r[low]=r[high];//將比支點(diǎn)小的記錄交換到低端； while(low<high&&r[low].key<=pivotkey)++low; r[high]=r[low];//將比支點(diǎn)大的記錄交換到高端；

}r[low]=r[0];//支點(diǎn)記錄到位； returnlow;//返回支點(diǎn)記錄所在位置。}//Partition34pivotkey=r[low].key;//取支點(diǎn)的關(guān)鍵Low=high=3，本趟停止，將支點(diǎn)定位并返回位置信息例2：關(guān)鍵字序列T=(21，25，49，25*，16，08），請寫出快速排序算法的一趟實(shí)現(xiàn)過程。highlow210825164925*321pivotkey=2108251649(08

，16）21（25*，49，25）25*跑到了前面，不穩(wěn)定！35Low=high=3，本趟停止，將支點(diǎn)定位并返回位置信息例2j從高端掃描尋找小于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一趟快速排序算法流程圖36j從高端掃描i從低端掃描i=low;j=high;r[0]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…h(huán)igh]

作快速排序//一趟快排，將r[]一分為二//在左子區(qū)間進(jìn)行遞歸快排，直到長度為1//在右子區(qū)間進(jìn)行遞歸快排，直到長度為1//QSort新的lowvoidQuickSort(SqList&L){QSort(L,

1,L.length

);}對順序表L進(jìn)行快速排序的操作函數(shù)為：37voidQSort(SqList&L,int例3：以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行快速算法的各趟排序結(jié)束時，關(guān)鍵字序列的狀態(tài)。原始序列：

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要求模擬算法實(shí)現(xiàn)步驟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)—因?yàn)槊刻舜_定的元素呈指數(shù)增加空間效率：O（log2n）—因?yàn)樗惴ǖ倪f歸性，要用到?？臻g穩(wěn)定性：

不穩(wěn)定—因?yàn)榭蛇x任一元素為支點(diǎn)。38例3：以關(guān)鍵字序列（256，301，751，129，937，快速排序算法詳細(xì)分析：快速排序是遞歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)（新的low和high）。可以證明，函數(shù)quicksort的平均計算時間也是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明：就平均計算時間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個。最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為log2(n+1)。因此，要求存儲開銷為o(log2n)。如果每次劃分對一個對象定位后，該對象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對兩個長度減半的子序列進(jìn)行排序，這是最理想的情況。此時，快速排序的趟數(shù)最少。39快速排序算法詳細(xì)分析：快速排序是遞歸的，需要有一個棧存放每層在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個比上一次少一個對象的子序列。這樣，必須經(jīng)過n-1趟才能把所有對象定位，而且第i趟需要經(jīng)過n-i次關(guān)鍵碼比較才能找到第

i

個對象的安放位置，總的關(guān)鍵碼比較次數(shù)將達(dá)到n2/2快速排序是一個不穩(wěn)定的排序方法40在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好序的討論2.“快速排序”是否真的比任何排序算法都快？設(shè)每個子表的支點(diǎn)都在中間（比較均衡），則：第1趟比較，可以確定1個元素的位置；第2趟比較（2個子表），可以再確定2個元素的位置；第3趟比較（4個子表），可以再確定4個元素的位置；第4趟比較（8個子表），可以再確定8個元素的位置；……只需log2n＋1趟便可排好序?！旧鲜?！因?yàn)槊刻丝梢源_定的數(shù)據(jù)元素是呈指數(shù)增加的！而且，每趟需要比較和移動的元素也呈指數(shù)下降，加上編程時使用了交替逼近技巧，更進(jìn)一步減少了移動次數(shù)，所以速度特別快。教材P276有證明：快速排序的平均排序效率為O(nlog2n)；但最壞情況(例如已經(jīng)有序)下仍為O(n2),改進(jìn)措施見P277。41討論2.“快速排序”是否真的比任何排序算法都快？設(shè)每個子表10.4選擇排序選擇排序有多種具體實(shí)現(xiàn)算法：1)簡單選擇排序2)錦標(biāo)賽排序3)堆排序選擇排序的基本思想是：每一趟在后面n-i

個待排記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i個記錄。4210.4選擇排序選擇排序有多種具體實(shí)現(xiàn)算法：選擇排序的1）簡單選擇排序思路簡單：每經(jīng)過一趟比較就找出一個最小值，與待排序列最前面的位置互換即可?！紫龋趎個記錄中選擇最小者放到r[1]位置；然后，從剩余的n-1個記錄中選擇最小者放到r[2]位置；…如此進(jìn)行下去，直到全部有序?yàn)橹?。?yōu)點(diǎn)：實(shí)現(xiàn)簡單缺點(diǎn)：每趟只能確定一個元素，表長為n時需要n-1趟前提：順序存儲結(jié)構(gòu)

431）簡單選擇排序思路簡單：每經(jīng)過一趟比較就找出一個最小值，與例：關(guān)鍵字序列T=（21，25，49，25*，16，08），請給出簡單選擇排序的具體實(shí)現(xiàn)過程。原始序列：

21，25，49，25*，16，08直接選擇排序第1趟第2趟第3趟第4趟第5趟08，25，49，25*，16，2108，16,49，25*，25，2108，16,

21，25*，25，4908，16,

21，25*，25，4908，16,

21，25*，25，49時間效率：O(n2)——雖移動次數(shù)較少，但比較次數(shù)仍多。空間效率：O（1）——無需任何附加單元！算法的穩(wěn)定性：不穩(wěn)定——因?yàn)榕判驎r，25*到了25的前面。最小值08與r[1]交換位置44例：關(guān)鍵字序列T=（21，25，49，25*，16，08）簡單選擇排序的算法如下：（亦可參見教材P276）VoidSelectSort(SqList&L

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

j=SelectMinKey(L,i);if(i!=j)

r[i]r[j];}

}//SelectSort//對順序表L作簡單選擇排序//選擇第i小的記錄，并交換到位//在r[i…L.length]中選擇key最小的記錄//與第i個記錄交換討論：能否利用（或記憶）首趟的n-1次比較所得信息，從而盡量減少后續(xù)比較次數(shù)呢？

答：能！請看——錦標(biāo)賽排序和堆排序！45簡單選擇排序的算法如下：（亦可參見教材P276）VoidS2）錦標(biāo)賽排序(又稱樹形選擇排序)基本思想：與體育比賽時的淘汰賽類似。

首先對n

個記錄的關(guān)鍵字進(jìn)行兩兩比較，得到n/2個優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來。然后在這n/2個較小者之間再進(jìn)行兩兩比較，…，如此重復(fù)，直到選出最小關(guān)鍵字的記錄為止。優(yōu)點(diǎn)：減少比較次數(shù)，加快排序速度缺點(diǎn)：空間效率低例：關(guān)鍵字序列T=（21，25，49，25*，16，08，63），請給出錦標(biāo)賽排序的具體實(shí)現(xiàn)過程。462）錦標(biāo)賽排序(又稱樹形選擇排序)基本思想：與體育比賽08Winner(勝者)2108086325*2121254925*160863r[1]注：為便于自動處理，建議每個記錄多開兩個特殊分量：初態(tài)：補(bǔ)足2k(k=log2n

)個葉子結(jié)點(diǎn)勝者樹第一趟：4708Winner(勝者)2108086325*212125第二趟：082108086325*2121254925*160863161616r[2]Winner(勝者)求次小值16時,只需比較2次，即只比較log2n-1次。令其Tag＝0,不參與比較48第二趟：082108086325*2121254925*16令其Tag＝0,不參與比較第三趟：162116166325*2121254925*160863r[3]Winner(勝者)632149令其Tag＝0,不參與比較第三趟：162116166325*082108086325*2121254925*1608636321第四趟：r[4]Winner(勝者)25252550082108086325*2121254925*160863082108086325*2121254925*1608631616166321252525第五趟：r[5]Winner(勝者)25*25*51082108086325*2121254925*160863082108086325*2121254925*160863161616632125252525*25*第六趟：r[6]Winner(勝者)49494952082108086325*2121254925*160863082108086325*2121254925*160863161616632125252525*25*494949第七趟：r[7]Winner(勝者)6353082108086325*2121254925*160863算法分析：錦標(biāo)賽排序構(gòu)成的樹是滿(完全）二叉樹，其深度為log2n+1，其中n

為待排序元素個數(shù)。時間復(fù)雜度：O(nlog2n)—n個記錄各自比較約log2n次空間效率：

O(n）—勝者樹的附加內(nèi)結(jié)點(diǎn)共有n’-1個！穩(wěn)定性：穩(wěn)定—左右結(jié)點(diǎn)相同者左為先討論：在簡單選擇排序過程中，每當(dāng)我們從表中選出最小元素之后，再選次最小元素時，必須把表中剩余元素再掃描一次。這樣，同一個元素會被掃描多次，浪費(fèi)！能否利用上次掃描的結(jié)果定出下一次的選擇結(jié)果呢？

答：能！請看——堆排序算法n’=2k=葉子總數(shù)54算法分析：錦標(biāo)賽排序構(gòu)成的樹是滿(完全）二叉樹，其深度為3）堆排序1.什么是堆？堆的定義：設(shè)有n個元素的序列k1，k2，…，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時，稱之為堆。ki≤

k2iki≤

k2i+1ki≥

k2iki≥

k2i+1或者i=1,2,…n/2解釋：如果讓滿足以上條件的元素序列（k1，k2，…，kn）順次排成一棵完全二叉樹，則此樹的特點(diǎn)是：樹中所有結(jié)點(diǎn)的值均大于（或小于）其左右孩子，此樹的根結(jié)點(diǎn)（即堆頂）必最大（或最?。?。2.怎樣建堆？3.怎樣堆排序？553）堆排序1.什么是堆？堆的定義：設(shè)有n個元素的序列k082546495867234561（大根堆）918566765867234561557例：有序列T1=（08,25,49,46,58,67）和序列T2=（91,85,76,66,58,67,55）,判斷它們是否“堆”？√（小根堆）√（小頂堆）（最小堆）（大頂堆）（最大堆）56082546495867234561（大根堆）9185667步驟：從最后一個非終端結(jié)點(diǎn)開始往前逐步調(diào)整，讓每個雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。212525*491608123456例：關(guān)鍵字序列T=(21，25，49，25*，16，08），請建大根堆。2.怎樣建堆？解：為便于理解，先將原始序列畫成完全二叉樹的形式：完全二叉樹的第一個非終端結(jié)點(diǎn)編號必為n/2

?。?性質(zhì)5)注：終端結(jié)點(diǎn)（即葉子）沒有任何子女，無需單獨(dú)調(diào)整。21i=3:49大于08，不必調(diào)整；i=2:25大于25*和16，也不必調(diào)整；i=1:21小于25和49，要調(diào)整！49而且21還應(yīng)當(dāng)向下比較?。?7步驟：從最后一個非終端結(jié)點(diǎn)開始往前逐步調(diào)整，讓每個雙親大于（voidHeapSort(HeapType&H){

//H是順序表，含有H.r[]和H.length兩個分量

for(i=length/2;i>0;--i)//把r[1…length]建成大根堆HeapAdjust(r,i,length);//使r[i…length]成為大根堆……}建堆算法(其實(shí)是堆排序算法中的第一步）這是針對結(jié)點(diǎn)i的堆調(diào)整函數(shù)，其含義是：從結(jié)點(diǎn)i開始到堆尾為止，自上向下比較，如果子女的值大于雙親結(jié)點(diǎn)的值，則互相交換，即把局部調(diào)整為大根堆。參見教材P281-28258voidHeapSort(HeapType&H){針對結(jié)點(diǎn)i的堆調(diào)整函數(shù)HeapAdjust如下：HeapAdjust(r,i,m){current=i;child=2*i;temp=r[i];

while(child<=m){if(child<m&&r[child].key<r[child+1].key

)child=child+1;if(temp.key>=r[child].key)breack;else{

r[current]=r[child];current=child;child=2*child;}

}r[current]=temp;}//HeapAdjust//temp是根，child是其左孩子//檢查是否到達(dá)當(dāng)前堆尾//讓child指向兩子女中的大者//根大則不必調(diào)整，結(jié)束整個函數(shù)//否則子女中的大者上移//并繼續(xù)向下整理！//直到自下而上都滿足堆定義，再安置老根——從結(jié)點(diǎn)i開始到當(dāng)前堆尾m為止，自上向下比較，如果子女的值大于雙親結(jié)點(diǎn)的值，則互相交換，即把局部調(diào)整為大根堆。//將根下降到子女位置59針對結(jié)點(diǎn)i的堆調(diào)整函數(shù)HeapAdjust如下：Heap關(guān)鍵：將堆的當(dāng)前頂點(diǎn)輸出后，如何將剩余序列重新調(diào)整為堆？方法：將當(dāng)前頂點(diǎn)與堆尾記錄交換，然后仿建堆動作重新調(diào)整，如此反復(fù)直至排序結(jié)束。3.怎樣進(jìn)行堆排序？60關(guān)鍵：將堆的當(dāng)前頂點(diǎn)輸出后，如何將剩余序列重新調(diào)整為堆？3.08252125*1649交換1號與6號記錄492525*21160812345649252125*1608初始最大堆2525*16211365420849例：對剛才建好的大根堆進(jìn)行排序：6108252125*1649交換1號與61625*21082549交換1號與5號記錄08

252125*1649從1號到5號重新調(diào)整為最大堆082525*2116491234561625*08252149136542082525*2508

2125*1649082525*21

081649621625*21082549交換1號與508162125*2549交換1號與4號記錄25*1621082549從1號到4號重新調(diào)整為最大堆25*1608212549123456081625*2521491365426308162125*2549交換1號與08162125*2549交換1號與3號記錄21160825*2549從1號到3號重新調(diào)整為最大堆211625*082549123456081625*2521491365426408162125*2549交換1號與308162125*2549交換1號與2號記錄160821

25*2549從1號到2號重新調(diào)整為最大堆160825*212549123456081625*2521491365426508162125*2549交換1號與2voidHeapSort(HeapType&H){//對順序表H進(jìn)行堆排序for(i=H.length/2;i>0;--i)

HeapAdjust(H,i,H.length);//初始堆for(i=H.length;i>1;--i){

H.r[1]H.r[i]; //交換，要借用tempHeapAdjust(H,1,i-1);//重建最大堆

}}堆排序的算法參見教材P281-282這是針對結(jié)點(diǎn)i的堆調(diào)整函數(shù)（也是建堆函數(shù)），每次調(diào)用耗時O(log2n)66voidHeapSort(HeapType&H){附1：基于初始堆進(jìn)行堆排序的算法步驟：堆的第一個對象V[0]具有最大的關(guān)鍵碼，將V[0]與V[n]對調(diào)，把具有最大關(guān)鍵碼的對象交換到最后，再對前面的n-1個對象，使用堆的調(diào)整算法，重新建立堆。結(jié)果具有次最大關(guān)鍵碼的對象又上浮到堆頂，即V[0]位置。再對調(diào)V[0]和V[n-1]，調(diào)用對前n-2個對象重新調(diào)整，…如此反復(fù)，最后得到全部排序好的對象序列。67附1：基于初始堆進(jìn)行堆排序的算法步驟：堆的第一個對象V[0]比較左右孩子大小，j指向大者比較大孩子與rc的大小若大向上浮rc=H.r[s];j=2s;j<m&&H.r[j].key<H.r[j+1].key++j;//指向右兄弟j<mrc.key>H.r[j].keyH.r[s]=H.r[j];s=j;j=2*j;//指向左孩子NNNYYYH.r[s…m]中除r[s]外，其他具有堆特征現(xiàn)調(diào)整r[s]的值，使H.r[s…m]為堆附2：

算法流程68比較左右孩子大小，j指向大者比較大孩子與rc的大小rc=堆排序算法分析：時間效率：

O(nlog2n)。因?yàn)檎麄€排序過程中需要調(diào)用n-1次HeapAdjust()算法，而算法本身耗時為log2n；空間效率：O(1)。僅在第二個for循環(huán)中交換記錄時用到一個臨時變量temp。穩(wěn)定性：不穩(wěn)定。優(yōu)點(diǎn)：對小文件效果不明顯，但對大文件有效。69堆排序算法分析：時間效率：O(nlog2n)。因?yàn)檎麄€排序10.5歸并排序歸并排序的基本思想是：將兩個（或以上）的有序表組成新的有序表。更實(shí)際的意義：可以把一個長度為n的無序序列看成是n個長度為1的有序子序列，首先做兩兩歸并，得到n/2個長度為2的子序列；再做兩兩歸并，…，如此重復(fù)，直到最后得到一個長度為n的有序序列。例：關(guān)鍵字序列T=（21，25，49，25*，93，62，72，08，37，16，54），請給出歸并排序的具體實(shí)現(xiàn)過程。7010.5歸并排序歸并排序的基本思想是：將兩個（或以上）的212525*9362720837165449212525*4962930872163754163754212525*490862729308212525*496272930816212525*374954627293len=1len=2len=4len=8len=16163754整個歸并排序僅需log2n趟71212525*9362720837165449212525*一趟歸并排序算法:(兩路有序并為一路)

參見教材P283void

Merge

(SR，&TR，i,m,n){//將有序的SR[i…m]和SR[m+1…n]歸并為有序的TR[i…n]for(k=i,j=m+1;i<=m&&j<=n;++k){if(SR[i]<=SR[j])TR[k]=SR[i++];elseTR[k]=SR[j++];//將SR中記錄由小到大地并入TR}if(i<=m)TR[k…n]=SR[i…m];//將剩余的SR[i…m]復(fù)制到TRif(j<=n)TR[k…n]=SR[j…n];//將剩余的SR[j…n]復(fù)制到TR}//Merge72一趟歸并排序算法:(兩路有序并為一路)參見教材Pvoid

MSort(SR，&TR1，s,t){//將無序的SR[s…t]歸并排序?yàn)門R1[s…t]

if(s==t)TR1[s]=SR[s];//當(dāng)len=1時返回else{

m=(s+t)/2;//將SR[s…t]平分為SR[s…m]和SR[m+1…t]

MSort(SR，&TR2，s,m);//將SR一分為二,2分為4…

//遞歸地將SR[s…m]歸并為有序的TR2[s…m]

MSort

(SR，&TR2，m+1,t);//遞歸地將SR[m+1…t]歸并為有序的TR2[m+1…t]

Merge(TR2，TR1，s,m,t);//將TR2[s…m]和TR2[m+1…t]歸并到TR1[s…t]

}

}//MSort遞歸形式的兩路歸并排序算法:參見教材P284

(一路無序變?yōu)橛行?簡言之，先由“長”無序變成“短”有序，再從“短”有序歸并為“長”有序。初次調(diào)用時為（L,L,1,length）73voidMSort(SR，&TR1，s,t){遞歸歸并排序算法分析：

時間效率：

O(nlog2n)因?yàn)樵谶f歸的歸并排序算法中，函數(shù)Merge()做一趟兩路歸并排序，需要調(diào)用merge()函數(shù)n/(2*len)

O(n/len)次，函數(shù)Merge()調(diào)用Merge()正好log2n次，而每次merge()要執(zhí)行比較O(len)次，所以算法總的時間復(fù)雜度為O(nlog2n)?？臻g效率：

O(n)因?yàn)樾枰粋€與原始序列同樣大小的輔助序列（TR）。這正是此算法的缺點(diǎn)。穩(wěn)定性：穩(wěn)定74歸并排序算法分析：時間效率：O(nlog2n)7410.6基數(shù)排序(RadixSort)要討論的問題：1.什么是“多關(guān)鍵字”排序？實(shí)現(xiàn)方法？2.單邏輯關(guān)鍵字怎樣“按位值”排序？基數(shù)排序的基本思想是：借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進(jìn)行排序。即：用關(guān)鍵字不同的位值進(jìn)行排序。7510.6基數(shù)排序(RadixSort)要討論的問題1.什么是“多關(guān)鍵字”排序？實(shí)現(xiàn)方法？例1：對一副撲克牌該如何排序？若規(guī)定花色和面值的順序關(guān)系為：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A則可以先按花色排序，花色相同者再按面值排序；也可以先按面值排序，面值相同者再按花色排序。例2：職工分房該如何排序？規(guī)定：先以總分排序（職稱分＋工齡分）；總分相同者，再按配偶總分排序，其次按配偶職稱、工齡、人口……等等排序。以上兩例都是典型的多關(guān)鍵字排序！761.什么是“多關(guān)鍵字”排序？實(shí)現(xiàn)方法？例1：對一副撲克牌多關(guān)鍵字排序的實(shí)現(xiàn)方法通常有兩種：最高位優(yōu)先法MSD(MostSignificantDigitfirst)例：對一副撲克牌該如何排序？答：若規(guī)定花色為第一關(guān)鍵字（高位），面值為第二關(guān)鍵字（低位），則使用MSD和LSD方法都可以達(dá)到排序目的。MSD方法的思路：先設(shè)立4個花色“箱”，將全部牌按花色分別歸入4個箱內(nèi)（每個箱中有13張牌）；然后對每個箱中的牌按面值進(jìn)行插入排序（或其它穩(wěn)定算法）。LSD方法的思路：先按面值分成13堆（每堆4張牌），然后對每堆中的牌按花色進(jìn)行排序（用插入排序等穩(wěn)定的算法）。想一想：用哪種方法更快些？最低位優(yōu)先法LSD(LeastSignificantDigitfirst)77多關(guān)鍵字排序的實(shí)現(xiàn)方法通常有兩種：最高位優(yōu)先法MSD(Mo2.單邏輯關(guān)鍵字怎樣“按位值”排序？設(shè)n個記錄的序列為：{V0,V1,…,Vn-1}，可以把每個記錄Vi的單關(guān)鍵碼Ki看成是一個d元組（Ki1,Ki2,…,Kid），則其中的每一個分量Kij(1jd)也可看成是一個關(guān)鍵字。4注1：

Ki1＝最高位，Kid＝最低位；Ki共有d位，可看成d元組；注2：每個分量Kij

(1

j

d)有radix種取值，則稱radix為基數(shù)。26(9,8,4)(0,1,…,9)（a,b,…,z）(d,i,a,n)310例1：關(guān)鍵碼984可以看成是

元組；基數(shù)radix為

。例2：關(guān)鍵碼dian可以看成是

元組；基數(shù)radix為

。思路：782.單邏輯關(guān)鍵字怎樣“按位值”排序？設(shè)n個記錄的序列為：因?yàn)橛蟹纸M，故此算法需遞歸實(shí)現(xiàn)。討論：是借用MSD方式來排序呢，還是借用LSD方式？例：初始關(guān)鍵字序列T=（32,13,27,32*,19，33），請分別用MSD和LSD進(jìn)行排序，并討論其優(yōu)缺點(diǎn)。法1（MSD）：原始序列：32,13,27,32*,19，33

先按高位Ki1

排序：（13,19）,27,（32,32*，33）

再按低位Ki2排序：13,19，27,32,32*,33法2（LSD）：原始序列：32,13,27,32*,19，33先按低位Ki2排序：

32,32*,13,33,27,19

再按高位Ki1排序：

13,19,27,32,32*,33無需分組，易編程實(shí)現(xiàn)！79因?yàn)橛蟹纸M，故此算法需遞歸實(shí)現(xiàn)。討論：是借用MSD方式來排序例：T=（02，77，70，54，64，21，55，11），用LSD排序。分析：①各關(guān)鍵字可視為2元組；②每位的取值范圍是：0-9；即基數(shù)radix＝10。因此，特設(shè)置10個隊(duì)列，并編號為0-9。1155216454707702原始序列12345678先對低位掃描出隊(duì)012345678910個隊(duì)列計算機(jī)怎樣實(shí)現(xiàn)LSD算法？分配過程收集過程下一步775564540211217012345678出隊(duì)后序列775554，6421，117002又稱散列過程！80例：T=（02，77，70，54，64，21，55，11），0123456789再次入隊(duì)再次出隊(duì)再對高位掃描小結(jié)：排序時經(jīng)過了反復(fù)的“分配”和“收集”過程。當(dāng)對關(guān)鍵字所有的位進(jìn)行掃描排序后，整個序列便從無序變?yōu)橛行蛄恕?75564540211217012345678出隊(duì)后序列70，776454，55211102再次分配再次收集7770645554211102再次出隊(duì)后序列這種LSD排序方法稱為：基數(shù)排序810再次入隊(duì)再次出隊(duì)再對高位掃描小結(jié)：排序時經(jīng)過了反復(fù)的“分配討論：所用隊(duì)列是順序結(jié)構(gòu)，浪費(fèi)空間，能否改用鏈?zhǔn)浇Y(jié)構(gòu)？用鏈隊(duì)列來實(shí)現(xiàn)基數(shù)排序—鏈?zhǔn)交鶖?shù)排序?qū)崿F(xiàn)思路：針對d元組中的每一位分量，把原始鏈表中的所有記錄,按Kij的取值，讓j=d,d-1,…,1，①先“分配”到radix個鏈隊(duì)列中去；②然后再按各鏈隊(duì)列的順序，依次把記錄從鏈隊(duì)列中“收集”起來；③分別用這種“分配”、“收集”的運(yùn)算逐趟進(jìn)行排序；④在最后一趟“分配”、“收集”完成后，所有記錄就按其關(guān)鍵碼的值從小到大排好序了。能！82討論：所用隊(duì)列是順序結(jié)構(gòu)，浪費(fèi)空間，能否改用鏈?zhǔn)浇Y(jié)構(gòu)？用鏈隊(duì)請實(shí)現(xiàn)以下關(guān)鍵字序列的鏈?zhǔn)交鶖?shù)排序：T=（614，738，921，485，637，101，215，530，790，306）例:614921485637738101215530790306第一趟分配e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]614738921485637101215530790306f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]原始序列鏈表：r[0]→（從最低位i=3開始排序，f[]

是隊(duì)首指針，e[]

為隊(duì)尾指針）第一趟收集（讓隊(duì)尾指針e[i]

鏈接到下一非空隊(duì)首指針f[i+1]

即可）530790921101614485215306637738r[0]→83請實(shí)現(xiàn)以下關(guān)鍵字序列的鏈?zhǔn)交鶖?shù)排序：例:614921第一趟收集的結(jié)果：e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]614738921485637101215530790306f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]第二趟分配（按次低位i=2）530790921101614485215306637738第二趟收集（讓隊(duì)尾指針e[i]

鏈接到下一非空隊(duì)首指針f[i+1]

）530790921101614485215306637738r[0]→r[0]→84第一趟收集的結(jié)果：e[0]e[1]e[2]第二趟收集的結(jié)果：530790921101614485215306637738e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]614738921485637101215530790306f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]第三趟分配（按最高位i=1）第三趟收集（讓隊(duì)尾指針e[i]

鏈接到下一非空隊(duì)首指針f[i+1]

）530790921101614485215306637738r[0]→r[0]→排序結(jié)束！85第二趟收集的結(jié)果：5307909211016144852151.排序前后的n個記錄都用順序表r[]存儲，但建議增開n個指針分量（轉(zhuǎn)為靜態(tài)鏈表形式）；這樣在記錄重排時不必移動數(shù)據(jù)，只需修改各記錄的鏈接指針即可。2.在radix個隊(duì)列中，每個隊(duì)列都要設(shè)置兩個指針：int

f[radix]指示隊(duì)頭(f[j]初始為空）；int

e[radix]指向隊(duì)尾（e[j]不必單獨(dú)初始化)；分配到同一隊(duì)列的關(guān)鍵碼要用鏈接指針鏈接起來。（注：以上一共增開了n+2radix個附加指針分量）3.待排序記錄存入r[]中，r[0]作為頭結(jié)點(diǎn)；每個記錄都