計(jì)算機(jī)軟件技術(shù)基礎(chǔ)-welcometonginx!

1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ),教 師：曾曉東電 話：13679007201E_mail: zengxiaodong@263.net,5.2 排序,一、基本概念二、選擇排序三、插入排序四、交換排序五、歸并排序六、各種排序算法的比較,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,一、基本概念,1. 排序設(shè)有含n個(gè)記錄的序列為{ R1,R2,…,Rn }，其相應(yīng)的關(guān)鍵字序列為{ K1,K2,...,Kn }?，F(xiàn)要求確定一種排序p1,p2,...

2、pn, 使其關(guān)鍵字滿足遞增（或遞減）的關(guān)系：Kp1≤Kp2≤???≤Kpn（或Kp1≥Kp2≥ ???≥Kpn）使原序列成為一個(gè)按關(guān)鍵字有序的序列：{ Rp1,Rp2,…Rpn },計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,一、基本概念,2.排序方法的穩(wěn)定性若Ki=Kj(1≤i≤n ,1≤j≤n ,i≠j)，在排序前Ri領(lǐng)先于Rj ，排序后Ri仍領(lǐng)先于Rj ，則稱此排序方法是穩(wěn)定的；反之稱為不穩(wěn)定的。3. 排序的分類若排序

3、時(shí)待排序記錄存放在內(nèi)存中進(jìn)行排序，則稱為內(nèi)部排序；若待排序記錄數(shù)量很大，在內(nèi)存中一次不能容納全部記錄，需要在排序過程中對(duì)外存進(jìn)行訪問，則稱為外部排序。4.基本操作1）對(duì)記錄中關(guān)鍵字大小進(jìn)行比較；2）將記錄從一個(gè)位置移到另一個(gè)位置。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,一、基本概念,5. 排序的時(shí)間開銷: 排序的時(shí)間開銷是衡量算法好壞的最重要的標(biāo)志。排序的時(shí)間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來衡量。算法運(yùn)行時(shí)間

4、代價(jià)的大略估算一般都按平均情況進(jìn)行估算。對(duì)于那些受對(duì)象排序碼序列初始排列及對(duì)象個(gè)數(shù)影響較大的，需要按最好情況和最壞情況進(jìn)行估算。5. 算法執(zhí)行時(shí)所需的附加存儲(chǔ) 評(píng)價(jià)算法好壞的另一標(biāo)準(zhǔn)。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,一、基本概念,7. 待排序的數(shù)據(jù)表使用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)其數(shù)據(jù)類型定義如下：記錄結(jié)點(diǎn)的類型定義：typedef struct{keywordtype key;datatype data;}RE

5、CORDNODE;待排序的數(shù)據(jù)表是RECORDNODE類型的數(shù)組struct RECORDNODE a[MaxSize];,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,二、選擇排序,選擇排序是不斷在待排序序列（無序區(qū)）中按記錄關(guān)鍵字遞增（或遞減）次序選擇記錄，放入有序區(qū)中，逐漸擴(kuò)大有序區(qū)，直到整個(gè)記錄區(qū)為有序區(qū)為止。其基本思想是: 每一趟 (例如第 i 趟, i = 1, 2, …, n-1) 在后面 n-i 個(gè)待排序?qū)ο笾羞x出排序碼最小的對(duì)

6、象, 作為有序?qū)ο笮蛄械牡?i 個(gè)對(duì)象。待到第 n-1 趟作完, 待排序?qū)ο笾皇Ｏ?個(gè), 就不用再選了。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,二、選擇排序,直接選擇排序過程：在當(dāng)前無序序列中選擇一個(gè)關(guān)鍵字最小的記錄，并將它和最前端的記錄交換。重復(fù)上述過程，使記錄區(qū)的前端逐漸形成一個(gè)由小到大的有序區(qū)。2) 基本步驟(1)在一組對(duì)象 a[i]～a[n] 中選擇具有最小關(guān)鍵字的對(duì)象；(2)若它不是這組對(duì)象中的第一個(gè)對(duì)象, 則將它與這

