數(shù)據(jù)結(jié)構(gòu)與算法 (10).ppt

第十章 內(nèi)部排序 Chapter10 InternalSorting 排序又稱分類 是計算機中最重要的操作 它是將一個數(shù)據(jù)元素 或記錄 的任意序列排列成一個按關鍵字有序的序列 若待排序列中存在兩個或以上關鍵字相等的記錄 設Ki Kj 1 i j n 即排序前Ri在Rj前 若在排序后Ri仍在Rj前 則稱排序是穩(wěn)定的 穩(wěn)定的排序方法 stablesortingmethod 排序 sorting 不穩(wěn)定的排序方法 unstablesortingmethod 待排序列中存在兩個或以上關鍵字相等的記錄 設Ki Kj 1 i j n 即排序前Ri在Rj前 若在排序后Rj卻在Ri前 則稱排序是不穩(wěn)定穩(wěn)定的 內(nèi)部排序 internalsorting 待排序列記錄全部存放在計算機隨機存儲器中進行排序的過程稱為內(nèi)部排序 外部排序 externalsorting 待排序列記錄數(shù)量太大 不能全部存放在計算機隨機存儲器中 排序過程中需對計算機外存進行訪問 這種排序過程稱為外部排序 1 比較操作 比較兩個關鍵字值的大小的操作 排序過程中的兩種基本操作 2 移動操作 將記錄從一個位置移動到另一個位置的操作 待排序列的三種存儲結(jié)構(gòu) 1 順序存儲 存儲在地址連續(xù)的一組存儲單元中 以此為例 2 鏈式存儲 存儲在地址不連續(xù)的一組存儲單元 鏈表 中 3 地址存儲 記錄順序存儲 另設關鍵字和記錄地址排序 typedefstruct keytypekey elemtype typedefstruct elemtype elem intlength sqlist 10 1插入排序 一 直接插入排序 直接插入排序 straightinsertionsort 是一種最簡單的排序方法 將記錄一個個插入到已排序好的有序表中 從而得到長度增加的新的有序表 voidstraightinsertsort sqlist 排序性能分析 比較次數(shù) 最好情況 n 1最壞情況 n 2 n 1 2平均比較次數(shù) n 4 n 1 4 二 折半插入排序 折半插入排序 binaryinsertionsort 與直接插入排序不同之處在于查找插入位置時不是用順序查找 而是用折半查找 可見 直接插入排序的時間復雜度為O n2 但在待排序列有序的的情況下 直接插入排序的時間復雜度下降為O n 移動次數(shù) 最好情況 0最壞情況 n 4 n 1 2平均移動次數(shù) n 4 n 1 4 折半插入排序的移動次數(shù)與直接插入排序相同 只是比較次數(shù)少了 因此其時間復雜度也為O n2 三 2 路插入排序 2 路插入排序目的是為了減少排序過程中移動記錄的次數(shù) 代價是需要n個記錄的輔助空間d 將r 1 賦值給d 1 將d看成循環(huán)的 其它記錄均與d 1 比較 比其小則在d 1 前插入 反之則在d 1 后插入 2 路插入排序的移動次數(shù)大約為n2 2 因此其時間復雜度仍為O n2 四 表插入排序 表插入排序需附設一個指針域 通過改變指針的值來達到不移動記錄而得到排序結(jié)果的目的 表插入排序是用改變指針來代替移動記錄操作 因此其時間復雜度還為O n2 表插入排序的結(jié)果是形成了鏈表 因此查找時只能用順序查找 為能使用折半查找 需對記錄重新排序 但這不影響其時間復雜度 五 希爾排序 希爾排序 Shell smethod 又稱為 縮小增量排序 diminishingincrementsort 是一種比較復雜的插入排序 希爾排序的思想是 用一定的增量間隔將待排序列分成多個組 每組都采用簡單插入排序 排序完一遍后 縮小增量間隔 再對新的分組采用簡單插入排序 反復此過程 直至增量間隔為1 即整個待排序列為一組時 執(zhí)行一遍簡單插入排序后結(jié)束 voidShellinsert sqlist 希爾排序的時間復雜度與增量序列有關 分析起來很復雜 有人認為為O n1 5 也有人認為為O n1 3 在以上插入排序中 除希爾排序為不穩(wěn)定排序外 其余的都是穩(wěn)定的排序 voidShellsort sqlist 10 2交換排序 一 起泡排序 起泡排序 bubblesort 也是一種最簡單的排序方法 將相鄰兩記錄一一比較 將關鍵字較小的記錄交換在前面 反復此過程 直到待排序列有序為止 voidbubblesort sqlist 起泡排序也是一種穩(wěn)定的排序 時間復雜度為O n2 二 快速排序 快速排序 quicksort 是對起泡排序的改進 將待排序列第一個元素 樞軸元素 pivot 放置到序列中的某個位置 使其前面的所有元素的關鍵字都小于它 后面的所有元素的關鍵字都大于它 再分別對樞軸元素前面和后面的兩段待排序列采用快速排序方法 直至每一段都只剩下一個元素為止 intquickpass sqlist voidquicksort sqlist 快速排序是基于比較和交換的排序方法里最快的一種排序 其時間復雜度為O nlogn 但快速排序的效率不太穩(wěn)定 在關鍵字均勻分布時 效率最高 在關鍵字有序時 效率將退化為O n2 如何解決這個難題呢 其實 我們仔細分析就可看出 效率低是因為樞軸元素的選取有問題 我們希望每次選取的樞軸元素都處于待排序列中間位置 但當待排序列有序時 樞軸元素的取值每次都是最大的或最小的 有鑒于此 我們能否考慮在樞軸元素選取時 與部分元素比較一下 選取它們中處于中間大小的元素與樞軸元素交換 作為新的樞軸元素 通常是將處于待排序列頭部 尾部和中間的三個元素比較 從而得到新的樞軸元素 這種方法叫 三者取中法 它能很有效的防止快速排序效率的退化 在空間復雜度上 除靜態(tài)數(shù)據(jù)外 由于遞歸的原因 棧的最大深度在最好的情況下為O logn 在最壞的情況下為n 在非遞歸算法中 每次都先對較短的子序列先進行排序能降低棧的深度 快速排序是不穩(wěn)定排序 voidquicksort sqlist 快速排序的非遞歸算法如下 作業(yè)29 試證明 當待排序列已呈現(xiàn)出有序狀態(tài)時 快速排序的時間復雜度為O n2 30 試以單鏈表為存儲結(jié)構(gòu)實現(xiàn)簡單插入排序 第六次上機作業(yè)輸入若干組長度各異的待排序列 分別用快速排序算法和改進的樞軸元素三者取中算法對待排序列進行排序 當待排子序列長度已小于20時 改用直接插入排序 利用時間函數(shù)驗證三者取中算法在效率上的提高 提示 待排序列的長度一般應為5000以上 10 3選擇排序 一 簡單選擇排序 簡單選擇排序 simpleselectionsort 同樣也是一種最簡單的排序方法 每次從待排序列中選出關鍵字最小記錄作為有序序列中最后一個記錄 直至最后一個記錄為止 voidsimpleselectionsort sqlist 二 樹形選擇排序 借鑒體育比賽中淘汰賽的做法 將兩兩比賽過的優(yōu)勝者推舉出去與其它組的優(yōu)勝者比賽 反復此過程 直到?jīng)Q出冠軍為止 若能記住每次比賽的結(jié)果 則亞軍的產(chǎn)生不必再經(jīng)過此過程 只需將與冠軍賽過的每一個運動員逐級進行比賽 即可得到亞軍 這就是樹形選擇排序的思路 樹形選擇排序 treeselectionsort 又稱為錦標賽排序 tournamentsort 是一種按錦標賽思 由于有不相鄰元素交換 所以簡單選擇排序是不穩(wěn)定的排序 其時間復雜度為O n2 樹形選擇排序除第一次外 每次都走了樹的一條分支 故其時間復雜度為O nlogn 想進行的排序 將相鄰記錄兩兩分為一組進行比較 將關鍵字較小的記錄送往上一層 參加與其它組關鍵字較小記錄的比較 兩兩比較后再送往上層關鍵字較小記錄 反復此過程 直到只剩下一個記錄即為關鍵字最小記錄 將待排序列中該最小記錄處置為無窮大 則與其比較過的所有記錄按層次逐級比較 直至找到下一個最小記錄為止 反復此過程直至序列有序 三 堆排序 堆的定義 堆排序的思路 將待排序列建成堆 初始堆生成 后 則序列的第一個元素 堆頂元素 就一定是序列中的最大元素 將其與序列的最后一個元素交換 將序列長度減一 再將序列建成堆 堆調(diào)整 后 堆頂元素 樹形排序需要2n 1個輔助空間 1964年J Willioms提出另外一種選擇排序 堆排序 heapsort 仍是序列中的最大元素 再次將其與序列最后一個元素交換并縮短序列長度 反復此過程 直至序列長度為一 所得序列即為排序后結(jié)果 堆排序的結(jié)果為 12 26 32 58 63 74 85 91 那么 應如何建立初始堆 又如何進行堆調(diào)整呢 其實 由此例可以看出 建立初始堆就是多次進行堆調(diào)整的過程 voidheapadjust sqlist voidheapsort sqlist 堆排序只需一個輔助空間用于交換 其時間復雜度為O nlogn 堆排序是不穩(wěn)定排序 10 4歸并排序 歸并排序 mergingsort 的思想是每次將兩個或兩個以上的有序表合并成一個較長的有序表 反復此過程 直到最終只剩下一個有序表為止 單個記錄即是最初的有序表 voidmerge sqlist voidmergesort sqlist 以上給出的是二路歸并排序的非遞歸算法 其實歸并排序可以很方便的用遞歸程序?qū)崿F(xiàn) 歸并排序是一種穩(wěn)定的排序方法 其時間復雜度為O nlogn 輔助空間為n 作業(yè)31 假設有n個值不同的元素存于數(shù)組A 1 n 中 另設一數(shù)組C 1 n 對每個元素A i C i 存放A中值小于A i 的元素的個數(shù) 則C i 0的元素即為最小元素 然后根據(jù)C的值大小將A中的元素重新排列 這種方法稱為計數(shù)排序 試編程實現(xiàn)之 10 5基數(shù)排序 基數(shù)排序 radixsort 是和前面所介紹的排序方法 基于比較的排序方法 完全不同的一種排序方法 它是一種分配排序 多關鍵字排序 如52張撲克牌按以下規(guī)則排成有序 可以看出 牌點是決定大小的主要因數(shù) 3 4 10 J Q K A 2 花色則是決定大小的次要因數(shù) Diamond Club Heart Spade 只有在牌點相同時 它才起作用 因此我們稱牌點為高位關鍵字 花色為 D3 C3 H3 S3 D4 C4 HA SA D2 C2 H2 S2 一般的 設有n個記錄序列 R1 R2 Rn 每個記錄Ri均含有d個關鍵字 Ki1 Ki2 Kid 則稱此序列對關鍵字 K1 K2 Kd 有序 是指序列中任意兩個記錄Ri和Rj 1 i j n 都滿足有序關系 Ki1 Ki2 Kid Kj1 Kj2 Kjd 其中K1稱為最高位關鍵字 Kd稱為最低位關鍵字 那么應如何實現(xiàn)序列的多關鍵字排序呢 低位關鍵字 決定元素的大小主要看高位關鍵字 低位關鍵字只有在高位關鍵字相等時才發(fā)揮作用 LSD法 將待排序列依次按Kd Kd 1 K1進行排序得到有序序列 這種排序方法稱為最低位優(yōu)先法 LeastSignificantDigitfirst MSD法 將序列先按K1進行排序 則序列將分成若干子序列 每個子序列中的記錄均具有相同的K1值 然后再分別對各子序列按K2進行排序 則序列將分成更多的子序列 反復此過程 直到全部子序列分別按Kd進行了排序后 再將所有子序列依次聯(lián)接成一個有序序列 這種排序方法稱為最高位優(yōu)先法 MostSignificantDigitfirst MSD與LSD各有什么特點呢 MSD在排序時間上要比LSD快些 且每次對排序方法是否穩(wěn)定沒有要求 但操作起來相對復雜 因為序列將被分成若干個子序列 而LSD每次均對全部記錄進行排序 但除按低位關鍵字排序?qū)Ψ€(wěn)定性沒有要求外 其后的所有排序方法均需是穩(wěn)定的 LSD比較容易用多次分配和收集來實現(xiàn) 鏈式基數(shù)排序 基數(shù)排序是將關鍵字看成d個關鍵字復合而成 即按其基數(shù)rd所處位置的權(quán)值大小分成高 低位關鍵字 再應用多次分配 收集方法將待排序列排成有序序列 該方法又稱為桶排序 bucketsort 待排序列用靜態(tài)鏈表存儲 是用2rd個指針來作為rd個桶的底和蓋指針 每次分配即將n個記錄按其Ki分配到各個桶中 收集時則按各桶順序從上到下依次收集 待排序列 22 12 91 26 74 53 51 85 22 12 91 26 74 53 51 85 收集 91 51 22 12 53 74 85 26 收集 12 22 26 51 53 74 85 91 91 22 12 53 74 85 26 51 10 6前面介紹的各種內(nèi)部排序方法的比較 一次分配的時間為O n 一次收集的時間為O rd 故基數(shù)排序的時間復雜度為O d n rd 基于比較的排序方法 最好的時間復雜度是O nlogn 下面介紹一種公式分組