c語言數(shù)據(jù)結(jié)構(gòu)_第08講排序-在線瀏覽
2024-12-04 03:54本頁面
【正文】 4． 效率分析 空間效率：僅用了一個(gè)輔助單元 ， 輔助空間為 O（ 1） 。 最好情況下：即待排序列已按關(guān)鍵字有序 ， 每趟操作只需 1次比較 2次移動(dòng) 。 平均情況下：即第 j趟操作 ， 插入記錄大約同前面的 j/2個(gè)記錄進(jìn)行關(guān)鍵碼比較 ， 移動(dòng)記錄的次數(shù)為 j/2+2次 。 直接插入排序是穩(wěn)定的排序方法 。 返 回 922 二分插入排序 (Binary Insertong Sort) 1． 基本思想 直接插入算法雖然簡單 ， 但當(dāng)記錄數(shù)量 n很大時(shí) ， 則比較次數(shù)將大大增加 ， 對(duì)于有序表 （ 限于順序存儲(chǔ)結(jié)構(gòu) ） ， 為了減少關(guān)鍵字的比較次數(shù) ， 可采用二分插入排序 。 2． 【 例 92】 若有 8個(gè)記錄已排序 ， 插入新的關(guān)鍵字為 653。 二分插入排序輔助空間和直接插入相同 ， 為 O（ 1） 。 二分插入排序是穩(wěn)定的排序方法 。i=n。 // 將 r[I]暫存到 r[0] while(low=high) // 在 r[ low．． high ]中折半查找有序插入的位置 { m=(low+high)/2。 // 插入點(diǎn)在低半?yún)^(qū) else low=m+1。j=high+1。 // 記錄后移 r[high+1]=r[0]。 1． 基本思想 先將整個(gè)待排序記錄序列分割成若干子序列分別進(jìn)行直接插入排序 ， 待整個(gè)序列中的記錄 “ 基本有序時(shí) ” ， 再對(duì)全體記錄進(jìn)行一次直接插入排序 。 2． 【 例 93】 待排序列為： 40， 30， 60， 80， 70， 10， 20， 40， 50， 05。 3． 算法 void Shellsort() { gap=n/2。 i=n。 while (j0) { if (r[j]r[j+gap]) { x=r[j]。 r[j+gap]=x。 } // 對(duì)子序列作直接插入排序 else j=0。} // 每次減半 ,直至步長為一 } 4． 效率分析 希爾排序的分析是一個(gè)復(fù)雜的問題 ， 因?yàn)樗臅r(shí)間是所取 “ 增量 ” 序列的函數(shù) ， 這涉及一些數(shù)學(xué)上尚未解決的難題 。其輔助空間為 O（ 1） 。 返 回 93 快速排序法 931 冒泡排序 (Bubble Sort) 1． 基本思想 冒泡法也稱沉底法 ， 每相鄰兩個(gè)記錄關(guān)鍵字比大小 ,大的記錄往下沉 （ 也可以小的往上浮 ） 。 2． 【 例 94】 一個(gè)數(shù)組存有 83， 16， 9， 96， 27， 75， 42， 69， 34等9個(gè)值 ， 在開始時(shí) 83與 16互相比較 ， 因 8316,所以兩元素互換 ， 然后 839,83與 9互換 ， 接著 8396,所以不變 ， 然后互換的元素有 (96:27),(96:75),(96,42),(96,69),(96,34),所以在第一趟排序結(jié)束時(shí)找到最大的值 96， 把它放在最下面的位置 ，過程如表 91所示 。 3. 算法 void Bubblesort() { for(i=1。i++) { for(j=L。j) if (R[j].keyR[j1].key) // 小則交換 { R[0].key=R[j].key。 R[j1].key=R[0].key。 時(shí)間效率：總共要進(jìn)行 n1趟冒泡 ， 對(duì) j個(gè)記錄的表進(jìn)行一趟冒泡需要 j1次關(guān)鍵字的比較 。 最壞情況下：每次比較后均要進(jìn)行三次移動(dòng) ， 移動(dòng)次數(shù) = 時(shí)間復(fù)雜度為 : O（ n2） 冒泡排序是一種穩(wěn)定排序 。 通過一趟快速排序?qū)⒋判虻挠涗浗M分割成獨(dú)立的兩部分 ， 其中前一部分記錄的關(guān)鍵字均比樞軸記錄的關(guān)鍵字??；后一部分記錄的關(guān)鍵字均比樞軸記錄的關(guān)鍵字大 ， 樞軸記錄得到了它在整個(gè)序列中的最終位置并被存放好 ， 這個(gè)過程稱為一趟快速排序 。 顯然 ， 這是一個(gè)遞歸的過程 ， 不斷進(jìn)行下去 ， 直到每個(gè)待排序的子序列中只有一個(gè)記錄時(shí)為止 ， 整個(gè)排序過程結(jié)束 。 這里有個(gè)問題 ， 就是如何把一個(gè)記錄組分成兩個(gè)部分 ？通常是以序列中第一個(gè)記錄的關(guān)鍵字值作為樞軸記錄 。 3.【 例 95】 對(duì)數(shù)據(jù)序列： 70， 75， 69， 32， 88， 18， 16，58進(jìn)行快速排序 。 while(ij) // 從表的兩端交替地向中間掃描 { while(ijamp。R[j].key=) j 。 while (ijamp。R[i].key=) i+ +。 } R[i]=pivot。 } void QuickSort(int low,int high) // 遞歸形式的快排序 { int pivotpos,k。 //調(diào)用 Partition(low,high)函數(shù) QuickSort(low,pivotpos1)。 // 對(duì)高子表遞歸排序 } } 5． 效率分析 空間效率：快速排序是遞歸的 ， 每層遞歸調(diào)用時(shí)的指針和參數(shù)均要用棧來存放 ， 遞歸調(diào)用層次數(shù)與上述二叉樹的深度一致 。 時(shí)間效率：在 n個(gè)記錄的待排序列中 ， 一次劃分需要約n次關(guān)鍵碼比較 ， 時(shí)效為 O(n)， 若設(shè) T(n)為對(duì) n個(gè)記錄的待排序列進(jìn)行快速排序所需時(shí)間 。 快速排序是通常被認(rèn)為在同數(shù)量級(jí) （ O(nlog2n)） 的排序方法中平均性能最好的 。 返 回 選擇排序主要是從待排序列中選取一個(gè)關(guān)鍵字值最小的記錄 ， 把它與第一個(gè)記錄交換存儲(chǔ)位置 ， 使之成為有序 。 依次類推 ，直至完成整個(gè)排序 。 （ 2） 基本操作：從無序中選擇關(guān)鍵字值最小的記錄 ， 將其與無序區(qū)的第一個(gè)記錄交換 （ 實(shí)質(zhì)是添加到有序區(qū)尾部 ） 。 94 選擇排序 2.【 例 96】 對(duì)： 53 36 48 36 60 7 18 41 進(jìn)行簡單選擇排序 3． 算法 void Selectsort() { for (i=1。i++) { h=i。j=n。 if (h!=j) { R[0]=R[i]。R[h]=R[0]。 找第一個(gè)最小記錄需進(jìn)行 n1次比較 ， 找第二個(gè)最小記錄需要比較 n2次 ， 找第 i個(gè)最小記錄需要進(jìn)行 ni次比較 ，總的比較次數(shù)為： （ n1） +（ n2） +…… +（ n
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1