7、組對(duì)象中的第一個(gè)對(duì)象對(duì)調(diào);(3)在這組對(duì)象中剔除這個(gè)具有最小關(guān)鍵字的對(duì)象。在剩下的對(duì)象a[i+1]～a[n]中重復(fù)執(zhí)行第(1)、(2)步, 直到剩余對(duì)象只有一個(gè)為止。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,最小者 08交換21,08,最小者 16交換25,16,最小者 21交換49,21,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,最小者 25*無交換,最小者 25無交換,各趟排序后的結(jié)果,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,1. 直接選擇排序,

8、3）算法void SelectSort(RECORDNODE a[],int n){/*對(duì)記錄數(shù)組a[1:n]進(jìn)行直接選擇排序*/int i,j,small;RECORDNODE swap;for (i=1;ia[j].key) small=j;if (small!=i){/*交換*/swap=a[small]; a[small]=a[i]; a[i]=swap;}}},計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,1

9、. 直接選擇排序,4）算法分析算法由兩層循環(huán)構(gòu)成，外層循環(huán)表示共需進(jìn)行n-1趟排序，內(nèi)層循環(huán)需進(jìn)行n-I次比較，也許會(huì)做一次交換，即記錄移動(dòng)次數(shù)最多為3?？偟臅r(shí)間性能為① 比較次數(shù)：n(n-1)/2② 移動(dòng)次數(shù)：最壞情況下為3(n-1)所以總的時(shí)間復(fù)雜度為：O(n2)空間復(fù)雜度為：O(1) 交換記錄時(shí)用直接選擇排序是一種不穩(wěn)定的排序算法,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,二、選擇排序,2. 堆排序1) 堆設(shè)有序列

10、{ k1,k2,…,kn }，若滿足：,則稱該序列構(gòu)成的完全二叉樹是一個(gè)堆。 例如，有序列：{ 96，83，27，38，11，9 } 構(gòu)成的完全二叉樹如上圖所示,它是一個(gè)堆。 易知堆頂元素為所有元素中的最小值或最大值,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,2）堆排序的過程由兩部分組成：① 將現(xiàn)有的序列構(gòu)成一個(gè)堆② 輸出堆頂元素，重新調(diào)整元素，構(gòu)成新的堆，直到堆空為止。3）堆的構(gòu)造：① 由所給序列生成對(duì)應(yīng)

11、的完全二叉樹；② 設(shè)完全二叉樹a[1..n]中結(jié)點(diǎn)a[k]的左右子樹均為堆，為構(gòu)成以a[k]為根結(jié)點(diǎn)的堆，需進(jìn)行調(diào)整。方法是將a[k]的值與其左右子樹的根結(jié)點(diǎn)進(jìn)行比較，若不滿足堆的條件，則將a[k]與其左右子樹中根結(jié)點(diǎn)大的交換，繼續(xù)進(jìn)行比較，直到所有子樹均滿足堆的定義為止。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,建立初始的最大堆,,,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,最大堆的向下調(diào)整算法v

12、oid createHeap(RECORDNODE a[],int p,int n){/*將a[p:n]建立為以a[p]為根的最大堆*/int i,j,k;i=p; j=2*i;a[0]=a[i];/*a[i]暫存到a[0]中*/while(j<=n){if(j<n&&a[j].key<a[j+1].key) j++;/*選兩子女的較大者*/if(a[0].key<a[j].

13、key){/*a[j]移向堆頂*/a[i]=a[j];i=j;j=2*i;} else break;}a[i]=a[0];},計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,③ 對(duì)于一個(gè)無序序列a[1..n]構(gòu)成的完全二叉樹，只要從它最后一個(gè)非終端結(jié)點(diǎn)：(n/2)開始直到根結(jié)點(diǎn)為止，逐步進(jìn)行上述調(diào)整，即可將該完全二叉樹調(diào)整為堆。 算法為：int p=n/2,i;for (i=p;i>=1;i--)

