數(shù)據(jù)結(jié)構(gòu)第10章ppt課件

1、計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講第第1010章章 排序排序排序的根本概念排序的根本概念插入排序插入排序選擇排序選擇排序交換排序歸并排序交換排序歸并排序基數(shù)排序基數(shù)排序性能比較性能比較主要知識(shí)點(diǎn)主要知識(shí)點(diǎn)計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講10.1 10.1 排序的根本概念排序的根本概念 排序是對(duì)數(shù)據(jù)元素序列建立某種有序陳列的過(guò)程排序是對(duì)數(shù)據(jù)元素序列建立某種有序陳列的過(guò)程, ,是把一個(gè)數(shù)是把一個(gè)數(shù)據(jù)元素序列整理成按關(guān)鍵字遞增或遞減陳列的過(guò)程。據(jù)元素序列整理成按關(guān)鍵字遞增或遞減陳列的過(guò)程。關(guān)鍵字是要排序的數(shù)據(jù)元素集合中的一個(gè)域，排序是以關(guān)鍵字關(guān)鍵字是要排序的數(shù)據(jù)元素集合中的一個(gè)域，

2、排序是以關(guān)鍵字為基準(zhǔn)進(jìn)展的。為基準(zhǔn)進(jìn)展的。主關(guān)鍵字主關(guān)鍵字: :數(shù)據(jù)元素值不同時(shí)該關(guān)鍵字的值也一定不同，是可數(shù)據(jù)元素值不同時(shí)該關(guān)鍵字的值也一定不同，是可以獨(dú)一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字以獨(dú)一區(qū)分各個(gè)不同數(shù)據(jù)元素的關(guān)鍵字; ;不滿足主關(guān)鍵字定義不滿足主關(guān)鍵字定義的關(guān)鍵字稱為次關(guān)鍵字。的關(guān)鍵字稱為次關(guān)鍵字。內(nèi)部排序是把待排數(shù)據(jù)元素全部調(diào)入內(nèi)存中進(jìn)展的排序。內(nèi)部排序是把待排數(shù)據(jù)元素全部調(diào)入內(nèi)存中進(jìn)展的排序。外部排序是因數(shù)量太大，把數(shù)據(jù)元素分批導(dǎo)入內(nèi)存，排好序后外部排序是因數(shù)量太大，把數(shù)據(jù)元素分批導(dǎo)入內(nèi)存，排好序后再分批導(dǎo)出到磁盤和磁帶外存介質(zhì)上的排序方法。再分批導(dǎo)出到磁盤和磁帶外存介質(zhì)上的排序方法

3、。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講比較排序算法優(yōu)劣的規(guī)范比較排序算法優(yōu)劣的規(guī)范: : (1)(1)時(shí)間復(fù)雜度時(shí)間復(fù)雜度: :它主要是分析記錄關(guān)鍵字的比較次數(shù)和記錄的它主要是分析記錄關(guān)鍵字的比較次數(shù)和記錄的 挪動(dòng)次數(shù)挪動(dòng)次數(shù)(2)(2)空間復(fù)雜度空間復(fù)雜度 : :算法中運(yùn)用的內(nèi)存輔助空間的多少算法中運(yùn)用的內(nèi)存輔助空間的多少 (3)(3)穩(wěn)定性穩(wěn)定性: :假設(shè)兩個(gè)記錄假設(shè)兩個(gè)記錄A A和和B B的關(guān)鍵字值相等，但排序后的關(guān)鍵字值相等，但排序后A A、B B的的 先后次序堅(jiān)持不變，那么稱這種排序算法是先后次序堅(jiān)持不變，那么稱這種排序算法是穩(wěn)定的穩(wěn)定的計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主

4、講10.210.2插入排序插入排序 插入排序的根本思想是：每步將一個(gè)待排序的數(shù)據(jù)元素，插入排序的根本思想是：每步將一個(gè)待排序的數(shù)據(jù)元素，按其關(guān)鍵碼大小，插入到前面曾經(jīng)排好序的一組數(shù)據(jù)元素的適按其關(guān)鍵碼大小，插入到前面曾經(jīng)排好序的一組數(shù)據(jù)元素的適當(dāng)位置上，直到數(shù)據(jù)元素全部插入為止。當(dāng)位置上，直到數(shù)據(jù)元素全部插入為止。1.1.直接插入排序直接插入排序常用的插入排序有直接插入排序和希爾排序兩種。常用的插入排序有直接插入排序和希爾排序兩種。 其根本思想是：其根本思想是： 順序地把待排序的數(shù)據(jù)元素按其關(guān)鍵字值的大小插入到順序地把待排序的數(shù)據(jù)元素按其關(guān)鍵字值的大小插入到已排序數(shù)據(jù)元素子集合的適當(dāng)位置。已排

