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

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