排序演算法總結

熱2已有 2573 次閱讀 2009-09-01 13:23

填問卷贏好書華章讀者調研活動結果公布

一、選擇排序

1. 基本思想：

每一趟從待排序的資料元素中選出最小（或最大）的乙個元素，順序放在已排好序的數列的最後，直到全部待排序的資料元素排完。

2. 排序過程：

【示例】：

初始關鍵字 [49 38 65 97 76 13 27 49]

第一趟排序後 13 ［38 65 97 76 49 27 49]

第二趟排序後 13 27 ［65 97 76 49 38 49]

第三趟排序後 13 27 38 [97 76 49 65 49]

第四趟排序後 13 27 38 49 [49 97 65 76]

第五趟排序後 13 27 38 49 49 [97 97 76]

第六趟排序後 13 27 38 49 49 76 [76 97]

第七趟排序後 13 27 38 49 49 76 76 [ 97]

最後排序結果 13 27 38 49 49 76 76 97

3.void selectionsort(type* arr,long len)

}選擇排序法的第一層迴圈從起始元素開始選到倒數第二個元素,主要是在每次進入的第二層迴圈之前,將外層迴圈的下標賦值給臨時變數,接下來的第二層迴圈中,如果發現有比這個最小位置處的元素更小的元素,則將那個更小的元素的下標賦給臨時變數,最後,在二層迴圈退出後,如果臨時變數改變,則說明,有比當前外層迴圈位置更小的元素,需要將這兩個元素交換.

二.直接插入排序

插入排序（insertion sort）的基本思想是：每次將乙個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子檔案中的適當位置，直到全部記錄插入完成為止。

直接插入排序

直接插入排序（straight insertion sort）：將乙個記錄插入到排好序的有序表中，從而得到乙個新的、記錄數增1的有序表。

直接插入排序演算法

哨兵（監視哨）有兩個作用：一是作為臨變數存放r[i]（當前要進行比較的關鍵字）的副本；二是在查詢迴圈中用來監視下標變數j是否越界。

當檔案的初始狀態不同時，直接插入排序所耗費的時間是有很大差異的。最好情況是檔案初態為正序，此時演算法的時間複雜度為o(n)，最壞情況是檔案初態為反序，相應的時間複雜度為o(n2)，演算法的平均時間複雜度是o(n2)。演算法的輔助空間複雜度是o(1)，是乙個就地排序。

直接插入排序是穩定的排序方法。

三. 氣泡排序

[演算法思想]：將被排序的記錄陣列r[1..n]垂直排列，每個記錄r[i]看作是重量為r[i].

key的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃瞄陣列r：凡掃瞄到違反本原則的輕氣泡，就使其向上"飄浮"。

如此反覆進行，直到最後任何兩個氣泡都是輕者在上，重者在下為止。

[演算法]：

void bubblesort(seqlist r) //bubblesort

[分析]：起泡排序的結束條件為：最後一趟沒有進行「交換」。

從起泡排序的過程可見，起泡排序是乙個增加有序序列長度的過程，也是乙個縮小無序序列長度的過程，每經過一趟起泡，無序序列的長度只縮小1。 [演算法思想]：將被排序的記錄陣列r[1..

n]垂直排列，每個記錄r[i]看作是重量為r[i].key的氣泡。根據輕氣泡不能在重氣泡之下的原則，從下往上掃瞄陣列r：

凡掃瞄到違反本原則的輕氣泡，就使其向上"飄浮"。如此反覆進行，直到最後任何兩個氣泡都是輕者在上，重者在下為止。

[演算法]：

void bubblesort(seqlist r) //bubblesort

[分析]：起泡排序的結束條件為：最後一趟沒有進行「交換」。

從起泡排序的過程可見，起泡排序是乙個增加有序序列長度的過程，也是乙個縮小無序序列長度的過程，每經過一趟起泡，無序序列的長度只縮小1。

四. 希爾排序

基本思想：

先取乙個小於n的整數d1作為第乙個增量，把檔案的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同乙個組中。先在各組內進行直接插人排序；然後，取第二個增量d2 　該方法實質上是一種分組插入方法。

給定例項的shell排序的排序過程

假設待排序檔案有10個記錄，其關鍵字分別是：

49，38，65，97，76，13，27，49，55，04。

增量序列的取值依次為：

5，3，1

shell排序的演算法實現

1．不設監視哨的演算法描述

void shellpass(seqlist r，int d)

//shellpass

void shellsort(seqlist r)

while(increment>1)

} //shellsort

注意：　當增量d=1時，shellpass和insertsort基本一致，只是由於沒有哨兵而在內迴圈中增加了乙個迴圈判定條件"j>0"，以防下標越界。

2．設監視哨的shell排序演算法

演算法分析

1．增量序列的選擇

shell排序的執行時間依賴於增量序列。

好的增量序列的共同特徵：

① 最後乙個增量必須為1；

② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。

有人通過大量的實驗，給出了目前較好的結果：當n較大時，比較和移動的次數約在nl.25到1.6n1.25之間。

2．shell排序的時間效能優於直接插入排序

希爾排序的時間效能優於直接插入排序的原因：

①當檔案初態基本有序時直接插入排序所需的比較和移動次數均較少。

排序演算法總結

排序演算法總結

排序演算法總結

排序演算法總結

相關推薦