5、序數(shù)據(jù)元素子集合的適當(dāng)位置。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講算法如下：算法如下：void InsertSort (DataType a, int n)/用直接插入法對(duì)用直接插入法對(duì)a0-an-1排序排序 int i, j; DataType temp; for(i=0; i -1 & temp.key = aj.key) aj+1 = aj; j-; aj+1 = temp; 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講算法分析算法分析: :(1)時(shí)間效率：時(shí)間效率： 由于在最壞情況下，一切元素的比較次數(shù)總由于在最壞情況下，一切元素的比較次數(shù)總和為和為01n-1)O(n2)。其

6、他情況下也要。其他情況下也要思索挪動(dòng)元素的次數(shù)。思索挪動(dòng)元素的次數(shù)。 故時(shí)間復(fù)雜度為故時(shí)間復(fù)雜度為O(n2) (2)空間效率：僅占用空間效率：僅占用1個(gè)附加內(nèi)存單元個(gè)附加內(nèi)存單元O(1)(3)算法的穩(wěn)定性：穩(wěn)定算法的穩(wěn)定性：穩(wěn)定計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講64789624564896245764624576489245676489567246489589624初始關(guān)鍵字序列初始關(guān)鍵字序列:第一次排序第一次排序:第二次排序第二次排序:第三次排序第三次排序:第四次排序第四次排序:第五次排序第五次排序:7直接插入排序過(guò)程直接插入排序過(guò)程 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講(1)

7、(1)根本思想：把整個(gè)待排序的數(shù)據(jù)元素分成假設(shè)干個(gè)小組，對(duì)根本思想：把整個(gè)待排序的數(shù)據(jù)元素分成假設(shè)干個(gè)小組，對(duì)同一小組內(nèi)的數(shù)據(jù)元素用直接插入法排序；小組的個(gè)數(shù)逐次減少，同一小組內(nèi)的數(shù)據(jù)元素用直接插入法排序；小組的個(gè)數(shù)逐次減少，當(dāng)完成了一切數(shù)據(jù)元素都在一個(gè)組內(nèi)的排序后排序過(guò)程終了。當(dāng)完成了一切數(shù)據(jù)元素都在一個(gè)組內(nèi)的排序后排序過(guò)程終了。 (2)(2)技巧：小組的構(gòu)成不是簡(jiǎn)單地技巧：小組的構(gòu)成不是簡(jiǎn)單地“逐段分割，而是將相隔某個(gè)逐段分割，而是將相隔某個(gè)增量增量dkdk的記錄組成一個(gè)小組的記錄組成一個(gè)小組, ,讓增量讓增量dkdk逐趟縮短例如依次取逐趟縮短例如依次取5,3,15,3,1，直到，直到dk

8、dk1 1為止。為止。(3)(3)優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列假設(shè)根本有優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能很快前移，且序列假設(shè)根本有序時(shí)，再用直接插入排序處置，時(shí)間效率會(huì)高很多。序時(shí)，再用直接插入排序處置，時(shí)間效率會(huì)高很多。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講算法如下：算法如下：void ShellSort (DataType a, int n, int d, int numOfD)/用希爾排序法對(duì)元素用希爾排序法對(duì)元素a0-an-1排序，排序，d0-dnumOfD-1為為希爾增量值希爾增量值 int i, j, k, m, span; DataType temp; for(m =

9、 0; m numOfD; m+) /共共numOfD次循環(huán)次循環(huán) span = dm; /取本次的增量值取本次的增量值 for(k = 0; k span; k+) /共共span個(gè)小組個(gè)小組 /組內(nèi)是直接插入排序，區(qū)別是每次不是增組內(nèi)是直接插入排序，區(qū)別是每次不是增1而是增而是增span for(i = k; i -1 & temp.key = aj.key) aj+span = aj; j = j-span; aj+span = temp; 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講653425871238564614779223563414771223654625879238結(jié)

10、果序列結(jié)果序列d=6563414771223654625879238561214653423774625879238結(jié)果序列結(jié)果序列d=3561214653423774625879238121423253438465665778792結(jié)果序列結(jié)果序列d=1(a)(b)(c)希爾排序的排序過(guò)程希爾排序的排序過(guò)程計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講10.3 10.3 選擇排序選擇排序 根本思想是：每次從待排序的數(shù)據(jù)元素集合中選取根本思想是：每次從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最小或最大的數(shù)據(jù)元素放到數(shù)據(jù)元素集關(guān)鍵字最小或最大的數(shù)據(jù)元素放到數(shù)據(jù)元素集合的最前或最后，數(shù)據(jù)元素集合不斷減少，當(dāng)合

11、的最前或最后，數(shù)據(jù)元素集合不斷減少，當(dāng)數(shù)據(jù)元素集合為空時(shí)選擇排序終了。數(shù)據(jù)元素集合為空時(shí)選擇排序終了。常用的選擇排序算法：常用的選擇排序算法： 1直接選擇排序直接選擇排序 2堆排序堆排序計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講 根本思想是：從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最小根本思想是：從待排序的數(shù)據(jù)元素集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第一個(gè)數(shù)據(jù)元素交的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第一個(gè)數(shù)據(jù)元素交換位置；然后從不包括第一個(gè)位置上數(shù)據(jù)元素的集合中選取關(guān)換位置；然后從不包括第一個(gè)位置上數(shù)據(jù)元素的集合中選取關(guān)鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第二個(gè)數(shù)

