數(shù)據(jù)結(jié)構(gòu) 使用C語(yǔ)言版 朱戰(zhàn)立叢書版本 排序幻燈片

1、第十章排序，排序的基本概念插入排序選擇排序交換排序合并排序基數(shù)排序性能比較，主要知識(shí)點(diǎn)，1，10.1排序的基本概念排序是建立數(shù)據(jù)元素序列的某種有序排列，并根據(jù)關(guān)鍵字將數(shù)據(jù)元素序列排序?yàn)檫f增(或遞減)排列的過(guò)程。關(guān)鍵字是要排序的數(shù)據(jù)元素集合中的字段，排序基于關(guān)鍵字。當(dāng)主關(guān)鍵字：的數(shù)據(jù)元素值不同時(shí)，關(guān)鍵字的值必須不同，這是一個(gè)可以唯一區(qū)分不同數(shù)據(jù)元素的關(guān)鍵字；不符合主要關(guān)鍵字定義的關(guān)鍵字稱為次要關(guān)鍵字。內(nèi)部排序是指通過(guò)將所有要排列的數(shù)據(jù)元素轉(zhuǎn)移到內(nèi)存中來(lái)進(jìn)行排序。外部排序是一種排序方法，在這種方法中，數(shù)據(jù)元素分批導(dǎo)入內(nèi)存，然后在排序后分批導(dǎo)出到磁盤和磁帶外部存儲(chǔ)介質(zhì)。比較排序算法的優(yōu)點(diǎn)和缺點(diǎn)的標(biāo)準(zhǔn)

2、3360 (1)時(shí)間復(fù)雜度：它主要分析記錄關(guān)鍵字的比較時(shí)間和記錄的移動(dòng)時(shí)間(2)空間復(fù)雜度3360算法中使用了多少輔助存儲(chǔ)空間(3)穩(wěn)定性3360如果兩個(gè)記錄A和B的關(guān)鍵字值相等，但是排序后A和B的順序保持不變， 那么該排序算法被認(rèn)為是穩(wěn)定的。該算法的空間復(fù)雜度是：這是執(zhí)行該算法所需的存儲(chǔ)器空間和數(shù)據(jù)元素的數(shù)量n，3，10.2之間的函數(shù)關(guān)系。 插入排序的基本思想是將要排序的數(shù)據(jù)元素插入到一組數(shù)據(jù)元素的適當(dāng)位置，這些數(shù)據(jù)元素在每一步都根據(jù)其鍵的大小進(jìn)行排序，直到所有的數(shù)據(jù)元素都被插入。1。直接插入排序，常用的插入排序有直接插入排序和希爾排序兩種。基本思想是根據(jù)鍵值的大小，將要排序的數(shù)據(jù)元素順序插

3、入到排序后的數(shù)據(jù)元素子集的適當(dāng)位置。算法如下：void insertshort(數(shù)據(jù)類型a ，int n)/通過(guò)直接插入對(duì)a 0-a n-1排序int i，j；數(shù)據(jù)類型臨時(shí)。對(duì)于(I=0；I -1)，5，算法分析：(1)空間效率：僅占用幾個(gè)臨時(shí)存儲(chǔ)單元O(1) (2)算法穩(wěn)定性：穩(wěn)定性(3)時(shí)間效率：在最壞的情況下(逆序)，所有元素的比較時(shí)間之和為(1 2n-)平均時(shí)間復(fù)雜度也為O(n2)，但在最好的情況下(正序)，所有元素的比較時(shí)間之和為(1 11)O(n)。分析：元素的順序越接近順序，比較的次數(shù)就越少。時(shí)間復(fù)雜度越接近0(n)。6、直接插入排序過(guò)程，7、2。外殼排序(也稱為簡(jiǎn)化增量排序)，

