【正文】 返回 例 ?已知序列{60,20,31,1,5,44,55,61,200,30,80,150,4,29},寫出采用快速排序算法排序的每一趟的結(jié)果。 /*收尾 */ } } 圖 初始狀態(tài) ?現(xiàn)以圖 306， 028，009， 948， 505， 917， 721， 430， 390為例說明 radixsort函數(shù)的執(zhí)行過程。 while (jrd) 基數(shù)排序算法續(xù) { j++。 } j=0。 if (f[t]==0) f[t]=p。 i) /*從關(guān)鍵字的最后一位開始 */ { for (j=0。 r[n].next=0。 int f[rd], e[rd]。 /*d為關(guān)鍵字的位數(shù) */ int next。然后將原始數(shù)據(jù)隊列中各結(jié)點，按所考慮的關(guān)鍵字某位數(shù)的值插入到相應“盒”的隊列中去。 ?每位數(shù)可能取值的數(shù)目 rd稱為基數(shù) (Radix)，例如對于十進制數(shù)的每一位可能有 0到 9十種取值，故基數(shù)為 10；而二進制的每一位數(shù)只能有 0和 1兩種取值，則基數(shù)為 2。 ?設(shè)每張卡片對應著一個多位數(shù)的關(guān)鍵字，在卡片排序機中對卡片進行多趟“分散”過程，每一趟逐張檢查卡片關(guān)鍵字的某一位數(shù)，將此位數(shù)取值相同的卡片放入同一片盒中。 } } 歸并排序分析 ?二路歸并排序的時間復雜性為 O(nlogn)，與堆排序和快速排序平均情況的時間復雜性是相同數(shù)量級。 else { k=(s+t)/2。 } ?上面的算法是對兩個有序序列歸并成一個有序序列。 j=t) { if (r[i].key = r[j].key) /*比較當前 r2[k++]=r[i++]。 j=m+1。 ?兩個有序表的歸并稱為二路歸并。對 n個元素，樹的深度 k=?log2n? +1，篩選算法中關(guān)鍵字的比較次數(shù)最多為 2（ k1），共調(diào)用了 n1次，所以總的比較次數(shù)小于 2n（ ?log2n?）次；在建初始堆時，因為第 h（ 1≤h≤k1）層最多有 2h1個元素，而每一個元素的最大調(diào)整次數(shù)為 kh，故總的調(diào)整次數(shù)不大于 4n。 i1。 for (i=n/2。 /*x不大于左右兒子 ， 即已找到 } /*了合適的位置 i， 循環(huán)結(jié)束 r[i]=x。 r[j].keyr[j+1].key)) j++。 例： void sift (r[], i, m) /*把 R[i： m]看成完全二叉樹 ， 以 { j=2*i。根據(jù)順序表示二叉樹的特點，除下標為 1的結(jié)點 (根結(jié)點 )沒有父結(jié)點以外，其余下標為 j 的結(jié)點（ 2≤j≤n）都有父結(jié)點，父結(jié)點的下標為 i= 。 返回 堆排序 ?堆的概念 ?堆排序（ Heap Sort）是利用二叉樹的一種排序方法。 1969年，辛格爾頓就遵循了這一建議，采用R[1].key, R[n].key, R[n/2].key的中間值，故稱作“三者取中”法。 Quicksort(r, k+1, hig)。 return(i)。 if (ij) /*已找到了滿足 r[i].keyx的 r[i] { r[j]=r[i]。 /*r[j].keyx的 r[j] i++。 do { while( r[j].key= amp。 ?圖中括號中的數(shù)據(jù)表示正進行比較的兩個數(shù)據(jù)，左面一個的下標為 i，右面一個的下標為j。 圖 快速排序 [ 13 15 7 10 30 4 8 25 ] [ 8 4 7 10] 13 [ 30 15 25 ] [ 7 4 ] 8 [ 10] 13 [ 30 15 25 ] 4 7 8 10 13 [ 30 15 25 ] 4 7 8 10 13 [ 25 15] 30 4 7 8 10 13 15 25 30 ?一趟快速排序采用從兩頭向中間掃描的辦法。 ?基本思想：在待排序的 n個數(shù)據(jù)中任取一個數(shù)據(jù)（通常取第一個數(shù)據(jù)），把該數(shù)據(jù)和文件中的所有記錄比較，所有比該數(shù)據(jù)小的放置在前一部分，所有比它大的放置在后一部分，即該數(shù)據(jù)排在這兩部分的中間。 } } ?文件的分割不是簡單地“逐段分割”，而是將相隔某個“增量”的記錄組成一個子文件，這樣可以使元素 跳躍式地移動 ；每個子文件中的元素個數(shù)不必相等。amp。 for (i=d+1, i=n。 ?例： 9 13 8 2 5 13 7 1 4 11 希爾排序算法 Void shellsort (r[], n, dk[], t) /*dk[]增量數(shù)組 /*t:增量數(shù)組的元素數(shù) { for (i=1。 直接插入排序 和 簡單選擇排序 的比較 ?直接插入 1. 輸入序列是未知的； 2. 排序結(jié)束之前，不能確定任何元素的 最終位置。 if ( i!=k) r[i] ? r[k]。 i++) { k=i。這樣掃描 n1次，處理元素的個數(shù)從 n逐次減 1。 冒泡排序算法分析 ?最好情況： 比較次數(shù)： n1 交換次數(shù)： 0 ?最壞情況 比較次數(shù)： n(n1)/2 交換次數(shù) : n(n1)/2 ?時間復雜度： o(n*n) ?冒泡排序是穩(wěn)定的。 } if (flag==1) return。 for( j=1。 } } 修正后的冒泡排序算法 void bubblesort(r[ ], n) { int i, j, flag。 in。 ?可以看出 ， 該算法是穩(wěn)定的 。 /*記錄后移 */ j。 i=n。 ?直接插入算法需要經(jīng)過（ n1）趟插入過程。 ?如果在排序過程中，數(shù)據(jù)的主要部分存放在外存儲器中（如軟盤、硬盤、磁帶），借助內(nèi)存進行內(nèi)、外存數(shù)據(jù)交換，逐步排列記錄之間的順序，則稱之為 外部排序。 記錄的形式定義為： Typedef struct rectype { KeyType key。數(shù)據(jù)結(jié)構(gòu) 第 九 章 排序 第九章 排序 ?知 識 點 排序的基本概念 三種簡單的排序方法：冒泡排序、直接選擇排序、簡單插入排序 堆排序 快速排序 歸并排序 基數(shù)排序 ?難 點 堆排序 快速排序 歸并排序 基數(shù)排序 ?要 求 熟練掌握以下內(nèi)容： 熟悉各種內(nèi)部排序方法的基本思想和特點 各種排序方法的優(yōu)缺點、時、空性能和適用場合 熟悉并掌握三種簡單排序算法、快速排序算法和堆排序算法 了解以下內(nèi)容： 二路歸并排序算法 基數(shù)排序算法 排序的歷史