【正文】 的算法是對兩個有序序列歸并成一個有序序列。 } } 歸并排序分析 ?二路歸并排序的時間復雜性為 O(nlogn)，與堆排序和快速排序平均情況的時間復雜性是相同數(shù)量級。 ?每位數(shù)可能取值的數(shù)目 rd稱為基數(shù) (Radix)，例如對于十進制數(shù)的每一位可能有 0到 9十種取值，故基數(shù)為 10；而二進制的每一位數(shù)只能有 0和 1兩種取值，則基數(shù)為 2。 /*d為關鍵字的位數(shù) */ int next。 r[n].next=0。 if (f[t]==0) f[t]=p。 while (jrd) 基數(shù)排序算法續(xù) { j++。 返回 例 ?已知序列{60,20,31,1,5,44,55,61,200,30,80,150,4,29},寫出采用快速排序算法排序的每一趟的結果。 p=head。 } } 返回 小 結 ?排序 ?冒泡排序 ?直接選擇排序 ?簡單插入排序 ?堆排序 ?快速排序 ?歸并排序 ?基數(shù)排序 返回 習題與練習 ?一、基本知識題 1. 解釋下列概念 (1) 排序 (2) 內部排序 (3) 堆 (4) 穩(wěn)定排序 2. 回答下面問題 (1) 5000個無序的數(shù)據(jù)，希望用最快速度挑選出其中前 10個最大的元素，在快速排序、堆排序、歸并排序和基數(shù)排序中采用哪種方法最好？為什么？ (2) 大多數(shù)排序算法都有哪兩個基本操作？ 3. 已知序列 {17， 25， 55， 43， 3， 32， 78， 67，91}，請給出采用冒泡排序法對該序列作遞增排序時每一趟的結果。） 4. 設一個一維數(shù)組 A[n]中存儲了 n個互不相同的整數(shù)，且這些整數(shù)的值都在 0到 n1之間，即 A中存儲了從 0到 n1這 n個整數(shù)。 3. 試設計一個算法實現(xiàn)雙向冒泡排序。 minkey=temp。 ?實現(xiàn)本題功能的函數(shù)如下 : void select(node *head) { node *p,*q,*min。若基數(shù) rd相同，對于關鍵字數(shù)目較多但位數(shù)較少的情況，采用基數(shù)排序較為適用。 /*尋找第一個非空隊列 */ p=f[j]。 j++) f[j]=0。 i=n1。 ?如此反復進行，直至做完 d趟，即排序結束。 ?對關鍵字的檢查從低位到高位進行，到檢查最高位的一趟“分散”過程結束，最后將卡片“收集”起來即排序完畢。 mergesort (r, r2, k+1, t)。 /*復制 } 歸并排序算法續(xù) while (i=m) /*把子序列 r[s… m]中剩 r2[k++]=r[i++]。 歸并排序算法 void merge (r[], r2[], s, m, t) /*把兩個有序子 { /*序列 r[s… m]和 r[m+1… t]歸 int i, j, k。 /*堆頂元素和最后一個 sift (r, 1, i1)。 ?把一個 n個元素的無序序列看成一棵完全二叉樹，則最后一個內部結點的下標是 ?n/2? .因此，只需從第 ?n/2? 個元素開始，直到第 1個元素，依次調用 sift, 即可建成一個堆。 /*堆 ， 現(xiàn)要調整 R[i]， 使整個序列 while (j=m) /*R[i： m]成為一個堆 { if ((jm amp。 ?由于堆是完全二叉樹，采用將結點順序編號存入一維數(shù)組中的表示法比鏈接表示法節(jié)省存儲空間，也便于計算。在所有已發(fā)表的排序算法中，該算法是研究最深的。 } } while (ij)。 (ij)) j。 i先不動使 j逐步前移，每次對二者所指的數(shù)據(jù)進行比較，當遇到 r[i]大于 r[j]的情況時，就將二者對調位置；然后令 j固定使 i逐步后移做數(shù)據(jù)比較，當遇到 r[i]大于 r[j] 時，又進行位置對調；然后又是 i不動使 j前移作數(shù)據(jù)比較； …… ； ?如此反復進行，直至 i與 j兩者相遇為止。 ?希爾排序是不穩(wěn)定的。 k=id。 希爾排序 ?希爾（ Shell Sort)又稱“縮小增量排序”，它也時一種插入排序類的方法。 j=n。 ?在每一趟掃描時，用一個整型變量 i 跟蹤當前最小元素的位置。 j++) if (r[j+1].key r[j].key) { flag=0。 j=ni。 /* 在 j+1位置插入 r[0]*/ } } 性能分析 ?最好的情況：當待排序的記錄已經(jīng)有序時，比較次數(shù)為 n1；移動次數(shù)為 2（ n1） ?最壞的情況：當待排序的記錄按遞減排列時，比較次數(shù)為 2+3+……+n=(n 1)(n+2)/2 移動次數(shù)為 ?(I+1)=(n1)(n+4)/2 ?取其平均值： 比較次數(shù) 和 移動次數(shù) 均為 n*n/2，時間復雜度為 O（ n*n），空間復雜度為 O（ 1）。 圖 直接插入排序 ( 0) 42 20 17 13 28 14 23 15 ( 1) [ 20 42] ( 2) [ 17 20 42 ] ( 3) [ 13 1 7 20 42 ] ( 4) [ 13 17 20 28 42 ] ( 5) [ 13 14 17 20 28 4 2] ( 6) [ 13 14 17 20 23 28 42 ] ( 7) [ 13 14 15 17 20 23 28 20] 直接插入排序算法 void insertsort (rectype r[], int n) { int i,j。 /*其他域 */ }rectype。 ?關鍵字 (key)：對一批記錄的排序，應該指定是根據(jù)記錄中哪個字段進行排列。 ?一種排序方法，如果排序后具有相同關鍵字的記錄仍維持排序之前的相對次序，則稱之為 穩(wěn)定的， 否則稱為 不穩(wěn)定的 。 i++) { r[0]=r[i]。 2. 冒泡排序 基本思想： 首先將 R[1]和 R[2]比較，若逆序，則交換 R[1]和 R[2]，然后比較 R[2]和 R[3],….. 直到第 n1個記錄和第 n個記錄比較，經(jīng)過這一趟比較，最大的記錄被放在最后一個位置上；然后對前 n1個記錄進行同樣的操作，則具有次大關鍵字的記錄被放在第 n1個記錄的位置上；重復以上過程，直到?jīng)]有記錄交換為止。 for(i=1。 } } ? Flag的作用 用來指示掃描中有沒有進行數(shù)據(jù)交換，每趟掃描開始前將其置 1。 圖 簡單選擇排序 ( 0) [ 13 15 6 10 20 8 3 19 ] ( 1) 3 [ 15 6 10 20 8 13