[理學(xué)]9排序技術(shù)(編輯修改稿)
2025-02-15 14:37 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 T1(P,m,i1)。 [對(duì)前面子表進(jìn)行快速排序 ] QKSORT1(P,i+1,n)。 [對(duì)后面子表進(jìn)行快速排序 ] } RETURN 快速排序的分析 快速排序也是一種互換類(lèi)排序方法，但它屬于 不穩(wěn)定 的排序。 設(shè)線性表的長(zhǎng)度為 n，則在最壞情況下，快速排序也需要 n(n1)/2次比較，但實(shí)際的排序效率要比冒泡排序高得多。 若系統(tǒng)不支持遞歸，則在快速排序過(guò)程中，隨著對(duì)各子表的不斷分割，劃分出的子表會(huì)越來(lái)越多，但一次只能對(duì)一個(gè)子表進(jìn)行再分割處理，因此需要將暫時(shí)不分割的子表保存起來(lái)，這可用一個(gè)棧來(lái)實(shí)現(xiàn)。 插入類(lèi)排序 ? 冒泡排序與快速排序本質(zhì)上都是通過(guò)數(shù)據(jù)元素的交換逐步消除線性表中的逆序 ，而插入類(lèi)的排序方法是將無(wú)序表中的元素按照一定的算法插入到有序的線性表中，直到原始無(wú)序表中的所有元素全部插入完畢為止。 ? 插入類(lèi)排序方法主要有： 簡(jiǎn)單插入排序 和 希爾排序 簡(jiǎn)單插入排序 ? 在線性表中，只包含第 1個(gè)元素的子表顯然可以是有序表，然后從線性表的第 2個(gè)元素開(kāi)始直到最后一個(gè)元素，逐次將其中的每一個(gè)元素插入到前面已經(jīng)有序的子表中。 ? 插入思想 ：首先將第 j個(gè)元素放到一個(gè)變量 T中，然后從有序子表的最后一個(gè)元素（即線性表中的第 j1個(gè)元素）開(kāi)始，往前逐個(gè)與 T進(jìn)行比較，將大于 T的元素均依次向后移動(dòng)一個(gè)位置，直到發(fā)現(xiàn)一個(gè)元素不大于 T為止，此時(shí)就將 T（即原線性表中的第 j個(gè)元素）插入到剛移出的空位置上，有序子表的長(zhǎng)度就變?yōu)?j了。 簡(jiǎn)單插入排序 6 8 9 7 6 5 4 6 2 1 1 6 8 2 9 7 6 5 4 3 1 1 6 8 2 4 9 7 6 5 3 1 1 6 8 2 4 9 7 6 5 3 1 1 9 8 7 6 6 5 4 3 2 1 1 6 9 8 7 6 5 4 3 2 1 1 6 8 2 4 9 6 7 5 3 1 1 6 8 2 4 9 6 1 7 5 3 1 6 8 2 4 9 6 1 3 7 5 1 6 8 2 4 9 6 1 3 7 5 1 6 8 2 4 9 6 1 3 7 1 5 其中紅底 黃字 為當(dāng)前插入的元素，白底 黑字 為 j指針的位置，即當(dāng)前要處理的元素 對(duì)于有相同關(guān)鍵字記錄的情況， 此算法是穩(wěn)定 的。 [算法 ]簡(jiǎn)單插入排序 輸入：待排序序列 P(1:n) 輸出：有序序列 P(1:n) PROCEDURE INSORT（ P， n） FOR j=2 TO n DO { T=P(j)； k=j1 WHILE (k0) and (P(k)T) DO { P(k+1)=P(k)。k=k1 } P(k+1)=T } RETURN 簡(jiǎn)單插入排序算法的 C語(yǔ)言描述： insort（ ET P[]， int n） { int j,k。 ET t。 for(j=1。jn。j++) { t=p[j]。k=j1。 while((k=0)amp。amp。(p[k]t)) { p[k+1]=p[k]。k=k1。} p[k+1]=t。 } return。 } 簡(jiǎn)單插入排序的分析 簡(jiǎn)單插入排序是一種插入類(lèi)排序方法，它屬于 穩(wěn)定 的排序。 在簡(jiǎn)單插入排序中，每一次比較后最多移掉一個(gè)逆序，因此，這種排序方法的效率與冒泡排序相同。在最壞情況下，簡(jiǎn)單插入排序需要 n(n1)/2次比較。 希爾排序 將整個(gè)無(wú)序序列分割成若干小子序列分別進(jìn)行簡(jiǎn)單插入排序。 子序列的分割方法如下： 將相隔某個(gè)增量 h的元素構(gòu)成一個(gè)子序列。在排序過(guò)程中，逐次減小這個(gè)增量，最后當(dāng) h減到 1時(shí)，進(jìn)行一次插入排序，排序就完成。 增量序列一般取 ht＝ n/2k(k＝ 1， 2， … ， [log2n])，其中 n為待排序序列的長(zhǎng)度。 在希爾排序過(guò)程中，雖然對(duì)于每一個(gè)子表 采用的仍然是插入排序，但是在子表中每 進(jìn)行一次比較就可能移去整個(gè)線性表中的 多個(gè)逆序，從而改善整個(gè)排序過(guò)程的性能 希爾排序示意圖 7 19 24 13 31 8 82 18 44 63 5 29 7 18 24 13 5 8 82 19 44 63 31 29 7 5 8 13 18 24 63 19 29 82 31 44 h=12/2=6
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1