12、鍵字最小的數(shù)據(jù)元素并將它與原始數(shù)據(jù)元素集合中的第二個(gè)數(shù)據(jù)元素交換位置；如此反復(fù)，直到數(shù)據(jù)元素集合中只剩一個(gè)數(shù)據(jù)元素交換位置；如此反復(fù)，直到數(shù)據(jù)元素集合中只剩一個(gè)數(shù)據(jù)元素為止。據(jù)元素為止。 優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單缺陷：每趟只能確定一個(gè)元素，表長(zhǎng)為缺陷：每趟只能確定一個(gè)元素，表長(zhǎng)為n n時(shí)需求時(shí)需求n-1n-1趟趟計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講算法如下：算法如下：void SelectSort(DataType a, int n) int i, j, small; DataType temp; for(i = 0; i n-1; i+) small = i; /設(shè)第設(shè)第i個(gè)數(shù)據(jù)元

13、素關(guān)鍵字個(gè)數(shù)據(jù)元素關(guān)鍵字最小最小 for(j = i+1; j n; j+)/尋覓關(guān)鍵字最小尋覓關(guān)鍵字最小的數(shù)據(jù)元素的數(shù)據(jù)元素 if(aj.key asmall.key) small=j; /記住最小元素的記住最小元素的下標(biāo)下標(biāo) if(small != i)/當(dāng)最小元素的下標(biāo)不為當(dāng)最小元素的下標(biāo)不為i時(shí)交換時(shí)交換位置位置 temp = ai; ai = asmall; asmall = temp; 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講645789624564789624567896424567896424567246489567246489初始關(guān)鍵字序列初始關(guān)鍵字序列:第一次排序結(jié)果第一

14、次排序結(jié)果:第二次排序結(jié)果第二次排序結(jié)果:第三次排序結(jié)果第三次排序結(jié)果:第四次排序結(jié)果第四次排序結(jié)果:第五次排序結(jié)果第五次排序結(jié)果:567246489最后結(jié)果序列最后結(jié)果序列:直接選擇排序的排序過(guò)程直接選擇排序的排序過(guò)程 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講算法分析算法分析時(shí)間效率：時(shí)間效率： O(n2) O(n2)雖挪動(dòng)次數(shù)較少，但比較次數(shù)雖挪動(dòng)次數(shù)較少，但比較次數(shù)仍多。仍多。 空間效率：空間效率：O(1)O(1)沒(méi)有附加單元僅用到?jīng)]有附加單元僅用到1 1個(gè)個(gè)temp)temp)算法的穩(wěn)定性：不穩(wěn)定算法的穩(wěn)定性：不穩(wěn)定計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講2.2.堆排序堆排序 根本

15、思想根本思想: :把待排序的數(shù)據(jù)元素集合構(gòu)成一個(gè)完全二叉樹(shù)構(gòu)把待排序的數(shù)據(jù)元素集合構(gòu)成一個(gè)完全二叉樹(shù)構(gòu)造，那么每次選擇出一個(gè)最大或最小的數(shù)據(jù)元素只需比較造，那么每次選擇出一個(gè)最大或最小的數(shù)據(jù)元素只需比較完全二叉樹(shù)的高度次，即完全二叉樹(shù)的高度次，即log2nlog2n次，那么排序算法的時(shí)間復(fù)雜度次，那么排序算法的時(shí)間復(fù)雜度就是就是O(nlog2n)O(nlog2n)。一、堆的定義一、堆的定義堆分為最大堆和最小堆兩種。定義如下：堆分為最大堆和最小堆兩種。定義如下：設(shè)數(shù)組設(shè)數(shù)組a中存放了中存放了n個(gè)數(shù)據(jù)元素，數(shù)組下標(biāo)從個(gè)數(shù)據(jù)元素，數(shù)組下標(biāo)從0開(kāi)場(chǎng)，假設(shè)當(dāng)數(shù)開(kāi)場(chǎng)，假設(shè)當(dāng)數(shù)組下標(biāo)組下標(biāo)2i+1n時(shí)有時(shí)有

16、:ai.keya2i+1.key(ai.keya2i+1.key)；假；假設(shè) 當(dāng) 數(shù) 組 下 標(biāo)設(shè) 當(dāng) 數(shù) 組 下 標(biāo) 2 i + 2 n 時(shí) 有時(shí) 有 : a i . k e y a 2 i + 2 . k e y (ai.keya2i+2.key)，那么這樣的數(shù)據(jù)構(gòu)造稱為最大堆，那么這樣的數(shù)據(jù)構(gòu)造稱為最大堆(最小堆最小堆)。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講1050325769408888764050109325(a)(b)(a)完全二叉樹(shù)完全二叉樹(shù) (b)最大堆最大堆 性質(zhì)：性質(zhì)：1 1最大堆的根結(jié)點(diǎn)是堆中值最大的數(shù)據(jù)元素，最小堆的根最大堆的根結(jié)點(diǎn)是堆中值最大的數(shù)據(jù)元素，最小堆的

