北京師范大學(xué)數(shù)據(jù)結(jié)構(gòu)教學(xué)資料第9章-排序

140 1 概述插入排序交換排序選擇排序歸并排序基數(shù)排序 第九章排序 140 2 概述 排序 將一組雜亂無(wú)章的數(shù)據(jù)按一定的規(guī)律順次排列起來(lái) 數(shù)據(jù)表 dataList 它是待排序數(shù)據(jù)元素的有限集合 排序碼 key 通常數(shù)據(jù)元素有多個(gè)屬性域 即多個(gè)數(shù)據(jù)成員組成 其中有一個(gè)屬性域可用來(lái)區(qū)分元素 作為排序依據(jù) 該域即為排序碼 每個(gè)數(shù)據(jù)表用哪個(gè)屬性域作為排序碼 要視具體的應(yīng)用需要而定 140 3 排序算法的穩(wěn)定性 如果在元素序列中有兩個(gè)元素r i 和r j 它們的排序碼k i k j 且在排序之前 元素r i 排在r j 前面 如果在排序之后 元素r i 仍在元素r j 的前面 則稱(chēng)這個(gè)排序方法是穩(wěn)定的 否則稱(chēng)這個(gè)排序方法是不穩(wěn)定的 內(nèi)排序與外排序 內(nèi)排序是指在排序期間數(shù)據(jù)元素全部存放在內(nèi)存的排序 外排序是指在排序期間全部元素個(gè)數(shù)太多 不能同時(shí)存放在內(nèi)存 必須根據(jù)排序過(guò)程的要求 不斷在內(nèi) 外存之間移動(dòng)的排序 140 4 排序的時(shí)間開(kāi)銷(xiāo) 排序的時(shí)間開(kāi)銷(xiāo)是衡量算法好壞的最重要的標(biāo)志 排序的時(shí)間開(kāi)銷(xiāo)可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來(lái)衡量 算法運(yùn)行時(shí)間代價(jià)的大略估算一般都按平均情況進(jìn)行估算 對(duì)于那些受元素排序碼序列初始排列及元素個(gè)數(shù)影響較大的 需要按最好情況和最壞情況進(jìn)行估算 算法執(zhí)行時(shí)所需的附加存儲(chǔ) 評(píng)價(jià)算法好壞的另一標(biāo)準(zhǔn) 140 5 待排序數(shù)據(jù)表的類(lèi)定義 includeconstintDefaultSize 100 templateclassdataList 數(shù)據(jù)表類(lèi)定義private T Vector 存儲(chǔ)排序元素的向量intmaxSize 向量中最大元素個(gè)數(shù)intcurrentSize 當(dāng)前元素個(gè)數(shù)public dataList intmaxSz DefaultSize 構(gòu)造函數(shù)maxSize maxSz currentSize 0 Vector newT maxSize 140 6 intLength returncurrentSize 取表長(zhǎng)度voidSwap T 140 7 插入排序 InsertSorting 基本方法是 每步將一個(gè)待排序的元素 按其排序碼大小 插入到前面已經(jīng)排好序的一組元素的適當(dāng)位置上 直到元素全部插入為止 基本思想是 當(dāng)插入第i i 1 個(gè)元素時(shí) 前面的V 0 V 1 V i 1 已經(jīng)排好序 這時(shí) 用V i 的排序碼與V i 1 V i 2 的排序碼順序進(jìn)行比較 找到插入位置即將V i 插入 原來(lái)位置上的元素向后順移 直接插入排序 InsertSort 140 8 各趟排序結(jié)果 i 1 i 2 140 9 012345 i 4 i 5 i 3 140 10 i 4時(shí)的排序過(guò)程 完成 i 4j 2 140 11 25 16 012345temp 21 49 25 08 16 25 i 4j 1 i 4j 0 i 4j 1 140 12 直接插入排序的算法 include dataList h templatevoidInsertSort dataList 140 13 do L j 1 L j j while j left 算法分析設(shè)待排序元素個(gè)數(shù)為currentSize n 則該算法的主程序執(zhí)行n 1趟 排序碼比較次數(shù)和元素移動(dòng)次數(shù)與元素排序碼的初始排列有關(guān) 140 14 最好情況下 排序前元素已按排序碼從小到大有序 每趟只需與前面有序元素序列的最后一個(gè)元素比較1次 總的排序碼比較次數(shù)為n 1 元素移動(dòng)次數(shù)為0 最壞情況下 第i趟時(shí)第i個(gè)元素必須與前面i個(gè)元素都做排序碼比較 并且每做1次比較就要做1次數(shù)據(jù)移動(dòng) 則總排序碼比較次數(shù)KCN和元素移動(dòng)次數(shù)RMN分別為 140 15 平均情況下排序的時(shí)間復(fù)雜度為o n2 直接插入排序是一種穩(wěn)定的排序方法 基本思想是 設(shè)在順序表中有一個(gè)元素序列V 0 V 1 V n 1 其中 V 0 V 1 V i 1 是已經(jīng)排好序的元素 在插入V i 時(shí) 利用折半搜索法尋找V i 的插入位置 折半插入排序的算法 include dataList h 折半插入排序 BinaryInsertsort 140 16 templatevoidBinaryInsertSort dataList 取中點(diǎn) 140 17 if temp low k L k 1 L k 成塊移動(dòng) 空出插入位置L low temp 插入 算法分析折半搜索比順序搜索快 所以折半插入排序就 140 18 平均性能來(lái)說(shuō)比直接插入排序要快 它所需的排序碼比較次數(shù)與待排序元素序列的初始排列無(wú)關(guān) 僅依賴(lài)于元素個(gè)數(shù) 在插入第i個(gè)元素時(shí) 需要經(jīng)過(guò) log2i 1次排序碼比較 才能確定它應(yīng)插入的位置 因此 將n個(gè)元素 為推導(dǎo)方便 設(shè)為n 2k 用折半插入排序所進(jìn)行的排序碼比較次數(shù)為 折半插入排序是一個(gè)穩(wěn)定的排序方法 140 19 當(dāng)n較大時(shí) 總排序碼比較次數(shù)比直接插入排序的最壞情況要好得多 但比其最好情況要差 在元素的初始排列已經(jīng)按排序碼排好序或接近有序時(shí) 直接插入排序比折半插入排序執(zhí)行的排序碼比較次數(shù)要少 折半插入排序的元素移動(dòng)次數(shù)與直接插入排序相同 依賴(lài)于元素的初始排列 140 20 希爾排序方法又稱(chēng)為縮小增量排序 該方法的基本思想是 設(shè)待排序元素序列有n個(gè)元素 首先取一個(gè)整數(shù)gap n作為間隔 將全部元素分為gap個(gè)子序列 所有距離為gap的元素放在同一個(gè)子序列中 在每一個(gè)子序列中分別 希爾排序 ShellSort 140 21 施行直接插入排序 然后縮小間隔gap 例如取gap gap 2 重復(fù)上述的子序列劃分和排序工作 直到最后取gap 1 將所有元素放在同一個(gè)序列中排序?yàn)橹?開(kāi)始時(shí)gap的值較大 子序列中的元素較少 排序速度較快 隨著排序進(jìn)展 gap值逐漸變小 子序列中元素個(gè)數(shù)逐漸變多 由于前面工作的基礎(chǔ) 大多數(shù)元素已基本有序 所以排序速度仍然很快 140 22 140 23 21 25 49 25 16 08 012345 21 i 2 08 49 Gap 2 25 16 49 16 25 08 21 25 49 25 08 16 21 25 25 140 24 21 25 49 25 16 08 012345 21 i 3 08 Gap 1 25 16 49 25 include dataList h template 希爾排序的算法 140 25 voidShellsort dataList 140 26 L j gap temp 將vector i 回送 while gap 1 算法分析Gap的取法有多種 最初shell提出取gap n 2 gap gap 2 直到gap 1 knuth提出取gap gap 3 1 還有人提出都取奇數(shù)為好 也有人提出各gap互質(zhì)為好 對(duì)特定的待排序元素序列 可以準(zhǔn)確地估算排序碼的比較次數(shù)和元素移動(dòng)次數(shù) 140 27 想要弄清排序碼比較次數(shù)和元素移動(dòng)次數(shù)與增量選擇之間的依賴(lài)關(guān)系 并給出完整的數(shù)學(xué)分析 還沒(méi)有人能夠做到 Knuth利用大量實(shí)驗(yàn)統(tǒng)計(jì)資料得出 當(dāng)n很大時(shí) 排序碼平均比較次數(shù)和元素平均移動(dòng)次數(shù)大約在n1 25到1 6n1 25的范圍內(nèi) 這是在利用直接插入排序作為子序列排序方法的情況下得到的 希爾排序是一種不穩(wěn)定的排序方法 140 28 交換排序 ExchangeSort 基本思想是兩兩比較待排序元素的排序碼 如果發(fā)生逆序 即排列順序與排序后的次序正好相反 則交換之 直到所有元素都排好序?yàn)橹?基本方法是 設(shè)待排序元素序列中的元素個(gè)數(shù)為n 最多作n 1趟 i 1 2 n 1 在第i趟中從后向前 j n 1 n 2 i 順次兩兩比較V j 1 key和V j key 如果發(fā)生逆序 則交換V j 1 和V j 起泡排序 BubbleSort 140 29 21 25 49 25 16 08 012345 21 25 i 1 49 25 16 25 16 08 49 Exchang 1 08 25 49 21 Exchang 1 i 2 i 3 08 16 Exchang 1 25 25 21 140 30 25 012345 i 4 49 16 Exchang 0 08 25 21 起泡排序的算法 templatevoidBubbleSort dataListj 140 31 if L j 1 L j 逆序Swap L j 1 L j 交換exchange 1 標(biāo)志置為1 有交換 pass 算法分析第i趟對(duì)待排序元素序列V i 1 V i V right 進(jìn)行排序 結(jié)果將該序列中排序碼最小的元素交換到序列的第一個(gè)位置 i 1 140 32 最多做n 1趟起泡就能把所有元素排好序 在元素的初始排列已經(jīng)按排序碼從小到大排好序時(shí) 此算法只執(zhí)行一趟起泡 做n 1次排序碼比較 不移動(dòng)元素 這是最好的情形 最壞的情形是算法執(zhí)行n 1趟起泡 第i趟 1 i n 做n i次排序碼比較 執(zhí)行n i次元素交換 在最壞情形下總的排序碼比較次數(shù)KCN和元素移動(dòng)次數(shù)RMN為 140 33 起泡排序需要一個(gè)附加元素以實(shí)現(xiàn)元素值的對(duì)換 起泡排序是一個(gè)穩(wěn)定的排序方法 基本思想是任取待排序元素序列中的某個(gè)元素 例如取第一個(gè)元素 作為基準(zhǔn) 按照該元素的排序碼大小 將整個(gè)元素序列劃分為左右兩個(gè)子序列 左側(cè)子序列中所有元素的排序碼都小于或等于基準(zhǔn)元素的排序碼 快速排序 QuickSort 140 34 右側(cè)子序列中所有元素的排序碼都大于基準(zhǔn)元素的排序碼基準(zhǔn)元素則排在這兩個(gè)子序列中間 這也是該元素最終應(yīng)安放的位置 然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法 直到所有的元素都排在相應(yīng)位置上為止 140 35 QuickSort List if List的長(zhǎng)度大于1 將序列List劃分為兩個(gè)子序列LeftList和RightList QuickSort LeftList QuickSort RightList 將兩個(gè)子序列LeftList和RightList合并為一個(gè)序列List 算法描述 140 36 21 25 49 25 16 08 012345 21 25 i 1 49 25 16 25 16 08 49 pivot 08 25 49 21 i 2 i 3 08 16 25 25 21 pivot pivot pivot 140 37 21 25 49 25 16 08 012345 25 i 1劃分 25 16 25 16 08 49 pivotpos 08 25 49 08 16 25 25 21 pivotpos 21 比較4次交換25 16 i i pivotpos 21 比較1次交換49 08 49 lowpivotpos 交換21 08 140 38 快速排序的算法 include dataList h templatevoidQuickSort dataList 140 39 QuickSort L pivotpos 1 right templateintdataList Partition constintlow constinthigh 數(shù)據(jù)表類(lèi)的共有函數(shù)intpivotpos low Tpivot Vector low 基準(zhǔn)元素for inti low 1 i high i 檢測(cè)整個(gè)序列 進(jìn)行劃分 140 40 if Vector i pivot pivotpos if pivotpos i Swap Vector pivotpos Vector i 小于基準(zhǔn)的交換到左側(cè)去Vector low Vector pivotpos Vector pivotpos pivot 將基準(zhǔn)元素就位returnpivotpos 返回基準(zhǔn)元素位置 算法分析 140 41 算法quicksort是一個(gè)遞歸的算法 其遞歸樹(shù)如圖所示 算法partition利用序列第一個(gè)元素作為基準(zhǔn) 將整個(gè)序列劃分為左右兩個(gè)子序列 算法中執(zhí)行了一個(gè)循環(huán) 只要是排序碼小于基準(zhǔn)元素排序碼的元素都移到序列左側(cè) 最后基準(zhǔn)元素安 140 42 到位 函數(shù)返回其位置 從快速排序算法的遞歸樹(shù)可知 快速排序的趟數(shù)取決于遞歸樹(shù)的高度 如果每次劃分對(duì)一個(gè)元素定位后 該元素的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同 則下一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序 這是最理想的情況 在n個(gè)元素的序列中 對(duì)一個(gè)元素定位所需時(shí)間為O n 若設(shè)t n 是對(duì)n個(gè)元素的序列進(jìn)行排序所需的時(shí)間 且每次對(duì)一個(gè)元素正確定位后 正好把序列分為長(zhǎng)度相等的兩個(gè)子序列 140 43 此時(shí) 總的計(jì)算時(shí)間為 T n cn 2T n 2 c是一個(gè)常數(shù) cn 2 cn 2 2T n 4 2cn 4T n 4 2cn 4 cn 4 2T n 8 3cn 8T n 8 cnlog2n nT 1 O nlog2n 可以證明 函數(shù)quicksort的平均計(jì)算時(shí)間也是O nlog2n 實(shí)驗(yàn)結(jié)果表明 就平均計(jì)算時(shí)間而言 快速排序是內(nèi)排序方法中最好的一個(gè) 快速排序是遞歸的 需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù) 140 44 最大遞歸調(diào)用層次數(shù)與遞歸樹(shù)高度一致 理想情況為 log2 n 1 存儲(chǔ)開(kāi)銷(xiāo)為O log2n 在最壞的情況 即待排序元素序列已經(jīng)按其排序碼從小到大排好序的情況下 其遞歸樹(shù)成為單支樹(shù) 每次劃分只得到一個(gè)比上一次少一個(gè)元素的子序列 必須經(jīng)過(guò)n 1趟才能把所有元素定位 而且第i趟需要經(jīng)過(guò)n i次排序碼比較才能找到第i個(gè)元素的安放位置 總的排序碼比較次數(shù)將達(dá)到 140 45 用第一個(gè)元素作為基準(zhǔn)元素 快速排序退化的例子 0816212525 49 08 012345pivot 初始 16212525 49 08 16 212525 49 21 0816 25 2525 49 081621 25 49 25 08162125 49 0816212525 i 1 i 2 i 3 i 4 i 5 140 46 用居中排序碼元素作為基準(zhǔn)元素 0816212525 49 012345pivot 21 初始 0816 21 2525 49 08 25 08 16 21 25 25 49 i 1 i 2 其排序速度退化到簡(jiǎn)單排序的水平 比直接插入排序還慢 占用附加存儲(chǔ) 棧 將達(dá)到O n 改進(jìn)辦法 取每個(gè)待排序元素序列的第一個(gè)元素 最后一個(gè)元素和位置接近正中的3個(gè)元素 取其排序碼居中者作為基準(zhǔn)元素 140 47 快速排序是一種不穩(wěn)定的排序方法 對(duì)于n較大的平均情況而言 快速排序是 快速 的 但是當(dāng)n很小時(shí) 這種排序方法往往比其它簡(jiǎn)單排序方法還要慢 因此 當(dāng)n很小時(shí)可以用直接插入排序方法 140 48 選擇排序 基本思想是 每一趟 例如第i趟 i 0 1 n 2 在后面n i個(gè)待排序元素中選出排序碼最小的元素 作為有序元素序列的第i個(gè)元素 待到第n 2趟作完 待排序元素只剩下1個(gè) 就不用再選了 140 49 直接選擇排序 SelectSort 直接選擇排序的基本步驟是 在一組元素V i V n 1 中選擇具有最小排序碼的元素 若它不是這組元素中的第一個(gè)元素 則將它與這組元素中的第一個(gè)元素對(duì)調(diào) 在這組元素中剔除這個(gè)具有最小排序碼的元素 在剩下的元素V i 1 V n 1 中重復(fù)執(zhí)行第 步 直到剩余元素只有一個(gè)為止 140 50 21 25 49 25 16 08 012345 21 25 i 0 49 25 16 25 16 08 49 08 25 49 21 i 1 i 2 08 16 25 25 21 初始 最小者08交換21 08 最小者16交換25 16 最小者21交換49 21 140 51 49 25 012345 25 i 4 25 16 08 49 25 49 21 結(jié)果 i 3 08 16 25 21 最小者25 無(wú)交換 最小者25無(wú)交換 25 21 16 08 各趟排序后的結(jié)果 140 52 直接選擇排序的算法 include dataList h templatevoidSelectSort dataList 交換 140 53 i 1時(shí)選擇排序的過(guò)程 140 54 k指示當(dāng)前序列中最小者 140 55 直接選擇排序的排序碼比較次數(shù)KCN與元素的初始排列無(wú)關(guān) 設(shè)整個(gè)待排序元素序列有n個(gè)元素 則第i趟選擇具有最小排序碼元素所需的比較次數(shù)總是n i 1次 總的排序碼比較次數(shù)為元素移動(dòng)次數(shù)與元素序列初始排列有關(guān) 當(dāng)這組元素初始狀態(tài)是按其排序碼從小到大有序的時(shí)候 元素的移動(dòng)次數(shù)達(dá)到最少RMN 0 140 56 最壞情況是每一趟都要進(jìn)行交換 總的元素移動(dòng)次數(shù)為RMN 3 n 1 直接選擇排序是一種不穩(wěn)定的排序方法 若待排序的數(shù)據(jù)元素順序存放于單鏈表中 每一趟排序先在鏈表中選擇關(guān)鍵碼值最大的元素 將它從鏈中摘下 再插入一個(gè)初始為空的新鏈表的首部 當(dāng)所有元素都從原鏈表中摘下并插入到新鏈表中 則新鏈表中元素已經(jīng)有序鏈接起來(lái) 鏈表直接選擇排序 140 57 鏈表直接選擇排序的算法 include staticList h templateintselectSort staticLinkedList s指示當(dāng)前最大元素while p 0 140 58 if L p data L s data s p r q 記憶當(dāng)前找到的排序碼最大結(jié)點(diǎn)q p p L p link if s f f L f link 結(jié)點(diǎn)s從鏈中摘下elseL r link L s link L s link L 0 link L 0 link s 結(jié)點(diǎn)s插入到結(jié)果鏈表的前端 140 59 它的思想與體育比賽時(shí)的淘汰賽類(lèi)似 首先取得n個(gè)元素的排序碼 進(jìn)行兩兩比較 得到 n 2 個(gè)比較的優(yōu)勝者 排序碼小者 作為第一步比較的結(jié)果保留下來(lái) 然后對(duì)這 n 2 個(gè)元素再進(jìn)行排序碼的兩兩比較 如此重復(fù) 直到選出一個(gè)排序碼最小的元素為止 由于每次兩兩比較的結(jié)果是把排序碼小者作為優(yōu)勝者上升到雙親結(jié)點(diǎn) 所以稱(chēng)這種比賽樹(shù)為勝者樹(shù) 錦標(biāo)賽排序 TournamentTreeSort 140 60 在圖例中 最下面是元素排列的初始狀態(tài) 相當(dāng)于一棵完全二叉樹(shù)的葉結(jié)點(diǎn) 它存放的是所有參加排序的元素的排序碼 140 61 在勝者樹(shù)中 位于最底層的葉結(jié)點(diǎn)叫做勝者樹(shù)的外結(jié)點(diǎn) 非葉結(jié)點(diǎn)稱(chēng)為勝者樹(shù)的內(nèi)結(jié)點(diǎn) 勝者樹(shù)最頂層是樹(shù)的根 表示最后選擇出來(lái)的具有最小排序碼的元素 外結(jié)點(diǎn)的個(gè)數(shù)為n時(shí) 內(nèi)結(jié)點(diǎn)的個(gè)數(shù)為n 1 定義根到最遠(yuǎn)層內(nèi)結(jié)點(diǎn)的路徑長(zhǎng)度s為從根到該內(nèi)結(jié)點(diǎn)路徑上的分支條數(shù) 則有s log2 n 1 這樣 最遠(yuǎn)層最左端的內(nèi)結(jié)點(diǎn)的編號(hào)為2s 最遠(yuǎn)層的內(nèi)結(jié)點(diǎn)個(gè)數(shù)為n 2s 而最遠(yuǎn)層外結(jié)點(diǎn)個(gè)數(shù)等于最遠(yuǎn)層內(nèi)結(jié)點(diǎn)個(gè)數(shù)的2倍 140 62 上例中 外結(jié)點(diǎn)數(shù)n 7 s log26 2 最遠(yuǎn)層最左端的內(nèi)結(jié)點(diǎn)編號(hào)為2s 4 該層的內(nèi)結(jié)點(diǎn)數(shù)共有m n 2s 7 4 3 最遠(yuǎn)層的外結(jié)點(diǎn)數(shù)為lowExt 2m 6 次遠(yuǎn)層最左端的外部結(jié)點(diǎn)編號(hào)為lowExt 1 7 140 63 若已知某外結(jié)點(diǎn)的編號(hào)為i 則其雙親結(jié)點(diǎn) 內(nèi)結(jié)點(diǎn) 的編號(hào)為k 則 其中offset 2s 1 1 指最遠(yuǎn)層最左端外結(jié)點(diǎn)之前結(jié)點(diǎn) 包括所有內(nèi)結(jié)點(diǎn)和次遠(yuǎn)層外結(jié)點(diǎn) 個(gè)數(shù) i lowExt即最遠(yuǎn)層外結(jié)點(diǎn) i lowExt即次遠(yuǎn)層外結(jié)點(diǎn) 140 64 勝者樹(shù)的類(lèi)定義 templateclassWinnerTree private intmaxSize 允許的最大選手?jǐn)?shù)intn 當(dāng)前大小 外部結(jié)點(diǎn)數(shù) intlowExt 最遠(yuǎn)層外部結(jié)點(diǎn)數(shù)intoffset 偏移 加1即為第1個(gè)外結(jié)點(diǎn) int t 勝者樹(shù)數(shù)組T e 選手?jǐn)?shù)組voidPlay intk intlc intrc int Winner inta intb 140 65 public constTmaxValue 序列中不可能的大值WinnerTree intTreeSize 20 構(gòu)造函數(shù) maxSize TreeSize n 0 t newint TreeSize WinnerTree delete t 析構(gòu)函數(shù)boolInitial Ta intsize int Winner inta intb boolrePlay inti int Winner inta intb 重構(gòu)voidUpdate e t 1 maxValue 修改intWinner const return n 0 t 1 0 取最終勝者 140 66 intWinner inti const return iboolWinnerTree Initial Ta intsize int Winner inta intb a 是勝者樹(shù)選手?jǐn)?shù)組 size是選手?jǐn)?shù) 函數(shù)Winner 用于得到兩選手a b比賽的勝者 初始化勝者樹(shù)的算法 140 67 if size maxSize size 2 returnfalse n size e a inti s for s 1 2 s n 1 s s 計(jì)算s 2 log2 n 1 lowExt 2 n s offset 2 s 1 for i 2 i lowExt i 2 最遠(yuǎn)層外結(jié)點(diǎn)比賽Play offset i 2 i 1 i Winner 選手i 1和i比賽 勝者升入雙親 offset i 2if n 2 0 i lowExt 2 次遠(yuǎn)層外結(jié)點(diǎn)比賽else 當(dāng)n為奇數(shù)時(shí) 內(nèi)結(jié)點(diǎn)要與外結(jié)點(diǎn)比賽Play n 2 t n 1 lowExt 1 Winner 140 68 i lowExt 3 i再進(jìn)到次遠(yuǎn)層其他外結(jié)點(diǎn) for i n i 2 其他次遠(yuǎn)層外結(jié)點(diǎn)比賽Play i lowExt n 1 2 i 1 i Winner returntrue 通過(guò)初始化操作 形成勝者樹(shù) 最后勝者進(jìn)入樹(shù)的根結(jié)點(diǎn) 此操作調(diào)用n 2次Play算法 而Play算法逐層向上比較 次數(shù)不超過(guò) log2n 140 69 templatevoidWinnerTree Play intk intlc intrc int Winner inta intb 通過(guò)比賽對(duì)樹(shù)初始化 在t k 處開(kāi)始比賽 lc和rc是 t k 的左子女和右子女 t k Winner lc rc 在e lc 和e rc 間選出勝者while k 1 到雙親結(jié)點(diǎn) 140 70 重新比賽 重構(gòu)勝者樹(shù)的算法 一旦選手i最后勝者 就將其值改為 使得以后不再參選 此時(shí) 需要重新進(jìn)行外結(jié)點(diǎn)e i 到根t 1 路徑上的比賽 重新執(zhí)行從勝者對(duì)應(yīng)的外結(jié)點(diǎn)到根的路徑上的比賽次數(shù)等于e i 到根t 1 的路徑上的分支數(shù) templateboolWinnerTree rePlay inti int Winner inta intb 針對(duì)元素i值的改變 重新組織勝者樹(shù) 140 71 if in returnfalse intk lc rc 比賽結(jié)點(diǎn)及其左右子女if i lowExt 最遠(yuǎn)層外結(jié)點(diǎn)k offset i 2 計(jì)算i的雙親lc 2 k offset rc lc 1 計(jì)算左右子女 else 次遠(yuǎn)層外結(jié)點(diǎn)k i lowExt n 1 2 if 2 k n 1 lc t 2 k rc i else lc 2 k n 1 lowExt rc lc 1 140 72 t k Winner lc rc k 2 for k 1 k 2 逐層向上比賽直到根t k Winner t 2 k t 2 k 1 templatevoidTournamentSort Ta constintleft constintright 建立樹(shù)的順序存儲(chǔ)數(shù)組tree 將數(shù)組a 中的元素復(fù) 錦標(biāo)賽排序的算法 140 73 復(fù)制到勝者樹(shù)中 對(duì)它們進(jìn)行排序 并把結(jié)果返送 回?cái)?shù)組中 left和right是排序元素的起點(diǎn)和終點(diǎn) size right left 1 待排序元素個(gè)數(shù)WinnerTreeWT size 勝者樹(shù)對(duì)象Tdata size 1 存儲(chǔ)輸入數(shù)據(jù)inti for i 1 i data i WT Initial data size Winner 構(gòu)造初始勝者樹(shù)for i 0 i size i a i WT Winner 輸出勝者WT Update 修改勝者的值 140 74 WT rePlay t 1 Winner 重構(gòu)勝者樹(shù)if WT Winner maxValue break 勝者樹(shù)是完全二叉樹(shù) 其高度為 log2n 其中n為待排序元素個(gè)數(shù) 除第一次選擇具有最小排序碼的元素需要進(jìn)行n 1次排序碼比較外 重構(gòu)勝者樹(shù)選擇次小 再次小排序碼所需的比較次數(shù)均為O log2n 總排序碼比較次數(shù)為O nlog2n 140 75 形成初始勝者樹(shù) 最小排序碼上升到根 排序碼比較次數(shù) 6 Winner 勝者 e 6 08 VS VS VS VS VS VS 140 76 排序碼比較次數(shù) 3 Winner 勝者 e 5 16 VS VS 輸出冠軍e 6 08并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài) VS 140 77 排序碼比較次數(shù) 3 Winner 勝者 e 1 21 VS VS 輸出冠軍e 5 16并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài) VS 140 78 排序碼比較次數(shù) 3 Winner 勝者 e 2 25 VS VS 輸出冠軍e 1 21并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài) VS 140 79 排序碼比較次數(shù) 3 Winner 勝者 e 4 25 VS VS 輸出冠軍e 2 25并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài) VS 140 80 排序碼比較次數(shù) 3 Winner 勝者 e 3 49 VS VS 輸出冠軍e 4 25 并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài) VS 140 81 排序碼比較次數(shù) 3 Winner 勝者 e 7 63 VS VS 輸出冠軍e 3 49并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài) VS 140 82 這種排序方法雖然減少了許多排序時(shí)間 但是使用了較多的附加存儲(chǔ) 如果有n個(gè)元素 必須使用至少2n 1個(gè)結(jié)點(diǎn)來(lái)存放勝者樹(shù) 錦標(biāo)賽排序是一個(gè)穩(wěn)定的排序方法 140 83 堆排序 HeapSort 利用堆及其運(yùn)算 可以很容易地實(shí)現(xiàn)選擇排序的思路 堆排序分為兩個(gè)步驟根據(jù)初始輸入數(shù)據(jù) 利用堆的調(diào)整算法siftDown 形成初始堆 通過(guò)一系列的元素交換和重新調(diào)整堆進(jìn)行排序 為了實(shí)現(xiàn)元素按排序碼從小到大排序 要求建立最大堆 140 84 建立初始的最大堆 140 85 21 25 25 49 16 08 0 1 2 3 4 5 i 49 25 25 16 21 08 0 2 5 4 3 1 21254925 1608 49252125 1608 i 0時(shí)的局部調(diào)整形成最大堆 i 1時(shí)的局部調(diào)整 140 86 最大堆的向下調(diào)整算法 templatesiftDown dataList temp排序碼大不調(diào)整 140 87 else 否則子女中的大者上移L i L j i j j 2 j 1 i下降到子女位置 L i temp temp放到合適位置 最大堆堆頂L Vector 0 具有最大的排序碼 將L Vector 0 與L Vector n 1 對(duì)調(diào) 把具有最大 基于初始堆進(jìn)行堆排序 140 88 排序碼的元素交換到最后 再對(duì)前面的n 1個(gè)元素 使用堆的調(diào)整算法siftDown L 0 n 2 重新建立最大堆 具有次最大排序碼的元素又上浮到L Vector 0 位置 再對(duì)調(diào)L Vector 0 和L Vector n 2 再調(diào)用siftDown L 0 n 3 對(duì)前面的n 2個(gè)元素重新調(diào)整 如此反復(fù)執(zhí)行 最后得到全部排序好的元素序列 這個(gè)算法即堆排序算法 其細(xì)節(jié)在下面的程序中給出 140 89 49 25 25 21 16 08 0 1 2 3 4 5 08 25 25 16 21 49 0 2 5 4 3 1 49252125 1608 08252125 1649 交換0號(hào)與5號(hào)元素 5號(hào)元素就位 初始最大堆 140 90 25 25 08 21 16 49 0 1 2 3 4 5 16 25 08 25 21 49 0 2 5 4 3 1 2525 21081649 1625 21082549 交換0號(hào)與4號(hào)元素 4號(hào)元素就位 從0號(hào)到4號(hào)重新調(diào)整為最大堆 140 91 25 16 08 21 25 49 0 1 2 3 4 5 08 16 25 25 21 49 0 2 5 4 3 1 25 1621082549 08162125 2549 交換0號(hào)與3號(hào)元素 3號(hào)元素就位 從0號(hào)到3號(hào)重新調(diào)整為最大堆 140 92 21 16 25 08 25 49 0 1 2 3 4 5 08 16 25 25 21 49 0 2 5 4 3 1 21160825 2549 08162125 2549 交換0號(hào)與2號(hào)元素 2號(hào)元素就位 從0號(hào)到2號(hào)重新調(diào)整為最大堆 140 93 16 08 25 21 25 49 0 1 2 3 4 5 08 16 25 25 21 49 0 2 5 4 3 1 16082125 2549 08162125 2549 交換0號(hào)與1號(hào)元素 1號(hào)元素就位 從0號(hào)到1號(hào)重新調(diào)整為最大堆 140 94 堆排序的算法 templatevoidHeapSort dataList 140 95 算法分析設(shè)堆中有n個(gè)結(jié)點(diǎn) 且2k 1 n 2k 則對(duì)應(yīng)的完全二叉樹(shù)有k層 在第i層上的結(jié)點(diǎn)數(shù) 2i 1 i 1 k 在第一個(gè)形成初始堆的for循環(huán)中對(duì)每一個(gè)非葉結(jié)點(diǎn)調(diào)用了一次堆調(diào)整算法siftDown 該循環(huán)所用的計(jì)算時(shí)間為 其中 i是層次編號(hào) 2i 1是第i層的最大結(jié)點(diǎn)數(shù) k i 是第i層結(jié)點(diǎn)能夠移動(dòng)的最大距離 140 96 第二個(gè)for循環(huán)中調(diào)用了n 1次siftDown 算法 該循環(huán)的計(jì)算時(shí)間為O nlog2n 因此 堆排序的時(shí)間復(fù)雜性為O nlog2n 該算法的附加存儲(chǔ)主要是在第二個(gè)for循環(huán)中用來(lái)執(zhí)行元素交換時(shí)所用的一個(gè)臨時(shí)元素 因此 該算法的空間復(fù)雜性為O 1 堆排序是一個(gè)不穩(wěn)定的排序方法 140 97 歸并排序 MergeSort 歸并 是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表 元素序列L1中有兩個(gè)有序表Vector left mid 和Vector mid 1 right 它們可歸并成一個(gè)有序表 存于另一元素序列L2的Vector left right 中 這種方法稱(chēng)為兩路歸并 2 waymerging 變量i和j分別是表Vector left mid 和Vector mid 1 right 的檢測(cè)指針 k是存放指針 140 98 當(dāng)i和j都在兩個(gè)表的表長(zhǎng)內(nèi)變化時(shí) 根據(jù)對(duì)應(yīng)項(xiàng)的排序碼的大小 依次把排序碼小的元素排放到新表k所指位置中 當(dāng)i與j中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí) 將另一個(gè)表中的剩余部分照抄到新表中 140 99 迭代的歸并排序算法 迭代的歸并排序算法就是利用兩路歸并過(guò)程進(jìn)行排序 其基本思想是 設(shè)初始元素序列有n個(gè)元素 首先把它看成是n個(gè)長(zhǎng)度為1的有序子序列 歸并項(xiàng) 做兩兩歸并 得到 n 2 個(gè)長(zhǎng)度為2的歸并項(xiàng) 最后一個(gè)歸并項(xiàng)的長(zhǎng)度為1 再做兩兩歸并 得到 n 4 個(gè)長(zhǎng)度為4的歸并項(xiàng) 最后一個(gè)歸并項(xiàng)長(zhǎng)度可以短些 如此重復(fù) 最后得到一個(gè)長(zhǎng)度為n的有序序列 140 100 迭代的歸并排序算法 21 25 25 25 93 62 72 08 37 16 54 49 21 25 49 62 93 08 72 16 37 54 21 25 25 49 08 62 72 93 16 37 54 08 08 21 16 25 21 25 25 49 25 62 37 72 49 93 54 16 37 54 62 72 93 len 1 len 2 len 4 len 8 len 16 140 101 兩路歸并算法 include dataList h templatevoidmerge dataList s1 s2是檢測(cè)指針 t是存放指針 140 102 while i mid 若第二個(gè)表未檢測(cè)完 復(fù)制 140 103 一趟歸并排序的算法 設(shè)L1 Vector 0 n 1 中n個(gè)記錄已經(jīng)分為一些長(zhǎng)度為len的歸并項(xiàng) 將這些歸并項(xiàng)兩兩歸并成長(zhǎng)度為2len的歸并項(xiàng) 結(jié)果放到L2 中 如果n不是2len的整數(shù)倍 則一趟歸并到最后 可能遇到兩種情形 剩下一個(gè)長(zhǎng)度為len的歸并項(xiàng)和另一個(gè)長(zhǎng)度不足len的歸并項(xiàng) 可用merge算法將它們歸并成一個(gè)長(zhǎng)度小于2len的歸并項(xiàng) 只剩下一個(gè)歸并項(xiàng) 其長(zhǎng)度小于或等于len 將它直接復(fù)制到結(jié)果表中 140 104 templatevoidMergePass dataList 140 105 兩路 歸并排序的主算法 templatevoidMergeSort dataList 140 106 在迭代的歸并排序算法中 函數(shù)MergePass 做一趟兩路歸并排序 要調(diào)用merge 函數(shù) n 2 len O n len 次 函數(shù)MergeSort 調(diào)用MergePass 正好 log2n 次 而每次merge 要執(zhí)行比較O len 次 所以算法總的時(shí)間復(fù)雜度為O nlog2n 歸并排序占用附加存儲(chǔ)較多 需要另外一個(gè)與原待排序元素?cái)?shù)組同樣大小的輔助數(shù)組 這是這個(gè)算法的缺點(diǎn) 歸并排序是一個(gè)穩(wěn)定的排序方法 140 107 遞歸的鏈表歸并排序 與快速排序類(lèi)似 歸并排序也可以利用劃分為子序列的方法遞歸實(shí)現(xiàn) 算法的思路是 首先把整個(gè)待排序序列劃分為兩個(gè)長(zhǎng)度大致相等的部分 分別稱(chēng)之為左子表和右子表 對(duì)這些子表分別遞歸地進(jìn)行排序 然后再把排好序的兩個(gè)子表進(jìn)行歸并 圖示 待排序元素序列的排序碼為 21 25 49 25 16 08 先是進(jìn)行子表劃分 待到子表中只有一個(gè)元素時(shí)遞歸到底 再實(shí)施歸并 逐步退出遞歸調(diào)用的過(guò)程 140 108 21254925 1608 212549 25 1608 21 25 49 2549 21 25 1608 25 16 08 21254925 1608 1608 25 2549 21 遞歸 21 25 16 08 49 25 25 1608 212549 回推 140 109 靜態(tài)鏈表的兩路歸并算法 include staticList h templateintListMerge staticLinkedList 140 110 else L k link j k j j L j link if i 0 L k link j i鏈檢測(cè)完 j鏈接上elseL k link i j鏈檢測(cè)完 i鏈接上returnL 0 link 返回結(jié)果鏈頭指針 templateintrMergeSort staticLinkedlist L constintleft constintright 對(duì)鏈表L Vector left right 進(jìn)行排序 各個(gè)結(jié)點(diǎn)中 遞歸的歸并排序算法 140 111 的鏈域link應(yīng)初始化為0 rMergeSort返回排序后 鏈表第一個(gè)結(jié)點(diǎn)的下標(biāo) L Vector 0 是工作單元if left right returnleft intmid left right 2 returnListMerge L rMergeSort L left mid rMegerSort L mid 1 right 鏈表的歸并排序方法的遞歸深度為O log2n 元素排序碼的比較次數(shù)為O nlog2n 鏈表的歸并排序方法是一種穩(wěn)定的排序方法 140 112 基數(shù)排序是采用 分配 與 收集 的辦法 用對(duì)多排序碼進(jìn)行排序的思想實(shí)現(xiàn)對(duì)單排序碼進(jìn)行排序的方法 以撲克牌排序?yàn)槔?每張撲克牌有兩個(gè) 排序碼 花色和面值 其有序關(guān)系為 花色 面值 2 3 4 5 6 7 8 9 10 J Q K A 基數(shù)排序 RadixSort 多排序碼排序 140 113 如果我們把所有撲克牌排成以下次序 2 A 2 A 2 A 2 A這就是多排序碼排序 排序后形成的有序序列叫做詞典有序序列 對(duì)于上例兩排序碼的排序 可以先按花色排序 之后再按面值排序 也可以先按面值排序 再按花色排序 一般情況下 假定有一個(gè)n個(gè)元素的序列 V0 V1 Vn 1 且每個(gè)元素Vi中含有d個(gè)排序碼 140 114 如果對(duì)于序列中任意兩個(gè)元素Vi和Vj 0 i j n 1 都滿(mǎn)足 則稱(chēng)序列對(duì)排序碼 K1 K2 Kd 有序 其中 K1稱(chēng)為最高位排序碼 Kd稱(chēng)為最低位排序碼 如果排序碼是由多個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)項(xiàng)組 則依據(jù)它進(jìn)行排序時(shí)就需要利用多排序碼排序 實(shí)現(xiàn)多排序碼排序有兩種常用的方法 140 115 如果對(duì)于序列中任意兩個(gè)元素Vi和Vj 0 i j n 1 都滿(mǎn)足 則稱(chēng)序列對(duì)排序碼 K1 K2 Kd 有序 K1稱(chēng)為最高位排序碼 Kd稱(chēng)為最低位排序碼 如果排序碼是由多個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)項(xiàng)組 則依據(jù)它進(jìn)行排序時(shí)就需要利用多排序碼排序 實(shí)現(xiàn)多排序碼排序有兩種常用的方法 140 116 最高位優(yōu)先MSD MostSignificantDigitfirst 最低位優(yōu)先LSD LeastSignificantDigitfirst 最高位優(yōu)先法通常是一個(gè)遞歸的過(guò)程 先根據(jù)最高位排序碼K1排序 得到若干元素組 元素組中各元素都有相同排序碼K1 再分別對(duì)每組中元素根據(jù)排序碼K2進(jìn)行排序 按K2值的不同 再分成若干個(gè)更小的子組 每個(gè)子組中的元素具有相同的K1和K2值 依此重復(fù) 直到對(duì)排序碼Kd完成排序?yàn)橹?最后 把所有子組中的元素依次連接起來(lái) 140 117 就得到一個(gè)有序的元素序列 最低位優(yōu)先法首先依據(jù)最低位排序碼Kd對(duì)所有元素進(jìn)行一趟排序 再依據(jù)次低位排序碼Kd 1對(duì)上一趟排序的結(jié)果再排序 依次重復(fù) 直到依據(jù)排序碼K1最后一趟排序完成 就可以得到一個(gè)有序的序列 使用這種排序方法對(duì)每一個(gè)排序碼進(jìn)行排序時(shí) 不需要再分組 而是整個(gè)元素組都參加排序 LSD和MSD方法也可應(yīng)用于對(duì)一個(gè)排序碼進(jìn)行的排序 此時(shí)可將單排序碼Ki看作是一個(gè)子排序碼組 140 118 鏈?zhǔn)交鶖?shù)排序 基數(shù)排序是典型的LSD排序方法 利用 分配 和 收集 對(duì)單排序碼進(jìn)行排序 在這種方法中 把單排序碼Ki看成是一個(gè)d元組 其中的每一個(gè)分量 1 j d 也可看成是一個(gè)排序碼 分量有radix種取值 稱(chēng)radix為基數(shù) 例如 排序碼984可以看成是一個(gè)3元組 9 8 4 每一位有0 1 9等10種取值 基數(shù)radix 10 140 119 排序碼 data 可以看成是一個(gè)4元組 d a t a 每一位有 a b z 等26種取值 radix 26 針對(duì)d元組中的每一位分量 把元素序列中的所有元素 按的取值 先 分配 到