14、createHeap(a,i,n);,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,4）堆排序由以下兩個(gè)步驟進(jìn)行：① 由給定的無序序列構(gòu)造最大堆；② 最大堆堆頂a[1]具有最大的關(guān)鍵字,將a[1]與a[n]對(duì)調(diào),把具有最大關(guān)鍵字的對(duì)象交換到最后,再對(duì)前面的n-1個(gè)對(duì)象,使用堆的調(diào)整算法Sieve(a,1,n-1),重新建立最大堆,具有次最大關(guān)鍵字的對(duì)象又上浮到a[1]位置。再對(duì)調(diào)a[1]和a[n-1],調(diào)用Sieve(

15、a,1,n-2),對(duì)前n-2個(gè)對(duì)象重新調(diào)整，…。如此反復(fù)執(zhí)行，最后得到全部排序好的對(duì)象序列。這個(gè)算法即堆排序算法。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,堆排序的算法Void HeapSort(RECORDNODE a[],int n){/

16、*使用堆排序算法對(duì)記錄數(shù)組a[1:n]按關(guān)鍵字遞增排序*/int i;for(i=n/2;i>=1;i--) createHeap(a,i,n);/*建立初始最大堆*/for(i=n;i>=2;i--){a[0]=a[1]; a[1]=a[i];a[i]=a[0];/*交換a[1]和a[I]*/createHeap (a,1,i-1);/*重建最大堆*/}},計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序

17、,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,5) 算法分析若設(shè)堆中有 n 個(gè)結(jié)點(diǎn), 且 2k-1 ? n ? 2k, 則對(duì)應(yīng)的完全二叉樹有 k 層。在第 i 層上的結(jié)點(diǎn)數(shù) ? 2i-1 (i = 1, 2, …, k)。在第一個(gè)形成初始堆的 for 循環(huán)中對(duì)每一個(gè)非葉結(jié)點(diǎn)調(diào)用了一次堆調(diào)整算法createHeap(),因此該循環(huán)所用的計(jì)算時(shí)間為：,其中, i 是層序號(hào), 2i-1 是第 i 層的最大結(jié)點(diǎn)數(shù), (k-i)是

18、第 i 層結(jié)點(diǎn)能夠移動(dòng)的最大距離。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 堆排序,第二個(gè)for循環(huán)中調(diào)用了n-1次createHeap( )算法, 該循環(huán)的計(jì)算時(shí)間為O(nlog2n)。因此, 堆排序的時(shí)間復(fù)雜性為O(nlog2n)。該算法的附加存儲(chǔ)主要是在第二個(gè)for循環(huán)中用來執(zhí)行對(duì)象交換時(shí)所用的一個(gè)臨時(shí)對(duì)象。因此，該算法的空間復(fù)雜性為O(1)。堆排序是一個(gè)不穩(wěn)定的排序方法。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,三、插入排序,插入排序

19、是將當(dāng)前無序區(qū)中最前端的記錄插入到有序區(qū)中，逐漸擴(kuò)大有序區(qū)，直到所有記錄都插入到有序區(qū)中為止。1. 直接插入排序1)基本思想是 : 當(dāng)插入第i (i ? 1) 個(gè)對(duì)象時(shí), 前面的a[0], a[1] , … , a[i-1]已經(jīng)排好序。這時(shí), 用a[i]的排序碼與a[i-1], a[i-2], …的關(guān)鍵碼順序進(jìn)行比較, 找到插入位置即將a[i]插入, 原來位置上的對(duì)象向后順移。 為了減少查找關(guān)鍵碼時(shí)的比較次數(shù)，可在有序區(qū)的前端a

20、[0]處設(shè)一個(gè)監(jiān)視哨，存放當(dāng)前要插入的關(guān)鍵字。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,各趟排序結(jié)果,21,25,49,25*,16,08,1 2 3 4 5 6,,0 1 2 3 4 5 6,21,25,49,25*,16,08,25,i = 2,0 1 2

