天津科技大學(xué)數(shù)據(jù)結(jié)構(gòu)排序-文庫吧資料
2024-10-25 15:10本頁面
【正文】 錄選到了堆頂?shù)奈恢?，而排序的結(jié)果應(yīng)是升序，所以，應(yīng)該將R[1]和 R[n]交換，這就得到了第一趟排序的結(jié)果。將初始的無序區(qū) R[1]到 R[n]建成一個(gè)大根堆，可用以下語句實(shí)現(xiàn)： for (i = n/2。 } R[i]=temp。j=2*i。 if (R[j].key) { R[i]=R[j]。amp。 j=2*i。 rectype temp。 例子： 關(guān)鍵字序列為 42， 13， 91， 23， 24， 16， 05，88， n=8，故從第四個(gè)結(jié)點(diǎn)開始調(diào)整 42 13 91 23 24 16 05 88 42 13 91 23 24 16 05 88 42 13 91 88 24 16 05 23 42 13 91 88 24 16 05 23 不調(diào)整 42 13 91 88 24 16 05 23 42 13 91 88 24 16 05 23 42 88 91 23 24 16 05 13 42 88 91 23 24 16 05 13 91 88 42 23 24 16 05 13 91 88 42 23 24 16 05 13 建成的堆 篩選算法 SIFT(rectype R[],int i。 若 R[i]的關(guān)鍵字已是三者中的最大者，則無須做任何調(diào)整，以 R[i]為根的子樹已構(gòu)成堆， 否則，將 R[i]和具有最大關(guān)鍵字的左孩子 R[2i]或右孩子 R[2i+1]進(jìn)行交換。 即只需依次將序號(hào)為 low(n/2)， low(n/2)1， ...，1的結(jié)點(diǎn)作為根的子樹都調(diào)整為堆即可。 10 15 56 25 30 70 10 15 56 25 30 70 小根堆示例 70 56 30 25 15 10 70 56 30 25 15 10 大根堆示例 堆排序的第一個(gè)工作是 建堆 ，即把整個(gè)記錄數(shù)組R[1]到 R[n]調(diào)整為一個(gè)堆。 堆排序分為兩個(gè)步驟： 根據(jù)初始輸入，形成初始堆。 直接選擇排序的時(shí)間復(fù)雜度 無論初始狀態(tài)如何，第 i 趟排序中選擇最小關(guān)鍵字的記錄，需做 ni次比較，因此總的比較次數(shù)為： 堆排序 樹型選擇排序 。 } } } ???????112 )(2/)1()(ninOnnin2. 當(dāng)文件為正序時(shí)，移動(dòng)次數(shù)為 0，文件初態(tài)為反序時(shí)，每趟排序均要執(zhí)行交換操作，總的移動(dòng)次數(shù)取最大值 3(n1)。 R[i]=R[k]。j++) if (R[j].keyR[k].key) k=j。 for (j=i+1。in1。 rectype temp。刪除具有最小關(guān)鍵字的對(duì)象，在剩下的對(duì)象中重復(fù)第 (1)、 (2)步，直到剩余對(duì)象只有一個(gè)為止。 四、選擇排序 基本原理 將待排序的結(jié)點(diǎn)分為已排序 (初始為空 )和為未排序兩組，依次將未排序的結(jié)點(diǎn)中值最小的結(jié)點(diǎn)插入已排序的組中。 可證 :快速排序的平均時(shí)間復(fù)雜度也是 O(nlog2n)。 快速排序的時(shí)間復(fù)雜度 考慮關(guān)鍵字的比較次數(shù)和對(duì)象移動(dòng)次數(shù) 最壞情況 每次劃分選取的基準(zhǔn)都是當(dāng)前無序區(qū)中關(guān)鍵字最小 (或最大 )的記錄，劃分的結(jié)果是基準(zhǔn)的左邊 (或右邊 )為空，劃分前后無序區(qū)的元素個(gè)數(shù)減少一個(gè)，因此，排序必須做 n1趟，每一趟中需做 ni次比較，所以最大比較次數(shù)為 n)O ( n l o gn C ( 1)nn l o g)C ( n / 22kn.. ....)8 C ( n / 23n)]2 C ( n / 24 [ n / 42n)4 C ( n / 22n)]2 C ( n / 22 [ n / 2n2 C ( n / 2)nC ( n )22kk3322?????????????????? 設(shè) C(n)表示對(duì)長(zhǎng)度為 n的序列進(jìn)行快速排序所需的比較次數(shù)，顯然，它應(yīng)該等于對(duì)長(zhǎng)度為 n的無序區(qū)進(jìn)行劃分所需的比較次數(shù) n1，加上遞歸地對(duì)劃分所得的左右兩個(gè)無序子區(qū)進(jìn)行快速排序所需的比較次數(shù)。 QUICKSORT(R,i+1,t1)。 if (s1t1){ i=PARTITION(R,s1,t1)。 return i。 } while (i!=j)。(ij)) i++。 while ((R[i].key=)amp。(ij)) j。 do { while ((R[j].key = )amp。 j=h。 基本過程 取待排序的結(jié)點(diǎn)序列中某個(gè)結(jié)點(diǎn)的值作為控制值，采用某種方法把這個(gè)結(jié)點(diǎn)放到適當(dāng)?shù)奈恢?，使得這個(gè)位置的左邊的所有結(jié)點(diǎn)的值都小于等于這個(gè)控制值，而這個(gè)位置的右邊的所有結(jié)點(diǎn)的值都大于等于這個(gè)控制值。 原因：關(guān)鍵字相同的兩個(gè)對(duì)象，在整個(gè)排序過程中，不會(huì)通過比較而相互交換。在 while循環(huán)之前和之中，至少要移動(dòng)記錄兩次，所以總的比較次數(shù)為 2(n1)。j++) if([j]L. key[j+1]){ L. key[j] ←→ L. key[j+1] change=True。 for(j=0。change。i1amp。 BOOL change。L){ //對(duì)順序表 L做起泡排序。 起泡排序 假設(shè)在排序過程中，記錄序列 R[1..n]的狀態(tài)為： 無序序列 R[1..ni+1] 有序序列 R[ni+2..n] 則 第 i趟起泡插入排序的基本思想 借助對(duì)無序序列中的記錄進(jìn)行“交換”的操作，將無序序列中關(guān)鍵字最大的記錄“交換”到 R[ni+1]的位置上。++k) ShellInsert(L,dlta[k])。L,int dlta[],int t){ //按增量序列 dlta[0..t1]對(duì)順序表 L作希爾排序 for(int k=0。 //記錄后移，查找插入位置 [j+dk]=[0]。 [0][j]。 j0 amp。 i++) if([idk] [i]){//需將 [i]插入有序子表 [0]=[i]。 for(i=dk+1。 2. 0號(hào)單元只是暫存單元，不是哨兵。L,int dk){ //對(duì)順序表 L做一趟希爾插入排序。假設(shè)將 n個(gè)記錄分成 d個(gè)子序列，則這 d個(gè)子序列分別為： { R[1]， R[1+d]， R[1+2d]， … ， R[1+kd] } { R[2]， R[2+d]， R[2+2d]， … ， R[2+kd] } … { R[d]， R[2d]， R[3d]， … ， R[kd]， R[(k+1)d] } 其中， d稱為增量， 它的值在排序過程中從大到小逐漸縮小（如： d=d/2），直至最后一趟排序減為 1。 “宏觀”調(diào)整 “跳躍式”的插入排序 。 } } // Arrange ★ 根據(jù)靜態(tài)鏈表 SL中各結(jié)點(diǎn)的指針值調(diào)整記錄位置，使得 SL中記錄按關(guān)鍵字非遞減有序順序排列 ★ 算法中使用了三個(gè)指針 : p指示第 i個(gè)記錄的當(dāng)前位置； i指示第 i個(gè)記錄應(yīng)在的位置； q指示第 i+1個(gè)記錄的當(dāng)前位置 ★ p指示第一個(gè)記錄的當(dāng)前位置 ★ SL[1..i1]中記錄已按關(guān)鍵字有
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1