4、(1)基本思想：將待排序的整個(gè)數(shù)據(jù)元素分成若干組，用直接插入法對(duì)同一組中的數(shù)據(jù)元素進(jìn)行排序；組的數(shù)量逐漸減少，并且當(dāng)所有數(shù)據(jù)元素都在一個(gè)組中排序時(shí)，排序過(guò)程結(jié)束。(2)技巧：組的組成不是簡(jiǎn)單的“按段劃分”，而是由一定增量dk分隔的記錄組成一個(gè)組，增量dk被一個(gè)接一個(gè)地縮短(例如，依次取5、3和1)，直到DK=1。(3)優(yōu)點(diǎn)：每次排序都采用直接插入排序法。當(dāng)數(shù)據(jù)元素n的數(shù)量很小時(shí)，嘗試調(diào)整元素的順序，使其接近順序。這樣，當(dāng)數(shù)據(jù)元素的數(shù)量n是所有元素時(shí)，數(shù)據(jù)元素的序列接近有序。因此，總的時(shí)間效率會(huì)好得多。算法如下：void shell sort(數(shù)據(jù)類型a ，int n，int d ，int nu

5、m FD)/使用hill排序方法對(duì)元素a 0-a n-1進(jìn)行排序，其中d0-dnum FD-1是hill增量值 int DataType temp對(duì)于(m=0；M -1 、9、希爾的排序過(guò)程，以及10、10.3?；舅枷胧菑囊判虻臄?shù)據(jù)元素集中選擇具有最小(或最大)關(guān)鍵字的數(shù)據(jù)元素，并將其放在數(shù)據(jù)元素集中的某個(gè)位置。數(shù)據(jù)元素集不斷縮小。當(dāng)數(shù)據(jù)元素集為空時(shí)，排序完成。常用的選擇性排序算法：(1)直接選擇性排序(2)堆排序，11，1。直接選擇性排序，基本思想是：從待排序的數(shù)據(jù)元素集中選擇關(guān)鍵字最小的數(shù)據(jù)元素，并與原始數(shù)據(jù)元素集中的第一個(gè)數(shù)據(jù)元素交換位置；然后，從不包括第一位置的數(shù)據(jù)元素的集合中選擇

6、具有最小關(guān)鍵字的數(shù)據(jù)元素，并將其與原始數(shù)據(jù)元素集合中的第二數(shù)據(jù)元素交換；重復(fù)此操作，直到數(shù)據(jù)元素集中只剩下一個(gè)數(shù)據(jù)元素。優(yōu)點(diǎn)：簡(jiǎn)單的實(shí)現(xiàn)缺點(diǎn)：每次只能確定一個(gè)元素。當(dāng)表格長(zhǎng)度為n時(shí)，需要n-1遍。算法如下：void selectsort(數(shù)據(jù)類型a ，int n) int i，j，small數(shù)據(jù)類型臨時(shí)。對(duì)于(I=0；I n-1；I) small=I；/讓ith數(shù)據(jù)元素的關(guān)鍵字是(j=i1；j . n ./查找關(guān)鍵字最小的數(shù)據(jù)元素。a小鍵。key)small=j；/記住下標(biāo)if(?。?i) /當(dāng)最小元素的下標(biāo)不是I temp=ai時(shí)交換位置；aI=asmall；asmall=temp；、13、

7、直接選擇排序的排序過(guò)程、14、算法分析的時(shí)間效率：O(n2)有一些動(dòng)作，但仍有許多比較?？臻g效率：O(1)只使用幾個(gè)臨時(shí)變量。算法穩(wěn)定性：不穩(wěn)定，15，2。堆排序。的基本思想是形成待排序數(shù)據(jù)元素的完整二叉樹結(jié)構(gòu)，因此每次選擇最大(或最小)的數(shù)據(jù)元素時(shí)，只需比較完整二叉樹的高度，即log2n倍，因此排序算法的時(shí)間復(fù)雜度為O(nlog2n)。1.堆的定義堆分為最大堆和最小堆。定義如下：讓數(shù)組A存儲(chǔ)N個(gè)數(shù)據(jù)元素，數(shù)組下標(biāo)從0開始。如果數(shù)組下標(biāo)2i 1=0；i -)創(chuàng)建該p(a，n，I)；，堆排序的基本思想是：循環(huán)以下過(guò)程，直到數(shù)組為空：(1)用當(dāng)前最大堆的最后一個(gè)元素交換最上面的一個(gè)0元素(它是最大

8、的元素);(2)堆疊元素的最大數(shù)量減少1；(3)由于在步驟(1)之后根節(jié)點(diǎn)不再滿足最大堆的定義，調(diào)整根節(jié)點(diǎn)以滿足最大堆的定義。3。堆排序算法，20。將完整的二叉樹調(diào)整到最大堆的過(guò)程，21。堆排序算法如下：void堆(數(shù)據(jù)類型a ，int n) int I；數(shù)據(jù)類型臨時(shí)。initcreateap(a，n)；/初始化并創(chuàng)建最大堆(I=n-1；I 0；I-)/當(dāng)前最大堆數(shù)每次遞減1 /將堆頂部的a0元素與當(dāng)前最大堆的最后一個(gè)元素交換為temp=a0；a0=aI；aI=temp；創(chuàng)建映射(a，I，0)。/調(diào)整根節(jié)點(diǎn)以滿足最大堆)，22，堆排序算法的排序過(guò)程，23，算法分析：時(shí)間效率：O(nlog2n)