21、 3 4 5 6,,21,25,49,25*,16,08,49,i = 3,,,,,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,,21,25,49,25*,16,08,,21,25,49,25*,16,08,i = 5,,21,25,49,25*,16,08,i = 6,,,,,i = 4,25*,,,,16,,,,,08,,,,,,0 1 2 3

22、 4 5 6,0 1 2 3 4 5 6,0 1 2 3 4 5 6,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,16,,49,16,16,,,21,25,49,25*,16,08,1 2 3 4 5

23、 6,21,25,49,25*,08,i = 4 時(shí)的排序過程,21,25,49,25*,完成,16,,08,16,,i = 5j = 4,i = 5j = 3,0 1 2 3 4 5 6,0 1 2 3 4 5 6,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,,25

24、,,25*,16,,16,,21,25,49,25*,08,21,49,25*,08,21,25,49,25*,16,08,16,,16,25,21,,,i = 5j = 2,i = 5j = 1,i = 5j = 0,,16,0 1 2 3 4 5 6,0 1 2 3 4 5

25、 6,0 1 2 3 4 5 6,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,三、插入排序,2）函數(shù)實(shí)現(xiàn)void straightInsert(RECORDNODE r[],int n){/*使用直接插入排序法對(duì)數(shù)組a(1:n)排序*/for (i=2;i<=n;i++){a[0]=a[i]; /*設(shè)置監(jiān)視哨*/ j=i-1;while

26、(a[0].key<a[j].key){a[j+1]=a[j];j--;}a[j+1]=a[0];}},計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,三、插入排序,3) 算法分析設(shè)待排序?qū)ο髠€(gè)數(shù)為n, 則該算法的while循環(huán)執(zhí)行n-1趟。關(guān)鍵碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)與對(duì)象關(guān)鍵碼的初始排列有關(guān)。最好情況下, 排序前對(duì)象已按關(guān)鍵碼從小到大有序, 每趟只需與前面有序?qū)ο笮蛄械淖詈笠粋€(gè)對(duì)象比較1次, 移動(dòng)2次對(duì)象,

27、總的關(guān)鍵碼比較次數(shù)為 n-1, 對(duì)象移動(dòng)次數(shù)為 2(n-1)。最壞情況下, 第 i 趟時(shí)第 i 個(gè)對(duì)象必須與前面 i 個(gè)對(duì)象都做關(guān)鍵碼比較, 并且每做1次比較就要做1次數(shù)據(jù)移動(dòng)。則總關(guān)鍵碼比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN分別為,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,三、插入排序,在平均情況下的排序碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)約為 n2/4。因此，直接插入排序的時(shí)間復(fù)雜度為 o(n2)。直接插入排序是一種穩(wěn)定的排序方法。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),

28、查找與排序,三、插入排序,2. 折半插入排序1）與直接插入排序相比，除了采用的是折半查找尋找插入的位置外，其它類似。2）算法void BinarySort(RECORDNODE a[],int n){for (i=2;i=low;j--) r[j+1]=r[j];r[low]=r[0];}},計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,三、插入排序,3) 算法分析折半查找比順序查找查找快, 所以折半插入排序就平均性能來說比直接

29、插入排序要快。它所需的關(guān)鍵碼比較次數(shù)與待排序?qū)ο笮蛄械某跏寂帕袩o關(guān), 僅依賴于對(duì)象個(gè)數(shù)。在插入第 i 個(gè)對(duì)象時(shí), 需要經(jīng)過 ?log2i? +1 次關(guān)鍵碼比較, 才能確定它應(yīng)插入的位置。因此, 將 n 個(gè)對(duì)象(為推導(dǎo)方便, 設(shè)為 n=2k )用折半插入排序所進(jìn)行的排序碼比較次數(shù)為：,其記錄移動(dòng)的數(shù)目與直接插入排序相同因此，此算法的時(shí)間復(fù)雜度為O(n2)折半插入排序是一個(gè)穩(wěn)定的排序算法,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,三、插入排序,