17、根結(jié)點(diǎn)是堆中值最小的數(shù)據(jù)元素，我們稱堆的根結(jié)點(diǎn)元素為堆頂結(jié)點(diǎn)是堆中值最小的數(shù)據(jù)元素，我們稱堆的根結(jié)點(diǎn)元素為堆頂元素。元素。2 2對(duì)于最大堆，從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的途徑上，數(shù)據(jù)元對(duì)于最大堆，從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的途徑上，數(shù)據(jù)元素組成的序列都是遞減有序的；對(duì)于最小堆，從根結(jié)點(diǎn)到每個(gè)素組成的序列都是遞減有序的；對(duì)于最小堆，從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)的途徑上，數(shù)據(jù)元素組成的序列都是遞增有序的。葉結(jié)點(diǎn)的途徑上，數(shù)據(jù)元素組成的序列都是遞增有序的。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講二、二、 創(chuàng)建堆創(chuàng)建堆 創(chuàng)建最大堆過(guò)程中要多次調(diào)用函數(shù)：調(diào)整完全二叉樹(shù)中某創(chuàng)建最大堆過(guò)程中要多次調(diào)用函數(shù)：調(diào)整完全二叉樹(shù)中某個(gè)

18、非葉結(jié)點(diǎn)個(gè)非葉結(jié)點(diǎn)aiaii = (n-1)/2i = (n-1)/2使之滿足最大堆定義，前提條使之滿足最大堆定義，前提條件是該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)件是該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)a2i+1a2i+1和右孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)a2i+2a2i+2都已是都已是最大堆。函數(shù)設(shè)計(jì)如下：最大堆。函數(shù)設(shè)計(jì)如下： 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講void CreatHeap (DataType a, int n, int h) int i, j, flag; DataType temp; i = h;/ i為要建堆的二叉樹(shù)根結(jié)點(diǎn)下標(biāo)為要建堆的二叉樹(shù)根結(jié)點(diǎn)下標(biāo) j = 2*i+1;/ j為為i的左孩子結(jié)點(diǎn)的下標(biāo)的

19、左孩子結(jié)點(diǎn)的下標(biāo) temp = ai; flag = 0; while(j n & flag != 1) /尋覓左右孩子結(jié)點(diǎn)中的較大者尋覓左右孩子結(jié)點(diǎn)中的較大者,j為其下標(biāo)為其下標(biāo) if(j n-1 & aj.key aj.key)/ai.keyaj.key flag=1;/標(biāo)志終了挑選條件標(biāo)志終了挑選條件 else/否那么把否那么把a(bǔ)j上移上移 ai = aj; i = j; j = 2*i+1; ai = temp;/把最初的把最初的ai賦予最后的賦予最后的aj計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講初始化創(chuàng)建最大堆算法如下：初始化創(chuàng)建最大堆算法如下：void InitC

20、reatHeap(DataType a, int n) int i; for(i = (n-1)/2; i = 0; i-) CreatHeap(a, n, i);堆排序的根本思想是：循環(huán)執(zhí)行如下過(guò)程直到數(shù)組為空：堆排序的根本思想是：循環(huán)執(zhí)行如下過(guò)程直到數(shù)組為空：1把堆把堆頂頂a0元素為最大元素和當(dāng)前最大堆的最后一個(gè)元素交換；元素為最大元素和當(dāng)前最大堆的最后一個(gè)元素交換；2最大最大堆元素個(gè)數(shù)減堆元素個(gè)數(shù)減1；3由于第由于第1步后根結(jié)點(diǎn)不再滿足最大堆的定義，步后根結(jié)點(diǎn)不再滿足最大堆的定義，所以調(diào)整根結(jié)點(diǎn)使之滿足最大堆的定義。所以調(diào)整根結(jié)點(diǎn)使之滿足最大堆的定義。三、堆排序算法三、堆排序算法計(jì)算機(jī)學(xué)

21、院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講1050325769408810503257694088數(shù)組數(shù)組1050328876940510503288769405數(shù)組數(shù)組1050408876932510504088769325數(shù)組數(shù)組1088405076932510884050769325數(shù)組數(shù)組8876405010932588764050109325數(shù)組數(shù)組(a)初始形狀初始形狀 (b)調(diào)整結(jié)點(diǎn)調(diào)整結(jié)點(diǎn)5后后 (c)調(diào)整結(jié)點(diǎn)調(diào)整結(jié)點(diǎn)32后后 (d)調(diào)整結(jié)點(diǎn)調(diào)整結(jié)點(diǎn)50后后 (e)調(diào)整結(jié)點(diǎn)調(diào)整結(jié)點(diǎn)10后后 完全二叉樹(shù)調(diào)整為最大堆的過(guò)程完全二叉樹(shù)調(diào)整為最大堆的過(guò)程 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華

