【正文】 關鍵 字比較的次數(shù)不超過 2 (?log2(n1)?+ ?log2(n2)?+ … +log22) 2n(?log2n?) 因此， 堆排序的時間復雜度為 O(nlogn)。amp。 2022年 8月 26日星期五 第 78頁 例如： 52, 23, 80, 36, 68, 14 (s=1, t=6) [ 52, 23, 80] [36, 68, 14] [ 52, 23][80] [ 52] [ 23, 52] [ 23, 52, 80] [36, 68][14] [36][68] [36, 68] [14, 36, 68] [ 14, 23, 36, 52, 68, 80 ] [23] 2022年 8月 26日星期五 第 79頁 void Msort ( RcdType SR[], RcdType amp。 } // MergeSort 容易看出，對 n 個記錄進行歸并排序的時間復雜度為 Ο (nlogn)。 對于數(shù)字型或字符型的 單關鍵字 ，可以 看成 是由多個數(shù)位或多個字符構成的 多關鍵字 ，此時可以 采用 這種 “分配 收集”的辦法 進行排序 ， 稱作基數(shù)排序法 。 4. 鏈式基數(shù)排序 需附設隊列首尾指針，則空間復雜度為 O(rd)。 Ri(K) ) 2022年 8月 26日星期五 第 106頁 例如 :對三個關鍵字進行排序的判定樹 如下： K1K3 K1K2 K1K3 K2K3 K2 K3 K2K1K3 K1K2K3 K3K2K1 K2K3K1 K3K1K2 K1K3K2 １．樹上的 每一次“比較”都是必要的 。 第三趟 由 3 個歸并段得到 2個歸并段； 第二趟 由 5 個歸并段得到 3個歸并段； 2022年 8月 26日星期五 第 113頁 假設“數(shù)據(jù)塊”的大小為 200，即每一次訪問外存可以讀 /寫 200個記錄。學習本章的目的是了解各種排序方法的原理以及各自的優(yōu)缺點，以便在編制軟件時能按照情況所需合理選用。 4) 一般情況下，對單關鍵字進行排序時，所用的排序方法是否穩(wěn)定無關緊要。 3) 基數(shù)排序的時間復雜度為 O (d n)，因此特別適合于待排記錄數(shù) n 值很大，而關鍵字 位數(shù) d 較小的情況。 k 的 大小可選，但需綜合考慮各種因素。 2022年 8月 26日星期五 第 112頁 例如： 假設有一個含 10,000個記錄的磁盤 文件，而當前所用的計算機一次只 能對 1000個記錄進行內(nèi)部排序，則 首先利用內(nèi)部排序的方法得到 10個 初始歸并段，然后進行逐趟歸并 。 可以證明， 這類排序法 可能達到的最快的時間復雜度為 O(nlogn)。 直接插入排序 和 起泡排序 能達到 O(n)的時間復雜度， 快速排序 的時間性能 蛻化為 O(n2) 。 2022年 8月 26日星期五 第 88頁 例如 :學生記錄含三個關鍵字 : 系別 、 班號 和 班內(nèi)的序列號 ，其中以系別為最主位關鍵字。 // 將 TR2[s..m]和 TR2[m+1..t]歸并到 TR1[s..t] 2022年 8月 26日星期五 第 81頁 void MergeSort (SqList amp。 // 將剩余的 SR[j..n] 復制到 TR 2022年 8月 26日星期五 第 77頁 歸并排序的算法 如果記錄無序序列 R[s..t] 的兩部分 R[s..?(s+t)/2?] 和 R[?(s+t)/2?+1..t] 分別按關鍵字有序， 則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。TR[], int i, int m, int n) { // 將有序的記錄序列 SR[i..m] 和 SR[m+1..n] // 歸并為有序的記錄序列 TR[i..n] } // Merge for (j=m+1, k=i。 // 左 /右“子樹根”之間先進行相互比較 // 令 j 指示關鍵字較大記錄的位置 2022年 8月 26日星期五 第 71頁 建堆是一個從下往上進行“篩選”的過程。 j*=2 ) { // j 初值指向左孩子 自上而下的篩選過程 。 // 將堆頂記錄和當前未經(jīng)排序子序列 // [1..i]中最后一個記錄相互交換 HeapAdjust(, 1, i1)。 12 36 27 65 49 81 73 55 40 34 98 例如 : 是堆 14不 2022年 8月 26日星期五 第 64頁 堆排序即是利用 堆的特性 對記錄序列進行排序的一種排序方法。 為避免出現(xiàn)這種情況， 需在進行一次劃分之前，進行“ 予處理 ”， 即： 先對 R(s).key, R(t).key 和 R[?(s+t)/2?].key，進行相互比較，然后 取 關鍵字為 “三者之中” 的記錄 為樞軸 記錄。 // 對 R[s..t] 進行 一次劃分 QSort(R, s, pivotloc1)。amp。 } return low。 while (lowhigh) { while (lowhigh amp。 例如 : 5 2 3 1 9 7 82 5 5 3 1 5 7 9 8 9 i=7 i=6 for (j = 1。 for(j=i+1。 // 插入 } // if } // ShellInsert 2022年 8月 26日星期五 第 41頁 void ShellSort (SqList amp。 i=n。 // 交換記錄，使第 i個記錄到位 SL[i].next = p。 j=k, k=SL[k].next ) { SL[j].next = i。利用靜態(tài)鏈表 進行排序，并 在排序完成之后，一次 性地調整各個記錄相互之間的位置 ， 即將每個記錄都調整到它們所應該在 的位置上。 j ) [j+1] = [j]。 // 插入到正確位置 2022年 8月 26日星期五 第 27頁 內(nèi)部排序的 時間分析 ： 實現(xiàn)內(nèi)部排序的 基本操作 有兩個： （ 2） “移動” 記錄。L ) { // 對順序表 L 作直接插入排序。 R[0].keyR[j].key。 2022年 8月 26日星期五 第 16頁 3. 選擇類 從記錄的無序子序列中 “選擇”關鍵字最小或最大 的記錄，并將它加入到有序子序列 中，以此方法增加記錄的有序子序列的長度。 // 關鍵字類型為整數(shù)類型 typedef struct { KeyType key。 2022年 8月 26日星期五 第 5頁 【 學習指南 】 本章學習的要點主要是了解各種排序方法實現(xiàn)時所依據(jù)的原則以及它們的主要操作（“關鍵字間的比較”和“記錄的移動”）的時間分析。 2．掌握各種排序方法的時間復雜度的分析方法。logn) 的高效排序方法和 O (d 2022年 8月 26日星期五 第 6頁 概述 插入排序 快速排序 堆排序 歸并排序 基數(shù)排序 各種排序方法的綜合比較 外部排序 2022年 8月 26日星期五 第 7頁 概 述 一、排序的定義 二、內(nèi)部排序和外部排序 三、內(nèi)部排序方法的分類 2022年 8月 26日星期五 第 8頁 一、什么是排序？ 排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組 “無序”的記錄序列調整為“有序” 的記錄序列。 // 記錄類型 typedef struct { RcdType r[MAXSIZE+1]。 2． 將 R[j+1..i1]中的所有 記錄 均 后移 一個位置； 1． 在 R[1..i1]中 查找 R[i]的插入位置， R[1..j].key ? R[i].key R[j+1..i1].key； 2022年 8月 26日星期五 第 21頁 直接插入排序 （基于順序查找） 表插入排序 （基于鏈表存儲） 不同的具體實現(xiàn)方法導致不同的算法描述 折半插入排序 （基于折半查找） 希爾排序 （基于逐趟縮小增量） 2022年 8月 26日星期五 第 22頁 一、直接插入排序 利用 “順序查找” 實現(xiàn) “在 R[1..i1]中 查找 R[i]的插入位置” 算法的實現(xiàn)要點： 2022年 8月 26日星期五 第 23頁 從 R[i1]起向前進行順序查找， 監(jiān)視哨設置在 R[0]； R[0] = R[i]。 for ( i=2。 ++i ) if ([i].key [i1].key) { } } // InsertSort [0] = [i]。L ) { } // BInsertSort 在 [1..i1]中折半查找插入位置； for ( i=2。 high = i1。 SL[1].next = 0。 // p指示第一個記錄的當前位置 for ( i=1。 所謂“宏觀”調整，指的是，“跳躍式” 的插入排序。 j0amp。 ++t) ShellInsert(L, dlta[k])。 temp=r[j]。 2022年 8月 26日星期五 第 46頁 時間分析 : 最好的情況（關鍵字在記錄序列中順序有序）： 只需進行一趟起泡 “ 比較”的次數(shù)： 最壞的情況（關鍵字在記錄序列中逆序有序）： 需進行 n1趟起泡 “ 比較”的次數(shù)： 0 “ 移動”的次數(shù)： “ 移動”的次數(shù)： n1 2)1()1(2 ?????nnini 2)1(3)1(3 2 ?????nnini2022年 8月 26日星期五 第 47頁 二、一趟快速排序（一次劃分） 目標： 找一個記錄， 以它的關鍵字