30、3. 希爾排序1) 希爾排序方法又稱為縮小增量排序。2) 該方法的基本思想是 : 設(shè)待排序?qū)ο笮蛄杏?n 個(gè)對(duì)象, 首先取一個(gè)整數(shù) gap < n 作為間隔, 將全部對(duì)象分為 gap 個(gè)子序列, 所有距離為 gap 的對(duì)象放在同一個(gè)子序列中,在每一個(gè)子序列中分別施行直接插入排序。然后縮小間隔 gap, 例如取 gap = ?gap/2?，重復(fù)上述的子序列劃分和排序工作。直到最后取 gap = 1, 將所有對(duì)象放在同一個(gè)序列

31、中排序?yàn)橹埂?計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,開始時(shí) gap 的值較大, 子序列中的對(duì)象較少, 排序速度較快; 隨著排序進(jìn)展, gap 值逐漸變小, 子序列中對(duì)象個(gè)數(shù)逐漸變多, 由于前面工作的基礎(chǔ), 大多數(shù)對(duì)象已基本有序, 所以排序速度仍然很快。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,3.希爾排序,3）函數(shù)實(shí)現(xiàn)Void shellSort(RECORDNODE s[],

32、int n){/*對(duì)記錄數(shù)組s[1:n]進(jìn)行希爾排序*//* d1=n/2,di=di-1/2 */int i,j,d;d=n/2;/*d是間隔*/while(d){/*循環(huán)直到d為0*/for(i=d+1;id;j=j-d)if(s[j].key>s[0].key) s[j]=s[j-d]else break;s[j]=s[0];}d=d/2;}},計(jì)算機(jī)

33、軟件技術(shù)基礎(chǔ),查找與排序,3.希爾排序,4) 算法分析Gap的取法有多種。最初 shell 提出取 gap = ?n/2?，gap = ?gap/2?，直到gap = 1。knuth 提出取 gap = ?gap/3? +1。對(duì)特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算排序碼的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。想要弄清排序碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)與增量選擇之間的依賴關(guān)系，并給出完整的數(shù)學(xué)分析，還沒有人能夠做到。 Knuth利用大量實(shí)驗(yàn)統(tǒng)計(jì)資料得

34、出 : 當(dāng) n 很大時(shí)，排序碼平均比較次數(shù)和對(duì)象平均移動(dòng)次數(shù)大約在 n1.25 到 1.6n1.25 的范圍內(nèi)。這是在利用直接插入排序作為子序列排序方法的情況下得到的。希爾排序是一種不穩(wěn)定的排序方法,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,四、交換排序,交換排序是根據(jù)序列中兩個(gè)結(jié)點(diǎn)關(guān)鍵字的比較結(jié)果，來對(duì)換在序列中的位置。算法的特點(diǎn)是將關(guān)鍵字較大的結(jié)點(diǎn)向序列的尾部移動(dòng)，關(guān)鍵字較小的結(jié)點(diǎn)向序列的前部移動(dòng)?；舅枷胧莾蓛杀容^待排序?qū)ο蟮呐判虼a,

35、如發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之。直到所有對(duì)象都排好序?yàn)橹埂?計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,四、交換排序,1. 冒泡排序基本方法：設(shè)待排序?qū)ο笮蛄兄械膶?duì)象個(gè)數(shù)為 n。最多作 n-1 趟, i = 1, 2, ?, n-1。在第 i 趟中從后向前，j = n, n-1, ?, i，順次兩兩比較a[j-1]和a[j]。如果發(fā)生逆序，則交換a[j-1]和a[j]。1）過程：對(duì)無序表進(jìn)行掃描，當(dāng)發(fā)現(xiàn)相鄰兩個(gè)記錄關(guān)