22、主講堆排序算法如下：堆排序算法如下：void HeapSort(DataType a, int n) int i; DataType temp; InitCreatHeap(a, n);/初始化創(chuàng)建最大堆初始化創(chuàng)建最大堆 for(i = n-1; i 0; i-)/當(dāng)前最大堆個(gè)數(shù)每次遞減當(dāng)前最大堆個(gè)數(shù)每次遞減1 /把堆頂把堆頂a0元素和當(dāng)前最大堆的最后一個(gè)元素交換元素和當(dāng)前最大堆的最后一個(gè)元素交換 temp = a0; a0 = ai; ai = temp; CreatHeap(a, i, 0);/調(diào)整根結(jié)點(diǎn)滿足最大堆調(diào)整根結(jié)點(diǎn)滿足最大堆 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講887640

23、5010932588764050109325(a)初始最大堆初始最大堆 76504051093276504051093288503240510950324051097688(b)交換頂點(diǎn)交換頂點(diǎn)88后后 (c)交換頂點(diǎn)交換頂點(diǎn)76后后 4032951040329510507688(d)交換頂點(diǎn)交換頂點(diǎn)50后后 3210953210954050768832109105932405076889595103240507688(g)交換頂點(diǎn)交換頂點(diǎn)10后后 559103240507688(h)交換頂點(diǎn)交換頂點(diǎn)9后后 (f)交換頂點(diǎn)交換頂點(diǎn)32后后 (e)交換頂點(diǎn)交換頂點(diǎn)40后后 堆排序算法的排序過(guò)程堆

24、排序算法的排序過(guò)程 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講算法分析：算法分析：時(shí)間效率：時(shí)間效率：O(nlog2n)。由于整個(gè)排序過(guò)程中需求調(diào)用。由于整個(gè)排序過(guò)程中需求調(diào)用n-1次次堆頂點(diǎn)的調(diào)整，而每次堆排序算法本身耗時(shí)為堆頂點(diǎn)的調(diào)整，而每次堆排序算法本身耗時(shí)為log2n；空間效率：空間效率：O(1)。僅在第二個(gè)。僅在第二個(gè)for循環(huán)中交換記錄時(shí)用到一循環(huán)中交換記錄時(shí)用到一個(gè)暫時(shí)變量個(gè)暫時(shí)變量temp。穩(wěn)定性：穩(wěn)定性： 不穩(wěn)定。不穩(wěn)定。優(yōu)點(diǎn)：對(duì)小文件效果不明顯，但對(duì)大文件有效。優(yōu)點(diǎn)：對(duì)小文件效果不明顯，但對(duì)大文件有效。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講10.4 10.4 交換排序交

25、換排序 交換排序的根本思想是：利用交換數(shù)據(jù)元素的位交換排序的根本思想是：利用交換數(shù)據(jù)元素的位置進(jìn)展排序的方法。置進(jìn)展排序的方法。交換排序的主要算法有：交換排序的主要算法有：1)冒泡排序冒泡排序2)快速排序快速排序計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講1.1.冒泡排序冒泡排序 根本思想：每趟不斷將數(shù)據(jù)元素兩兩比較，并按根本思想：每趟不斷將數(shù)據(jù)元素兩兩比較，并按“前小后大前小后大或或“前大后小規(guī)那么交換。前大后小規(guī)那么交換。優(yōu)點(diǎn)：每趟終了時(shí)，不僅能擠出一個(gè)最大值到最后面位置，優(yōu)點(diǎn)：每趟終了時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒(méi)有交換發(fā)還能同時(shí)部分理順其他元素

26、；一旦下趟沒(méi)有交換發(fā)生，還可以提早終了排序。生，還可以提早終了排序。計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講算法中心語(yǔ)句如下：算法中心語(yǔ)句如下：for(i = 1;i n & flag = 1; i+)for(i = 1;i n & flag = 1; i+) flag = 0; flag = 0; for(j = 0;j n - i; j+) for(j = 0;j n - i; j+) flag = 1; flag = 1; temp = aj; temp = aj; aj = aj+1; aj = aj+1; aj+1 = temp; aj+1 = temp; 計(jì)算機(jī)學(xué)

27、院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講初始關(guān)鍵字序列初始關(guān)鍵字序列:第一次排序結(jié)果第一次排序結(jié)果:第二次排序結(jié)果第二次排序結(jié)果:第三次排序結(jié)果第三次排序結(jié)果:第四次排序結(jié)果第四次排序結(jié)果:第五次排序結(jié)果第五次排序結(jié)果:最后結(jié)果序列最后結(jié)果序列:385192649971665192638491669751926381496697519261384966975191263849669751192638496697151926384966971519263849669715192638496697第六次排序結(jié)果第六次排序結(jié)果:第七次排序結(jié)果第七次排序結(jié)果:冒泡排序算法的排序過(guò)程冒泡排序算法的排序過(guò)程 計(jì)

