【正文】 19 ] ( 2) 3 6 [ 15 10 20 8 13 19 ] ( 3) 3 6 8 [ 10 20 15 13 19 ] ( 4) 3 6 8 10 [ 20 15 13 19 ] ( 5) 3 6 8 10 13 [ 15 20 19 ] ( 6) 3 6 8 10 13 15 [ 20 19 ] ( 7) 3 6 8 10 13 15 19 20 簡單選擇排序算法 void selectsort (r[ ], n) { int i, j, k。 } } 簡單選擇排序分析 ?簡單選擇排序在 (n1)趟掃描中共需進行n(n1)/2次比較，最壞情況下的互換次數(shù)為 (n1)，整個算法的時間復雜性為 O(n2)。 i=t。 (r[0].keyr[k].key)) { r[k+d}.key=r[k].key。 ?第一次劃分以后，再用相同的算法對劃成的兩部分分別進行類似的運算，即從每一部分中任選一個數(shù)據將其劃分成更小的兩部分。 ?最后一行只有一個括號，說明 i與 j相等了，此單元即是數(shù)據 13的最終位置。 } 快速排序算法續(xù) while (r[i].key =) amp。 } ?整個快速排序過程如下： Void quicksort(r[], low, hig) { int k。 快速排序分析 ?快速排序的平均時間復雜性為 O(nlogn)，對 n較大的情況，這種算法是平均速度最快的排序算法，但當 n很小時，此方法往往比其他簡單排序方法還要慢。 ? ?2/j?由堆的定義可知，其根結點（即在數(shù)組中下標為 1的結點）具有最小的關鍵字，堆排序就是利用這一特點進行的。 if (r[j].key) /*j為左右兒子中較小者的下標 { r[i]=r[j]。 i=1。 堆排序在最壞的情況下，其時間復雜度為 O（ nlog2n）。 k=s。若待排序的序列在一個數(shù)組 r[1…n] 中，可把 n個記錄分成 n個子序列，兩兩歸并， …… 直到歸并成一個有 n個記錄的有序序列為止。 ?歸并排序是穩(wěn)定的排序方法。 ?圖 。 }。 p=1。 else r[e[t]].next=p。 if (f[j]!=0) { r[t].next=f[j]。 例 ?解 : 快速排序各趟的結果如下 : [60 20 31 1 5 44 55 61 200 30 80 150 4 29] [29 20 31 1 5 44 55 4 30] 60 [80 150 200 61] [4 20 5 1] 29 [44 55 31 30] 60 [61] 80 [200 150] [1] 4 [5 20] 29 [30 31] 44 [55] 60 61 80 150 [200] 1 4 5 [20] 29 30 [31] 44 55 60 61 80 150 200 1 4 5 20 29 30 31 44 55 60 61 80 150 200 例 ?已知序列 {26,5,77,1,61,11,59,15,48,19}寫出采用歸并排序算法排序的每一趟的結果。 while(p!=NULL) { min=p。 4. 已知序列 {491， 77， 572， 16， 996， 101， 863，258， 689， 325}，請分別給出采用快速排序、堆排序和基數(shù)排序法對該序列作遞增排序時每一趟的結果。試編寫一算法將 A排序，結果存放在數(shù)組 B[n]中，要求算法的時間復雜性為 O(n)。 2. 設計一個用單鏈表作存儲結構的直接插入排序算法。 pkey=minkey。 }。 028 p 306 009 948 505 917 721 430 3 9 0 0 第一趟分配后各隊列情況 f [ 0 ] r [ 0 ] 430 390 f [ 1 ] r [ 1 ] 721 f[2] r[2] N U L L f[3] r[3] N U L L f[4] r[4] N U L L f [ 5 ] r [ 5 ] 505 f [ 6 ] r [ 6 ] 306 f [ 7 ] r [ 7 ] 917 f [ 8 ] r [ 8 ] 028 948 f [ 9 ] 009 r [ 9 ] 第一趟收集后的情況 390 p 430 721 505 306 917 028 948 0 0 9 0 第三趟分配后各隊列情況 f [ 0 ] r [ 0 ] 009 028 f[2] r[2] N U L L f[1] r[1] N U L L f [ 3 ] r [ 3 ] 306 390 f [ 4 ] r [ 4 ] 430 f [ 5 ] r [ 5 ] 505 f[6] r[6] N U L L f[8] r[8] N U L L f [ 7 ] r [ 7 ] 721 f [ 9 ] r [ 9 ] 917 948 第三趟收集后的情況 028 p 009 306 390 430 505 721 917 948 0 基數(shù)排序分析 ?采用基數(shù)排序需進行 d趟關鍵字的分散和收集過程，每趟運算時間為 O(n+rd)，故總的時間復雜性為 O(d(n+rd))。 while (f[j]==0) j++。 jrd。 /*隊列的頭 、 尾指示器 ， rd是基數(shù) ， 十進制為 10*/ for (i=1。 ?當一趟結束時，再把各“盒”的隊列依次首尾相連，鏈接成一個鏈接隊列，以此作為下一趟的輸入。 ?一趟“分散”過程結束后，在此排列基礎上，再進行下一趟檢查另一位數(shù)的“分散”。 mergesort (r, r2, s, k)。 /*記錄 else r2[k++]=r[j++]。 ?歸并排序就是利用歸并過程，開始時先將 n個數(shù)據看成 n個長度為 1的已排好序的表，將相鄰的表成對合并，得到長度為 2的（ n/2）個有序表，每個表含有 2個數(shù)據；進一步再將相鄰表成對合并，得到長度為 4的（ n/4）個有序表； …… ；如此重復做下去，直至所有數(shù)據均合并到一個長度為 n的有序表為止，就完成了排序。 i) { r[1]?r[i]。 /*把 x放在 i的位置上 } 篩選算法 ?介紹第 1個問題，即把一個無序的序列建成一個堆。 /*R[i+1]和 R[i+2]為根的左右子樹是 x=r[i]。 ?（大根）堆（ Heap）：在一棵完全二叉樹中，