36、鍵字逆序時(shí)就進(jìn)行交換，第一次掃描后就將最大關(guān)鍵字記錄沉到底部，而關(guān)鍵字較小的記錄則像氣泡一樣逐漸上浮。然后對(duì)剩下的記錄再進(jìn)行掃描，直到某次掃描時(shí)不發(fā)生交換，則排序完成。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,1. 冒泡排序,2)算法void BubbleSort(RECORDNODE a[],int n){/*使用冒泡排序算法，對(duì)記錄數(shù)組a[1:n}排序*/int i,j;int exchange =

37、1;/*標(biāo)志，記錄是否有交換*/for(i=1;ii;j--)if(a[j-1].key>a[j].key){/*逆序*/a[0]=a[j];a[j]=a[j-1];a[j-1]=a[0];/*交換*/ exchange = 1;/*標(biāo)志置為1,有交換*/}}},計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,1. 冒泡排序,算法也可寫成：void BubbSort(R

38、ECORDNODE a[],int n){int i;for (i=0;ia[j].key){ t=a[i]; a[i]=a[j]; a[j]=t; }},計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,1. 冒泡排序,3) 算法分析第i趟對(duì)待排序?qū)ο笮蛄衋[i],a[I+1],?,a[n]進(jìn)行排序, 結(jié)果將該序列中排序碼最小的對(duì)象交換到序列的第一個(gè)位置(i), 其它對(duì)象也都向排序的最終位置移動(dòng)。在個(gè)別情形

39、, 對(duì)象可能在排序中途向相反的方向移動(dòng)。最多做n-1趟冒泡就能把所有對(duì)象排好序。在對(duì)象的初始排列已經(jīng)按關(guān)鍵字從小到大排好序時(shí),此算法只執(zhí)行一趟起泡,做n-1次關(guān)鍵字比較,不移動(dòng)對(duì)象。這是最好的情形。最壞的情形是算法執(zhí)行n-1趟起泡,第i趟 (1? i? n) 做 n- i 次關(guān)鍵字比較, 執(zhí)行 n-i 次對(duì)象交換。這樣在最壞情形下總的關(guān)鍵字比較次數(shù)KCN和對(duì)象移動(dòng)次數(shù)RMN為：,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,1. 冒泡排序,冒泡

40、排序的平均時(shí)間復(fù)雜度為O(n2)起泡排序需要一個(gè)附加對(duì)象以實(shí)現(xiàn)對(duì)象值的對(duì)換。起泡排序是一個(gè)穩(wěn)定的排序方法。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,四、交換排序,2. 快速排序1）基本思想快速排序是對(duì)冒泡排序的一種改進(jìn)?；舅枷胧侨稳〈判?qū)ο笮蛄兄械哪硞€(gè)對(duì)象 (例如取第一個(gè)對(duì)象) 作為基準(zhǔn),按照該對(duì)象的關(guān)鍵字大小,將整個(gè)對(duì)象序列劃分為左右兩個(gè)子序列： 左側(cè)子序列中所有對(duì)象的關(guān)鍵字都小于或等于基準(zhǔn)對(duì)象的關(guān)鍵字 右側(cè)子序列中所有對(duì)象

41、的關(guān)鍵字都大于基準(zhǔn)對(duì)象的關(guān)鍵字基準(zhǔn)對(duì)象則排在這兩個(gè)子序列中間(這也是該對(duì)象最終應(yīng)安放的位置)。然后分別對(duì)這兩個(gè)子序列重復(fù)施行上述方法，直到所有的對(duì)象都排在相應(yīng)位置上為止。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 快速排序,2）分割過程① 選取表中一個(gè)元素a[k]（一般選取第一元素），令x=a[k]，稱為控制關(guān)鍵字，用控制關(guān)鍵字和無序區(qū)中其余元素關(guān)鍵字進(jìn)行比較。② 設(shè)置兩個(gè)指示器i,j，分別表示線性表第一個(gè)和最后一個(gè)元素位置。

42、③ 將j逐漸減小，逐次比較a[j]與x，直到出現(xiàn)一個(gè)a[j]x，然后將a[i]移到a[j]位置。如此反復(fù)進(jìn)行，直到i=j為止，最后將x移到a[j]位置，完成一趟排序。此時(shí)以x為界將原數(shù)組分割成兩個(gè)子區(qū)。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 快速排序,3）算法：void QuickSort(RECORDNODE a[],int low,int high){/*對(duì)

43、記錄數(shù)組a[low:high]進(jìn)行快速排序*/if(low>=high) return;t=a[low]; i=low; j=high;while(i=t.key) j--;/*從末端向中間搜索*/if(i<j) a[i]=a[j];while(i<j&&a[i]<=t.key) i++;/*從前端向中間搜索*/if(i<j) a[j]=a[i];}a[i]=t;if