9、。因?yàn)檎麄€(gè)排序過(guò)程需要調(diào)用堆頂點(diǎn)的調(diào)整n-1次，而每次堆排序算法本身需要log2n；空間效率：0(1)。只使用了幾個(gè)臨時(shí)變量。穩(wěn)定性：不穩(wěn)定。優(yōu)點(diǎn)：對(duì)于小文件效果不明顯，但是對(duì)于大文件效果很好。24、10.4交換排序的基本思想是使用交換數(shù)據(jù)元素的位置進(jìn)行排序的方法。交換排序的主要算法有：1)冒泡排序2)快速排序，25、1。泡泡分類。基本思想是每次成對(duì)比較數(shù)據(jù)元素，并根據(jù)“先小后大”(或“先大后小”)的規(guī)則交換它們。優(yōu)點(diǎn)：每次通過(guò)結(jié)束時(shí)，不僅最大值可以被擠出到最后位置，而且其他元素也可以同時(shí)被部分拉直；一旦下次旅行沒有交換，你也可以提前結(jié)束分揀。26，算法的核心語(yǔ)句如下：flag=1；對(duì)于(I=

10、1；i aj 1。鍵) flag=1；temp=aj；aj=aj 1；aj 1=temp；、27、冒泡排序算法的排序過(guò)程、28、算法分析：最佳情況：初始排列已經(jīng)排序，只執(zhí)行一次冒泡，比較關(guān)鍵代碼n-1次，不移動(dòng)數(shù)據(jù)元素。最差情況：初始排列顛倒，算法需要執(zhí)行n-1個(gè)氣泡，第I個(gè)鍵比較執(zhí)行n-1次，數(shù)據(jù)元素交換執(zhí)行n-1次。此時(shí)，比較和記錄移動(dòng)時(shí)間的總數(shù)為：比較時(shí)間：n(n-1)/2移動(dòng)時(shí)間：3 n(n-1)/2，29，2?？焖倥判颍舅枷耄阂源判蛄兄械娜魏卧?例如，第一個(gè))為中心，所有較小的元素將被提出，所有較大的元素將被放在后面。然后為每個(gè)子表重新選擇中心元素，并根據(jù)此規(guī)則進(jìn)行調(diào)整，直到

11、每個(gè)子表中只剩下一個(gè)元素。此時(shí)，它是一個(gè)有序的序列。優(yōu)點(diǎn)：因?yàn)槊看温眯锌梢源_定不止一個(gè)元素的位置，而且它以指數(shù)級(jí)增長(zhǎng)，所以速度非?？?。因此：時(shí)間效率：0(N2)-考慮最差情況下的空間效率：0(1)-僅使用幾個(gè)臨時(shí)變量穩(wěn)定性：穩(wěn)定，30、算法的核心語(yǔ)句如下：而(i j ，31、快速排序，快速排序過(guò)程，32、標(biāo)記有下劃線的數(shù)據(jù)元素被選擇用于此快速排序，每個(gè)快速排序過(guò)程中，33、時(shí)間效率：0(nlog2n)-因?yàn)樵诿看蝹鬟f中確定的元素以指數(shù)方式增加空間效率：0(log2n)-因?yàn)檫f歸需要堆棧穩(wěn)定性：不穩(wěn)定性-因?yàn)樗惴ǚ治觯?4，10.5合并排序，合并排序主要是雙向合并排序，基本思想是：可以把長(zhǎng)度為n

