【正文】 返回 。） 4. 設(shè)一個(gè)一維數(shù)組 A[n]中存儲(chǔ)了 n個(gè)互不相同的整數(shù)，且這些整數(shù)的值都在 0到 n1之間，即 A中存儲(chǔ)了從 0到 n1這 n個(gè)整數(shù)。 3. 試設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)雙向冒泡排序。 ?二、算法設(shè)計(jì)題 1. 一個(gè)線性表中的元素為全部為正或者負(fù)整數(shù)，試設(shè)計(jì)一算法，在盡可能少的時(shí)間內(nèi)重排該表，將正、負(fù)整數(shù)分開(kāi)，使線性表中所有負(fù)整數(shù)在正整數(shù)前面。 5. 已知序列 {86， 94， 138， 62， 41， 54， 18， 32}，請(qǐng)給出采用插入排序法對(duì)該序列作遞增排序時(shí)，每一趟的結(jié)果。 } } 返回 小 結(jié) ?排序 ?冒泡排序 ?直接選擇排序 ?簡(jiǎn)單插入排序 ?堆排序 ?快速排序 ?歸并排序 ?基數(shù)排序 返回 習(xí)題與練習(xí) ?一、基本知識(shí)題 1. 解釋下列概念 (1) 排序 (2) 內(nèi)部排序 (3) 堆 (4) 穩(wěn)定排序 2. 回答下面問(wèn)題 (1) 5000個(gè)無(wú)序的數(shù)據(jù)，希望用最快速度挑選出其中前 10個(gè)最大的元素，在快速排序、堆排序、歸并排序和基數(shù)排序中采用哪種方法最好？為什么？ (2) 大多數(shù)排序算法都有哪兩個(gè)基本操作？ 3. 已知序列 {17， 25， 55， 43， 3， 32， 78， 67，91}，請(qǐng)給出采用冒泡排序法對(duì)該序列作遞增排序時(shí)每一趟的結(jié)果。 minkey=temp。 } temp=pkey。 q=pnext。 p=head。 ?實(shí)現(xiàn)本題功能的函數(shù)如下 : void select(node *head) { node *p,*q,*min。 struct node *next。 ?解 : 快速排序各趟的結(jié)果如下 : [26] [5] [77] [1] [61] [11] [59] [15] [48] [19] [5 26] [1 77] [11 61] [15 59] [19 48] [1 5 26 77 ] [11 15 59 61] [19 48] [1 5 11 15 26 59 61 77] [19 48] [1 5 11 15 19 26 48 59 61 77] 例 ?設(shè)計(jì)一個(gè)用單鏈表作存儲(chǔ)結(jié)構(gòu)的選擇排序算法。 返回 例 ?已知序列{60,20,31,1,5,44,55,61,200,30,80,150,4,29},寫出采用快速排序算法排序的每一趟的結(jié)果。若基數(shù) rd相同，對(duì)于關(guān)鍵字?jǐn)?shù)目較多但位數(shù)較少的情況，采用基數(shù)排序較為適用。 /*收尾 */ } } 圖 初始狀態(tài) ?現(xiàn)以圖 306， 028，009， 948， 505， 917， 721， 430， 390為例說(shuō)明 radixsort函數(shù)的執(zhí)行過(guò)程。 t=e[j]。 while (jrd) 基數(shù)排序算法續(xù) { j++。 /*尋找第一個(gè)非空隊(duì)列 */ p=f[j]。 } j=0。 基數(shù)排序算法續(xù) e[t]=p。 if (f[t]==0) f[t]=p。 j++) f[j]=0。 i) /*從關(guān)鍵字的最后一位開(kāi)始 */ { for (j=0。 /*原始數(shù)據(jù)串成靜態(tài)鏈表，頭指針為 p*/ 基數(shù)排序算法續(xù) for ( i=d。 r[n].next=0。 i=n1。 int f[rd], e[rd]。 element rsqlist[n]。 /*d為關(guān)鍵字的位數(shù) */ int next。 ?如此反復(fù)進(jìn)行，直至做完 d趟，即排序結(jié)束。然后將原始數(shù)據(jù)隊(duì)列中各結(jié)點(diǎn)，按所考慮的關(guān)鍵字某位數(shù)的值插入到相應(yīng)“盒”的隊(duì)列中去。 圖 基數(shù)排序 3 0 6 0 2 8 0 0 9 9 4 8 5 0 5 9 1 7 7 2 1 4 3 0 3 9 0 ( a ) 原始數(shù)據(jù) key 390 430 721 505 306 917 948 028 009 盒 0 1 2 3 4 5 6 7 8 9 4 3 0 3 9 0 7 2 1 5 0 5 3 0 6 9 1 7 0 2 8 9 4 8 0 0 9 ( b ) 第一趟 key 009 306 505 917 028 721 430 948 390 盒 0 1 2 3 4 5 6 7 8 9 5 0 5 3 0 6 0 0 9 9 1 7 7 2 1 0 2 8 4 3 0 9 4 8 3 9 0 ( c ) 第二趟 key 028 009 390 306 430 505 721 948 917 盒 0 1 2 3 4 5 6 7 8 9 0 0 9 0 2 8 3 0 6 3 9 0 4 3 0 5 0 5 7 2 1 9 1 7 9 4 8 ( d ) 第三趟 ?為每個(gè)“盒”設(shè)置一個(gè)鏈接隊(duì)列，并將各隊(duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e存于兩個(gè)一維數(shù)組中。 ?每位數(shù)可能取值的數(shù)目 rd稱為基數(shù) (Radix)，例如對(duì)于十進(jìn)制數(shù)的每一位可能有 0到 9十種取值，故基數(shù)為 10；而二進(jìn)制的每一位數(shù)只能有 0和 1兩種取值，則基數(shù)為 2。 ?對(duì)關(guān)鍵字的檢查從低位到高位進(jìn)行，到檢查最高位的一趟“分散”過(guò)程結(jié)束，最后將卡片“收集”起來(lái)即排序完畢。 ?設(shè)每張卡片對(duì)應(yīng)著一個(gè)多位數(shù)的關(guān)鍵字，在卡片排序機(jī)中對(duì)卡片進(jìn)行多趟“分散”過(guò)程，每一趟逐張檢查卡片關(guān)鍵字的某一位數(shù)，將此位數(shù)取值相同的卡片放入同一片盒中。 返回 基數(shù)排序 ?基數(shù)排序 (Radix sort)最初是用于在卡片排序機(jī)上處理穿孔卡片的一種排序方法。 } } 歸并排序分析 ?二路歸并排序的時(shí)間復(fù)雜性為 O(nlogn)，與堆排序和快速排序平均情況的時(shí)間復(fù)雜性是相同數(shù)量級(jí)。 mergesort (r, r2, k+1, t)。 else { k=(s+t)/2。 ?二路歸并的遞歸算法如下： 二路歸并排序函數(shù) void mergesort (r[], r1[], s, t) /*將 r[s..t]中的記 { int k。 } ?上面的算法是對(duì)兩個(gè)有序序列歸并成一個(gè)有序序列。 /*復(fù)制 } 歸并排序算法續(xù) while (i=m) /*把子序列 r[s… m]中剩 r2[k++]=r[i++]。 j=t) { if (r[i].key = r[j].key) /*比較當(dāng)前 r2[k++]=r[i++]。 /*k為數(shù)組 r2[ ]的下標(biāo) while ( i=m amp。 j=m+1。 歸并排序算法 void merge (r[], r2[], s, m, t) /*把兩個(gè)有序子 { /*序列 r[s… m]和 r[m+1… t]歸