44、(low<i-1) QuickSort(a,low,i-1); if(i+1<high) QuickSort(a,i+1,high);},計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,4）舉例：設(shè)序列為{46,55,13,42,94,5,17,70},,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 快速排序,5) 算法分析算法quicksort是一個(gè)遞歸的算法, 其遞歸樹如圖所示。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 快速排序,快速排序的趟

45、數(shù)取決于遞歸樹的高度。如果每次劃分對(duì)一個(gè)對(duì)象定位后, 該對(duì)象的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同, 則下一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序, 這是最理想的情況。在 n個(gè)元素的序列中,對(duì)一個(gè)對(duì)象定位所需時(shí)間為 O(n)。若設(shè)t(n) 是對(duì) n 個(gè)元素的序列進(jìn)行排序所需的時(shí)間, 而且每次對(duì)一個(gè)對(duì)象正確定位后, 正好把序列劃分為長(zhǎng)度相等的兩個(gè)子序列, 此時(shí), 總的計(jì)算時(shí)間為：T(n)? cn + 2T(n/2) /*

46、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) ………? cn log2n + nT(1) = O(n log2n ),計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 快速排序,可以證明, 函數(shù)quicksort的平均計(jì)算時(shí)間也是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明: 就平均計(jì)算時(shí)間而言, 快速排序

47、是所有內(nèi)排序方法中最好的一個(gè)?？焖倥判蚴沁f歸的，需要有一個(gè)棧存放每層遞歸調(diào)用時(shí)的指針和參數(shù)。最大遞歸調(diào)用層次數(shù)與遞歸樹的高度一致,理想情況為 ?log2(n+1)? 。因此，要求存儲(chǔ)開銷為 O(log2n)。在最壞的情況, 即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵字從小到大排好序的情況下, 其遞歸樹成為單支樹, 每次劃分只得到一個(gè)比上一次少一個(gè)對(duì)象的子序列?？偟年P(guān)鍵字比較次數(shù)將達(dá),因此，快速排序在最壞情況下的時(shí)間復(fù)雜度為O(n2) 快速排序

48、是一種不穩(wěn)定的排序方法。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,用第一個(gè)對(duì)象作為基準(zhǔn)對(duì)象,快速排序退化的例子,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,2. 快速排序,其排序速度退化到簡(jiǎn)單排序的水平, 比直接插入排序還慢。占用附加存儲(chǔ)(棧)將達(dá)到O(n)。改進(jìn)辦法: 取每個(gè)待排序?qū)ο笮蛄械牡谝粋€(gè)對(duì)象、最后一個(gè)對(duì)象和位置接近正中的 3 個(gè)對(duì)象，取其關(guān)鍵字居中者作為基準(zhǔn)對(duì)象。,用居中排序碼對(duì)象作為基準(zhǔn)對(duì)象,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,五、歸并排序,1

49、. 歸并，是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。對(duì)象序列a中兩個(gè)有序表a[l] …a[m]和a[m+1] …a[n]。它們可歸并成一個(gè)有序表, 存于另一對(duì)象序列b的b[l] …b[n] 中。這種歸并方法稱為兩路歸并 (2-way merging)。設(shè)變量 i 和 j 分別是表a[l] …a[m]和a[m+1] …a[n]的當(dāng)前檢測(cè)指針。變量 k 是存放指針。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,五、歸并排序,當(dāng) i 和 j

50、都在兩個(gè)表的表長(zhǎng)內(nèi)變化時(shí), 根據(jù)對(duì)應(yīng)項(xiàng)的排序碼的大小,依次把排序碼小的對(duì)象排放到新表 k 所指位置中；當(dāng) i 與 j 中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí)，將另一個(gè)表中的剩余部分照抄到新表中。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,五、歸并排序,2. 歸并排序歸并排序算法就是利用兩路歸并過程進(jìn)行排序的。其基本思想是：假設(shè)初始對(duì)象序列有 n 個(gè)對(duì)象，首先把它看成是 n 個(gè)長(zhǎng)度為 1 的有序子序列 (歸并項(xiàng))，先做兩兩歸并，得到 ?n / 2? 個(gè)長(zhǎng)度為

51、 2 的歸并項(xiàng) (如果 n 為奇數(shù)，則最后一個(gè)有序子序列的長(zhǎng)度為1)；再做兩兩歸并，…，如此重復(fù)，最后得到一個(gè)長(zhǎng)度為 n 的有序序列。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,五、歸并排序,兩路歸并算法的函數(shù)實(shí)現(xiàn)void merge(int start,int end,int m,RECORDNODE a[]){/*將有序表a(start:m)和a(m+1:end)歸并為一個(gè)新的有序表a(start:end)*/RECORDNODE t

