數(shù)據(jù)結(jié)構(gòu)之排序課件-wenkub.com
2024-08-27 09:02 本頁(yè)面
【正文】 試編寫(xiě)一算法將 A排序，結(jié)果存放在數(shù)組 B[n]中，要求算法的時(shí)間復(fù)雜性為 O(n)。 2. 設(shè)計(jì)一個(gè)用單鏈表作存儲(chǔ)結(jié)構(gòu)的直接插入排序算法。 4. 已知序列 {491， 77， 572， 16， 996， 101， 863，258， 689， 325}，請(qǐng)分別給出采用快速排序、堆排序和基數(shù)排序法對(duì)該序列作遞增排序時(shí)每一趟的結(jié)果。 pkey=minkey。 while(p!=NULL) { min=p。 }。 例 ?解 : 快速排序各趟的結(jié)果如下 : [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}寫(xiě)出采用歸并排序算法排序的每一趟的結(jié)果。 028 p 306 009 948 505 917 721 430 3 9 0 0 第一趟分配后各隊(duì)列情況 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 第三趟分配后各隊(duì)列情況 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ù)排序需進(jìn)行 d趟關(guān)鍵字的分散和收集過(guò)程，每趟運(yùn)算時(shí)間為 O(n+rd)，故總的時(shí)間復(fù)雜性為 O(d(n+rd))。 if (f[j]!=0) { r[t].next=f[j]。 while (f[j]==0) j++。 else r[e[t]].next=p。 jrd。 p=1。 /*隊(duì)列的頭 、 尾指示器 ， rd是基數(shù) ， 十進(jìn)制為 10*/ for (i=1。 }。 ?當(dāng)一趟結(jié)束時(shí)，再把各“盒”的隊(duì)列依次首尾相連，鏈接成一個(gè)鏈接隊(duì)列，以此作為下一趟的輸入。 ?圖 。 ?一趟“分散”過(guò)程結(jié)束后，在此排列基礎(chǔ)上，再進(jìn)行下一趟檢查另一位數(shù)的“分散”。 ?歸并排序是穩(wěn)定的排序方法。 mergesort (r, r2, s, k)。若待排序的序列在一個(gè)數(shù)組 r[1…n] 中，可把 n個(gè)記錄分成 n個(gè)子序列，兩兩歸并， …… 直到歸并成一個(gè)有 n個(gè)記錄的有序序列為止。 /*記錄 else r2[k++]=r[j++]。 k=s。 ?歸并排序就是利用歸并過(guò)程，開(kāi)始時(shí)先將 n個(gè)數(shù)據(jù)看成 n個(gè)長(zhǎng)度為 1的已排好序的表，將相鄰的表成對(duì)合并，得到長(zhǎng)度為 2的（ n/2）個(gè)有序表，每個(gè)表含有 2個(gè)數(shù)據(jù)；進(jìn)一步再將相鄰表成對(duì)合并，得到長(zhǎng)度為 4的（ n/4）個(gè)有序表； …… ；如此重復(fù)做下去，直至所有數(shù)據(jù)均合并到一個(gè)長(zhǎng)度為 n的有序表為止，就完成了排序。 堆排序在最壞的情況下，其時(shí)間復(fù)雜度為 O（ nlog2n）。 i) { r[1]?r[i]。 i=1。 /*把 x放在 i的位置上 } 篩選算法 ?介紹第 1個(gè)問(wèn)題，即把一個(gè)無(wú)序的序列建成一個(gè)堆。 if (r[j].key) /*j為左右兒子中較小者的下標(biāo) { r[i]=r[j]。 /*R[i+1]和 R[i+2]為根的左右子樹(shù)是 x=r[i]。 ? ?2/j?由堆的定義可知，其根結(jié)點(diǎn)（即在數(shù)組中下標(biāo)為 1的結(jié)點(diǎn)）具有最小的關(guān)鍵字，堆排序就是利用這一特點(diǎn)進(jìn)行的。 ?（大根）堆（ Heap）：在一棵完全二叉樹(shù)中，每個(gè)結(jié)點(diǎn)如果有兒子的話，此結(jié)點(diǎn)必須大于或等于其兒子結(jié)點(diǎn)。 快速排序分析 ?快速排序的平均時(shí)間復(fù)雜性為 O(nlogn)，對(duì) n較大的情況，這種算法是平均速度最快的排序算法，但當(dāng) n很小時(shí)，此方法往往比其他簡(jiǎn)單排序方法還要慢。 } } 快速排序分析 ?當(dāng)初始序列有序或基本有序時(shí)，快速排序就接近于冒泡排序了，其時(shí)間復(fù)雜度為 O(n*n). ?該算法是霍爾 1962年提出的。 } ?整個(gè)快速排序過(guò)程如下： Void quicksort(r[], low, hig) { int k。 j。 } 快速排序算法續(xù) while (r[i].key =) amp。amp。 ?最后一行只有一個(gè)括號(hào)，說(shuō)明 i與 j相等了，此單元即是數(shù)據(jù) 13的最終位置。 ?假設(shè)原始數(shù)據(jù)已存于一個(gè)一維數(shù)組 r中，具體的做法是：設(shè)兩個(gè)指示器 i和 j，初始時(shí) i指向數(shù)組中的第一個(gè)數(shù)據(jù)， j指向最末一個(gè)數(shù)據(jù)。 ?第一次劃分以后，再用相同的算法對(duì)劃成的兩部分分別進(jìn)行類似的運(yùn)算，即從每一部分中任選一個(gè)數(shù)據(jù)將其劃分成更小的兩部分。 ?任何增量序列能使用，但必須保證 t1=1；當(dāng)增量序列為 1時(shí)，該算法就退化成直接插入排序了。 (r[0].keyr[k].key)) { r[k+d}.key=r[k].key。 i++) { r[0]=r [i]。 i=t。 ?簡(jiǎn)單選擇 1. 輸入是已知的； 2. 每一趟排序結(jié)束后，所選擇的元素都 都放在了最終的位置上。 } } 簡(jiǎn)單選擇排序分析 ?簡(jiǎn)單選擇排序在 (n1)趟掃描中共需進(jìn)行n(n1)/2次比較，最壞情況下的互換次數(shù)為 (n1)，整個(gè)算法的時(shí)間復(fù)雜性為 O(n2)。 /*k始終記住到目前為止最小者的下標(biāo)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1