12、的無(wú)序序列看成長(zhǎng)度為1的n個(gè)有序子序列，先每?jī)蓚€(gè)合并得到長(zhǎng)度為2的n/2個(gè)有序子序列；然后成對(duì)合并，重復(fù)直到最終得到長(zhǎng)度為n的有序序列。一次性雙向合并排序算法如下：35，void merge(數(shù)據(jù)類型a ，int n，數(shù)據(jù)類型swap ，int k)/k為子數(shù)組長(zhǎng)度，一次性雙向合并排序后的子序列存儲(chǔ)在數(shù)組swap int m=0，u1，l2，I，j，U2；int L1=0；/當(dāng)(L1 k=n-1) L2=L1 k；/第二有序子陣列u1的下限u1=L2-1；/第一個(gè)有序子陣列u2的上界=(l2 k-1=n-1)？L2 k-1:n-1；/第二子陣列的上限/兩個(gè)有序子陣列被合并用于(i=l1，j=l

13、2I=u1、36、/子陣列2已完成，子陣列1中的剩余元素存儲(chǔ)在swap中，同時(shí)(I=u1) swapm=aI；m；我；/子陣列1已完成，子陣列2中的剩余元素存儲(chǔ)在swap中，同時(shí)(j=U2) swapm=aj；m；j； L1=U2 1；/在原始數(shù)組中只存儲(chǔ)一組數(shù)據(jù)元素，以便將數(shù)組交換為(i=l1I n；I，m)交換m=aI；，37，雙向合并排序算法分析，時(shí)間效率：O(nlog2n)，空間效率：O(n)，因?yàn)樗枰c原始序列大小相同的輔助序列。這是這個(gè)算法的缺點(diǎn)。穩(wěn)定：穩(wěn)定。這是雙向合并排序算法的一個(gè)重要特征。38，10.6基數(shù)排序，也稱為桶排序，當(dāng)關(guān)鍵字是整數(shù)類型時(shí)，是一種非常有效的排序方法。

14、其基本思想是：將待排序數(shù)據(jù)元素的關(guān)鍵字設(shè)為M位D元整數(shù)(小于M位的關(guān)鍵字在高位用0填充)，并分別用0、1、2、d-1設(shè)置D個(gè)桶。首先，根據(jù)關(guān)鍵字的最低值將每個(gè)數(shù)據(jù)元素依次放入相應(yīng)的桶中，然后根據(jù)桶的大小和數(shù)據(jù)元素進(jìn)入桶的順序收集分布在每個(gè)桶中的數(shù)據(jù)元素，從而形成新的數(shù)據(jù)元素集排列。我們稱這種排序過(guò)程為基數(shù)排序；39、然后根據(jù)關(guān)鍵字的次低數(shù)值將每個(gè)數(shù)據(jù)元素放入相應(yīng)的桶中，然后按照桶號(hào)從小到大和數(shù)據(jù)元素進(jìn)入桶的順序收集分布在每個(gè)桶中的數(shù)據(jù)元素；重復(fù)該過(guò)程，并且在完成第m個(gè)基數(shù)排序之后獲得有序數(shù)據(jù)元素序列。數(shù)據(jù)元素的關(guān)鍵序列是710，342，045，686，006，841，429，134，068，264。排序過(guò)程如下：40、(d)第三基數(shù)排序，41、基數(shù)排序算法滿足先入先出桶中數(shù)據(jù)元素序列的原則。實(shí)現(xiàn)基數(shù)排序算法有兩種不同的方法，基于順序隊(duì)列和鏈?zhǔn)疥?duì)列。在基于鏈?zhǔn)疥?duì)列的基數(shù)排序算法中，d個(gè)隊(duì)列可以被設(shè)計(jì)為一個(gè)隊(duì)列數(shù)組(將隊(duì)列數(shù)組命名為tub)，隊(duì)列數(shù)組的每個(gè)元素包括兩個(gè)字段：前字段和后字段。前面的字段用于指示