28、算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講算法分析：算法分析：最好情況：初始陳列曾經(jīng)有序，只執(zhí)行一趟起泡，做最好情況：初始陳列曾經(jīng)有序，只執(zhí)行一趟起泡，做 n-1 次關(guān)鍵碼比較，不挪動(dòng)數(shù)據(jù)元素。次關(guān)鍵碼比較，不挪動(dòng)數(shù)據(jù)元素。最壞情形：初始陳列逆序，算法要執(zhí)行最壞情形：初始陳列逆序，算法要執(zhí)行n-1趟起泡，第趟起泡，第i趟趟(1 i n) 做了做了n- i 次關(guān)鍵碼比較，執(zhí)行了次關(guān)鍵碼比較，執(zhí)行了n-i 次數(shù)據(jù)元素次數(shù)據(jù)元素交換。此時(shí)的比較總次數(shù)和記錄挪動(dòng)次數(shù)為：交換。此時(shí)的比較總次數(shù)和記錄挪動(dòng)次數(shù)為：11111233121nininninnnin)()()()(移移動(dòng)動(dòng)次次數(shù)數(shù)比比較較次次數(shù)數(shù)計(jì)

29、算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講2 .2 .快速排序快速排序 根本思想：從待排序列中任取一個(gè)元素根本思想：從待排序列中任取一個(gè)元素 ( (例如取第一個(gè)例如取第一個(gè)) ) 作為作為中心，一切比它小的元素一概前放，一切比它大的元素一概后中心，一切比它小的元素一概前放，一切比它大的元素一概后放，構(gòu)成左右兩個(gè)子表；然后再對(duì)各子表重新選擇中心元素并放，構(gòu)成左右兩個(gè)子表；然后再對(duì)各子表重新選擇中心元素并依此規(guī)那么調(diào)整，直到每個(gè)子表的元素只剩一個(gè)。此時(shí)便為有依此規(guī)那么調(diào)整，直到每個(gè)子表的元素只剩一個(gè)。此時(shí)便為有序序列了。序序列了。優(yōu)點(diǎn)：由于每趟可以確定不止一個(gè)元素的位置，而且呈指數(shù)添加，優(yōu)點(diǎn)：由于每

30、趟可以確定不止一個(gè)元素的位置，而且呈指數(shù)添加，所以特別快。所以特別快。 因此：因此：時(shí)間效率：時(shí)間效率：O On2) n2) 思索最壞情況思索最壞情況空間效率：空間效率：O O1 1 只在交換時(shí)用到一個(gè)緩沖單元只在交換時(shí)用到一個(gè)緩沖單元穩(wěn)穩(wěn) 定定 性：性： 穩(wěn)定的穩(wěn)定的計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講算法中心語(yǔ)句如下：算法中心語(yǔ)句如下：while(i j & temp.key = aj.key) j-;/while(i j & temp.key = aj.key) j-;/在數(shù)組在數(shù)組的右端掃描的右端掃描if(i j)if(i j) ai = aj; ai = aj;

31、 i+; i+; while(i j & ai.key temp.key) i+;/while(i j & ai.key temp.key) i+;/在數(shù)組在數(shù)組的左端掃描的左端掃描if(i j)if(i j) aj = ai; aj = ai; j-; j-; 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講6055483710908436365548371090849090365548371090843655483710908436554837109084365548371090843655483710908436554837108436554837106084iiiiiiiij

32、jjjjjjjij初始關(guān)鍵字序列初始關(guān)鍵字序列:(1)(2)(3)(4)(5)(6)(7)(8)快速排序算法一次快速排序過(guò)程快速排序算法一次快速排序過(guò)程 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講圖中標(biāo)有下劃?rùn)M線的數(shù)據(jù)元素為本次快速排序選取的規(guī)范圖中標(biāo)有下劃?rùn)M線的數(shù)據(jù)元素為本次快速排序選取的規(guī)范元素。元素。快速排序算法各次快速排序過(guò)程快速排序算法各次快速排序過(guò)程 初始關(guān)鍵字序列初始關(guān)鍵字序列:(1)(2)60554837109084363655483710609010 3637556084(3)10 3648608490最后結(jié)果最后結(jié)果10363748556084903748558490 計(jì)算

33、機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講時(shí)間效率：時(shí)間效率：O(nlog2n) 由于每趟確定的元素呈指數(shù)添加由于每趟確定的元素呈指數(shù)添加空間效率：空間效率：O(log2n)由于遞歸要用堆棧由于遞歸要用堆棧穩(wěn)穩(wěn) 定定 性：性： 不不 穩(wěn)穩(wěn) 定定 由于有騰躍式交換。由于有騰躍式交換。算法分析：算法分析：計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講10.5 10.5 歸并排序歸并排序 歸并排序主要是二路歸并排序歸并排序主要是二路歸并排序,根本思想是：可以把一個(gè)長(zhǎng)根本思想是：可以把一個(gè)長(zhǎng)度為度為n 的無(wú)序序列看成是的無(wú)序序列看成是 n 個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為 1 的有序子序列的有序子序列 ，首先做，首先做兩兩歸

