數(shù)據(jù)結(jié)構(gòu)之排序課件(已改無錯(cuò)字)
2022-10-13 09:02:20 本頁面
【正文】 時(shí)，因?yàn)榈?h（ 1≤h≤k1）層最多有 2h1個(gè)元素，而每一個(gè)元素的最大調(diào)整次數(shù)為 kh，故總的調(diào)整次數(shù)不大于 4n。 堆排序在最壞的情況下，其時(shí)間復(fù)雜度為 O（ nlog2n）。 ?堆排序是不穩(wěn)定的。 返回 歸并排序 ?歸并是指將若干個(gè)已排序好的有序表合并成一個(gè)有序表。 ?兩個(gè)有序表的歸并稱為二路歸并。 ?歸并排序就是利用歸并過程，開始時(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的有序表為止，就完成了排序。 歸并排序算法 void merge (r[], r2[], s, m, t) /*把兩個(gè)有序子 { /*序列 r[s… m]和 r[m+1… t]歸 int i, j, k。 /*并成一個(gè)有序序列 r2[s… t] i=s。 j=m+1。 k=s。 /*k為數(shù)組 r2[ ]的下標(biāo) while ( i=m amp。amp。 j=t) { if (r[i].key = r[j].key) /*比較當(dāng)前 r2[k++]=r[i++]。 /*記錄 else r2[k++]=r[j++]。 /*復(fù)制 } 歸并排序算法續(xù) while (i=m) /*把子序列 r[s… m]中剩 r2[k++]=r[i++]。 /*余的部分 copy到 while (j=t) /*r2[]中 r2[k++]=r[j++]。 } ?上面的算法是對(duì)兩個(gè)有序序列歸并成一個(gè)有序序列。若待排序的序列在一個(gè)數(shù)組 r[1…n] 中，可把 n個(gè)記錄分成 n個(gè)子序列，兩兩歸并， …… 直到歸并成一個(gè)有 n個(gè)記錄的有序序列為止。 ?二路歸并的遞歸算法如下： 二路歸并排序函數(shù) void mergesort (r[], r1[], s, t) /*將 r[s..t]中的記 { int k。 /*錄 2路歸并后放在 r1[s..t]中 if (s=t) r1[s]=r[s]。 else { k=(s+t)/2。 mergesort (r, r2, s, k)。 mergesort (r, r2, k+1, t)。 merge (r2, r1, s, k, t)。 } } 歸并排序分析 ?二路歸并排序的時(shí)間復(fù)雜性為 O(nlogn)，與堆排序和快速排序平均情況的時(shí)間復(fù)雜性是相同數(shù)量級(jí)。 ?歸并排序是穩(wěn)定的排序方法。 返回 基數(shù)排序 ?基數(shù)排序 (Radix sort)最初是用于在卡片排序機(jī)上處理穿孔卡片的一種排序方法?；鶖?shù)排序是采用“分散”的辦法排序。 ?設(shè)每張卡片對(duì)應(yīng)著一個(gè)多位數(shù)的關(guān)鍵字，在卡片排序機(jī)中對(duì)卡片進(jìn)行多趟“分散”過程，每一趟逐張檢查卡片關(guān)鍵字的某一位數(shù)，將此位數(shù)取值相同的卡片放入同一片盒中。 ?一趟“分散”過程結(jié)束后，在此排列基礎(chǔ)上，再進(jìn)行下一趟檢查另一位數(shù)的“分散”。 ?對(duì)關(guān)鍵字的檢查從低位到高位進(jìn)行，到檢查最高位的一趟“分散”過程結(jié)束，最后將卡片“收集”起來即排序完畢。 ?設(shè)一組關(guān)鍵字的個(gè)數(shù)為 n（即卡片的張數(shù)），每個(gè)關(guān)鍵字的位數(shù)為 d，每位數(shù)可能有 rd種取值，則這種排序方法需進(jìn)行 d趟“分散”，每趟檢查 n張卡片的某一位數(shù)，并按此位數(shù)值的不同，將卡片分別放到 rd個(gè)卡片盒中。 ?每位數(shù)可能取值的數(shù)目 rd稱為基數(shù) (Radix)，例如對(duì)于十進(jìn)制數(shù)的每一位可能有 0到 9十種取值，故基數(shù)為 10；而二進(jìn)制的每一位數(shù)只能有 0和 1兩種取值，則基數(shù)為 2。 ?圖 。 圖 基數(shù)排序 3 0 6 0 2 8 0 0 9 9 4 8 5 0 5 9 1 7 7 2 1 4 3 0 3 9 0 ( a ) 原始數(shù)據(jù) key 390 430 721 505 306 917 948 028 009 盒 0 1 2 3 4 5 6 7 8 9 4 3 0 3 9 0 7 2 1 5 0 5 3 0 6 9 1 7 0 2 8 9 4 8 0 0 9 ( b ) 第一趟 key 009 306 505 917 028 721 430 948 390 盒 0 1 2 3 4 5 6 7 8 9 5 0 5 3 0 6 0 0 9 9 1 7 7 2 1 0 2 8 4 3 0 9 4 8 3 9 0 ( c ) 第二趟 key 028 009 390 306 430 505 721 948 917 盒 0 1 2 3 4 5 6 7 8 9 0 0 9 0 2 8 3 0 6 3 9 0 4 3 0 5 0 5 7 2 1 9 1 7 9 4 8 ( d ) 第三趟 ?為每個(gè)“盒”設(shè)置一個(gè)鏈接隊(duì)列，并將各隊(duì)列的隊(duì)首和隊(duì)尾指針分別存于兩個(gè)一維數(shù)組中。 ?開始時(shí)，將原始數(shù)據(jù)構(gòu)成一個(gè)鏈接隊(duì)列，設(shè)各“盒”的隊(duì)列均為空隊(duì)列。然后將原始數(shù)據(jù)隊(duì)列中各結(jié)點(diǎn)，按所考慮的關(guān)鍵字某位數(shù)的值插入到相應(yīng)“盒”的隊(duì)列中去。 ?當(dāng)一趟結(jié)束時(shí)，再把各“盒”的隊(duì)列依次首尾相連，鏈接成一個(gè)鏈接隊(duì)列，以此作為下一趟的輸入。 ?如此反復(fù)進(jìn)行，直至做完 d趟，即排序結(jié)束。 數(shù)據(jù)類型 ?設(shè)基數(shù)排序中記錄的數(shù)據(jù)類型如下： struct element { int key[d]。 /*d為關(guān)鍵字的位數(shù) */ int next。 }。 element rsqlist[n]。 基數(shù)排序算法 void radixsort (rsqlist r, int d, int n,int p) { /*d為關(guān)鍵字的位數(shù) ， n為待排序的數(shù)據(jù)個(gè)數(shù) ， p指向鏈表中的第一個(gè)結(jié)點(diǎn) */ int i,j,t。 int f[rd], e[rd]。 /*隊(duì)列的頭 、 尾指示器 ， rd是基數(shù) ， 十進(jìn)制為 10*/ for (i=1。 i=n1。 i++) r[i].next=i+1。 r[n].next=0。 p=1。 /*原始數(shù)據(jù)串成靜態(tài)鏈表，頭指針為 p*/ 基數(shù)排序算法續(xù) for ( i=d。 i0。 i) /*從關(guān)鍵字的最后一位開始 */ { for (j=0。 jrd。 j++) f[j]=0。 /* 隊(duì)列指示器置初值 */ while (i!=0) /*進(jìn)行分配 */ { t=r[p].key[i]。 if (f[t]==0) f[t]=p。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1