52、emp[MAXSIZE];int i,j,k;i=start;j=m+1;k=start;while(i<=m&&j<=end)if(a[i].key<a[i].key){temp[i]=a[i];k++;I++;}else{temp[k]=a[j];k++;j++;}while(j<=end){temp[k]=a[j];k++;j++;}while(i<=m

53、){temp[k]=a[i];k++;i++;}for(i=start;i<=end;I++) a[i]=temp{i};/*臨時(shí)表的內(nèi)容存回到a中*/},計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,五、歸并排序,歸并排序的算法void MergeSort(RECORDNODE a[],int n){/*對(duì)長(zhǎng)度為n的數(shù)組a排序*/Int length,left,right;left=0;length=1;while(l

54、ength<N){right=min(n-1,left+2*length-1)//限制right的值，使其不越界Merge(left,right,length,a);if(right+length<N) left=right+1;//右邊還有待合并段else{length*=2;left=1;}//從新開始下一趟排序}},計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,五、歸并排序,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),

55、查找與排序,五、歸并排序,3. 算法分析1) 時(shí)間復(fù)雜度在函數(shù)MergeSort中while循環(huán)將被執(zhí)行l(wèi)og2n次在while循環(huán)中，將調(diào)用Merge函數(shù)n/(2length)次而在Merge函數(shù)中，將比較length次,故在while循環(huán)中，將比較O(n)次因此，此算法的時(shí)間復(fù)雜度為O(nlogn)2) 空間復(fù)雜度歸并排序占用附加存儲(chǔ)較多, 需要另外一個(gè)與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組。這是這個(gè)算法的缺點(diǎn)。3

56、) 歸并排序是一個(gè)穩(wěn)定的排序算法,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,六、各種排序方法的比較,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,六、各種排序方法的比較,? 原則1）待排序記錄的個(gè)數(shù)2）記錄本身的大小3）關(guān)鍵字的分布情況4）對(duì)排序穩(wěn)定性的要求5）現(xiàn)有語言工具條件等,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,六、各種排序方法的比較,? 結(jié)論1）若待排序的記錄數(shù)n較小（n≤50），則可采用插入排序或直接選擇排序。且由于插入排序的移動(dòng)次數(shù)

57、較選擇排序多，因此若記錄本身較大時(shí)宜采用選擇排序。2）若n較大，則應(yīng)采用時(shí)間復(fù)雜度O(nlog2n)的排序方法，如快速排序或堆排序。當(dāng)排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均運(yùn)行時(shí)間最短；堆排序只需1個(gè)輔助空間，且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞情況，但堆排序的建堆時(shí)間較長(zhǎng)。3）若待排序記錄按關(guān)鍵字基本有序，則宜采用插入排序或冒泡排序。,計(jì)算機(jī)軟件技術(shù)基礎(chǔ),查找與排序,六、各種排序方法的比較,4）從方法的穩(wěn)定性看，所有時(shí)間復(fù)雜度為O(