34、并，得到兩兩歸并，得到 n / 2 個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為 2 的有序子序列的有序子序列 ；再做兩兩；再做兩兩歸并，歸并，如此反復(fù)，直到最后得到一個(gè)長(zhǎng)度為，如此反復(fù)，直到最后得到一個(gè)長(zhǎng)度為 n 的有序序列。的有序序列。 一次二路歸并排序算法如下：一次二路歸并排序算法如下：計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講void Merge(DataType a, int n, DataType swap, int k)/k為有序子數(shù)組的長(zhǎng)度，一次二路歸并排序后的有序子序列存于數(shù)組為有序子數(shù)組的長(zhǎng)度，一次二路歸并排序后的有序子序列存于數(shù)組swap中中 int m = 0, u1,l2,i,j,u2; int

35、 l1 = 0;/第一個(gè)有序子數(shù)組下界為第一個(gè)有序子數(shù)組下界為0 while(l1+k = n-1) l2 = l1 + k; /計(jì)算第二個(gè)有序子數(shù)組下界計(jì)算第二個(gè)有序子數(shù)組下界 u1 = l2 - 1;/計(jì)算第一個(gè)有序子數(shù)組上界計(jì)算第一個(gè)有序子數(shù)組上界 u2 = (l2+k-1 = n-1)? l2+k-1: n-1; /計(jì)算第二個(gè)有序子數(shù)組上界計(jì)算第二個(gè)有序子數(shù)組上界 /兩個(gè)有序子數(shù)組合并兩個(gè)有序子數(shù)組合并 for(i = l1, j = l2; i = u1 & j = u2; m+) if(ai.key = aj.key) swapm = ai; i+; else swapm=

36、aj; j+; /子數(shù)組子數(shù)組2已歸并完，將子數(shù)組已歸并完，將子數(shù)組1中剩余的元素存放到數(shù)組中剩余的元素存放到數(shù)組swap中中while(i = u1) swapm = ai; m+; i+;計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講 /子數(shù)組子數(shù)組1已歸并完，將子數(shù)組已歸并完，將子數(shù)組2中剩余的元素存放到數(shù)組中剩余的元素存放到數(shù)組swap中中 while(j = u2) swapm = aj; m+; j+; l1 = u2 + 1; /將原始數(shù)組中只夠一組的數(shù)據(jù)元素順序存放到數(shù)組將原始數(shù)組中只夠一組的數(shù)據(jù)元素順序存放到數(shù)組swap中中for(i = l1; i n; i+, m+) swa

37、pm = ai;計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講由于在遞歸的歸并排序算法中，遞歸調(diào)用函數(shù)由于在遞歸的歸并排序算法中，遞歸調(diào)用函數(shù)Merge( )約為約為log2n 次，而每次歸并要執(zhí)行比較約為次，而每次歸并要執(zhí)行比較約為n次，所以算法次，所以算法總的時(shí)間復(fù)雜度為總的時(shí)間復(fù)雜度為O(nlog2n)?？臻g效率：空間效率： O(n) 由于需求一個(gè)與原始序列同樣大小的輔助序列。這是此算由于需求一個(gè)與原始序列同樣大小的輔助序列。這是此算法的缺陷。法的缺陷。穩(wěn)定性：穩(wěn)定穩(wěn)定性：穩(wěn)定計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講10.6 10.6 基數(shù)排序基數(shù)排序 基數(shù)排序也稱作桶排序，是一種當(dāng)關(guān)鍵字

38、為整數(shù)類型時(shí)非基數(shù)排序也稱作桶排序，是一種當(dāng)關(guān)鍵字為整數(shù)類型時(shí)非常高效的排序方法。常高效的排序方法。 其根本思想是：其根本思想是： 設(shè)待排序的數(shù)據(jù)元素關(guān)鍵字是設(shè)待排序的數(shù)據(jù)元素關(guān)鍵字是m m位位d d進(jìn)制整數(shù)缺乏進(jìn)制整數(shù)缺乏m m位的關(guān)位的關(guān)鍵字在高位補(bǔ)鍵字在高位補(bǔ)0 0，設(shè)置，設(shè)置d d個(gè)桶，令其編號(hào)分別為個(gè)桶，令其編號(hào)分別為0,1,2,d-10,1,2,d-1。首先按關(guān)鍵字最低位的數(shù)值依次把各數(shù)據(jù)元素放到相應(yīng)的桶中，首先按關(guān)鍵字最低位的數(shù)值依次把各數(shù)據(jù)元素放到相應(yīng)的桶中，然后按照桶號(hào)從小到大和進(jìn)入桶中數(shù)據(jù)元素的先后次序搜集分然后按照桶號(hào)從小到大和進(jìn)入桶中數(shù)據(jù)元素的先后次序搜集分配在各桶中的

39、數(shù)據(jù)元素，這樣就構(gòu)成了數(shù)據(jù)元素集合的一個(gè)新配在各桶中的數(shù)據(jù)元素，這樣就構(gòu)成了數(shù)據(jù)元素集合的一個(gè)新的陳列，我們稱這樣的一次排序過(guò)程為一次基數(shù)排序；的陳列，我們稱這樣的一次排序過(guò)程為一次基數(shù)排序；計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講 再對(duì)一次基數(shù)排序得到的數(shù)據(jù)元素序列按關(guān)鍵字次低位再對(duì)一次基數(shù)排序得到的數(shù)據(jù)元素序列按關(guān)鍵字次低位的數(shù)值依次把各數(shù)據(jù)元素放到相應(yīng)的桶中，然后按照桶號(hào)的數(shù)值依次把各數(shù)據(jù)元素放到相應(yīng)的桶中，然后按照桶號(hào)從小到大和進(jìn)入桶中數(shù)據(jù)元素的先后次序搜集分配在各桶從小到大和進(jìn)入桶中數(shù)據(jù)元素的先后次序搜集分配在各桶中的數(shù)據(jù)元素；這樣的過(guò)程反復(fù)進(jìn)展，當(dāng)完成了第中的數(shù)據(jù)元素；這樣的過(guò)程

40、反復(fù)進(jìn)展，當(dāng)完成了第m次基數(shù)次基數(shù)排序后，就得到了排好序的數(shù)據(jù)元素序列。排序后，就得到了排好序的數(shù)據(jù)元素序列。數(shù)據(jù)元素的關(guān)鍵字序列為數(shù)據(jù)元素的關(guān)鍵字序列為710,342,045,686,006,841,429,134,068,264排序過(guò)程如下排序過(guò)程如下計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講8411342231342644045568600667068871004299710841342134264045686006068429搜集后的新序列搜集后的新序列:放置放置71014292134384134204545264068676868006090067104291348413420452

41、64068686搜集后的新序列搜集后的新序列:放置放置1341264234234294568667107841800604506809006045068134264342429686710841搜集后的新序列搜集后的新序列:放置放置(a)初始形狀初始形狀 (b)第一次基數(shù)排序第一次基數(shù)排序 (c)(c)第二次基數(shù)排序第二次基數(shù)排序 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講 基數(shù)排序算法進(jìn)出桶中的數(shù)據(jù)元素序列滿足先進(jìn)先出的原基數(shù)排序算法進(jìn)出桶中的數(shù)據(jù)元素序列滿足先進(jìn)先出的原那么，桶實(shí)踐就是隊(duì)列。實(shí)現(xiàn)基數(shù)排序算法時(shí)，有基于順序隊(duì)那么，桶實(shí)踐就是隊(duì)列。實(shí)現(xiàn)基數(shù)排序算法時(shí)，有基于順序隊(duì)列和基于鏈?zhǔn)疥?duì)

42、列兩種不同的實(shí)現(xiàn)方法。列和基于鏈?zhǔn)疥?duì)列兩種不同的實(shí)現(xiàn)方法。在基于鏈?zhǔn)疥?duì)列的基數(shù)排序算法中，可以把在基于鏈?zhǔn)疥?duì)列的基數(shù)排序算法中，可以把d個(gè)隊(duì)列設(shè)計(jì)成一個(gè)隊(duì)列設(shè)計(jì)成一個(gè)隊(duì)列數(shù)組設(shè)隊(duì)列數(shù)組名為個(gè)隊(duì)列數(shù)組設(shè)隊(duì)列數(shù)組名為tub，隊(duì)列數(shù)組的每個(gè)元素中，隊(duì)列數(shù)組的每個(gè)元素中包括兩個(gè)域：包括兩個(gè)域： front域和域和rear域。域。front域用于指示隊(duì)頭，域用于指示隊(duì)頭，rear域用于指示隊(duì)尾。當(dāng)?shù)谟蛴糜谥甘娟?duì)尾。當(dāng)?shù)趇i=0,1,2,d-1個(gè)隊(duì)列中有數(shù)據(jù)元素個(gè)隊(duì)列中有數(shù)據(jù)元素要放入時(shí)，就在隊(duì)列數(shù)組的相應(yīng)元素要放入時(shí)，就在隊(duì)列數(shù)組的相應(yīng)元素tubi中的隊(duì)尾位置插入中的隊(duì)尾位置插入一個(gè)結(jié)點(diǎn)?；阪?zhǔn)疥?duì)列基

43、數(shù)排序算法的存儲(chǔ)構(gòu)造表示圖如以一個(gè)結(jié)點(diǎn)?；阪?zhǔn)疥?duì)列基數(shù)排序算法的存儲(chǔ)構(gòu)造表示圖如以下圖所示。下圖所示。 計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講.rearfrontdatanext 012d-1. .tub 一個(gè)十進(jìn)制關(guān)鍵字一個(gè)十進(jìn)制關(guān)鍵字K的第的第i位數(shù)值位數(shù)值Ki的計(jì)算公式為：的計(jì)算公式為：),.,2 , 1()int(10)int(10101miKiiKKi計(jì)算機(jī)學(xué)院計(jì)算機(jī)學(xué)院 蔡之華主講蔡之華主講基于鏈?zhǔn)疥?duì)列的基數(shù)排序算法如下：基于鏈?zhǔn)疥?duì)列的基數(shù)排序算法如下：#include LinQueue.h#include LinQueue.hvoid RadixSort(DataType a, int n, int m, int d)void RadixSort(DataType a, int n, int m, int d)/對(duì)數(shù)據(jù)元素對(duì)數(shù)據(jù)元素a0-an-1a0-an-