367
排序算法(2)
255 406 134 592 657 745 683對該序列進行3次掃描後會發現，第3此掃描中最後一次交換的一對紀錄是L[4]和L[5]：
50 67 255 134 | 406 483 592 657 683 745 888
顯 然，第3次掃描(i=3)結束後L[5]以後的序列都已經排好序了，所以下一次掃描不必到達Last(L)-i=11-4=7，即第2行的for 循環j不必到達7，隻要到達4-1=3就可以了。按照這種思路，可以來回地進行掃描，即先從頭掃到尾，再從尾掃到頭。這樣就得到雙向冒泡排序算法：
procedure Bi-Directional_Bubble_Sort(var L:List);
var
low,up,t,i:position;
begin
1 low:=First(L);up:=Last(L);
2 while up>low do
begin
3 t:=low;
4 for i:=low to up-1 do
5 if L[i]>L[i+1] then
begin
6 swap(L[i],L[i+1]);
7 t:=i;
end;
8 up:=t;
9 for i:=up downto low+1 do
10 if L[i]< L[i-1] then
begin
11 swap(L[i],L[i-1]);
12 t:=i;
end;
13 low:=t;
end;
end;
算法利用兩個變量low和up記錄排序的區域L[low..up]，用變量t 記錄最近一次交換紀錄的位置，4-7行從前向後掃描，9-12行從後向前掃描，每次掃描以後利用t所記錄的最後一次交換記錄的位置，並不斷地縮小需要排序的區間，直到該區間隻剩下一個元素。
直觀上來看，雙向冒泡法先讓重的氣泡沉到底下，然後讓輕的氣泡浮上來，然後再讓較大氣泡沉下去，讓較輕氣泡浮上來，依次反複，直到排序結束。
雙向冒泡排序法的性能分析比較複雜，目前暫缺，那位朋友知道請告訴我。
冒泡排序法和雙向冒泡排序法是原地置換排序法，也是穩定排序法，如果算法Bubble_Sort中第3行的比較條件L[j]>L[j+1]改為L[j]>= L[j+1]，則不再是穩定排序法。
選擇排序 Selection Sort
選擇排序的基本思想是對待排序的記錄序列進行n-1遍的處理，第i遍處理是將L[i..n]中最小者與L[i]交換位置。這樣，經過i遍處理之後，前i個記錄的位置已經是正確的了。
選擇排序算法可實現如下。
procedure Selection_Sort(var L:List);
var
i,j,s:position;
begin
1 for i:=First(L) to Last(L)-1 do
begin
2 s:=i;
3 for j:=i+1 to Last(L) do
4 if L[j]< L[s] then
5 s:=j; //記錄L[i..n]中最小元素的位置
6 swap(L[i],L[s]); //交換L[i],L[s]
end;
end;
算法Selection_Sort中裏麵的一個for循環需要進行n-i次比較，所以整個算法需要
次比較。
顯而易見，算法Selection_Sort中共調用了n-1次swap過程。選擇排序法是一個原地置換排序法，也是穩定排序法。
插入排序 Insertion Sort
插 入排序的基本思想是，經過i-1遍處理後,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當位置，使得L[1..i]又 是排好序的序列。要達到這個目的，我們可以用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤ L[i]，則L[1..i]已排好序，第i遍處理就結束了；否則交換L[i]與L[i-1]的位置，繼續比較L[i-1]和L[i-2]，直到找到某一個 位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]時為止。圖1演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。
圖1 對4個元素進行插入排序
在 下麵的插入排序算法中，為了寫程序方便我們可以引入一個哨兵元素L[0]，它小於L[1..n]中任一記錄。所以，我們設元素的類型 ElementType中有一個常量-∞，它比可能出現的任何記錄都小。如果常量-∞不好事先確定，就必須在決定L[i]是否向前移動之前檢查當前位置是 否為1，若當前位置已經為1時就應結束第i遍的處理。另一個辦法是在第i遍處理開始時，就將L[i]放入L[0]中，這樣也可以保證在適當的時候結束第i 遍處理。下麵的算法中將對當前位置進行判斷。
插入排序算法如下：
procedure Selection_Sort(var L:List);
var
i,j:position;
v:ElementType;
begin
1 for i:=First(L)+1 to Last(L) do
begin
2 v:=L[i];
3 j:=i;
4 while (j<>First(L))and(L[j-1]< v) do //循環找到插入點
begin
5 L[j]:=L[j-1]; //移動元素
6 j:=j-1;
end;
7 L[j]:=v; //插入元素
end;
end;
下 麵考慮算法Insertion_Sort的複雜性。對於確定的i，內while循環的次數為O(i)，所以整個循環體內執行了∑O(i)=O(∑i)，其 中i從2到n。即比較次數為O(n2)。如果輸入序列是從大到小排列的，那麼內while循環次數為i-1次，所以整個循環體執行了∑(i-1)=n(n -1)/2次。由此可知，最壞情況下，Insertion_Sort要比較Ω(n2)次。
如果元素類型是一個很大的紀錄，則算法第5行要消耗大量的時間，因此有必要分析移動元素的次數。經過分析可知，平均情況下第5行要執行n(n-1)/4次，分析方法與冒泡排序的分析相同。
如果移動元素要消耗大量的時間，則可以用鏈表來實現線性表，這樣Insertion_Sort可以改寫如下(當然前一個算法同樣也適用於鏈表，隻不過沒下麵這個好，但是下麵算法這個比較複雜)：
注意：在下麵的算法中鏈表L增加了一個哨兵單元，其中的元素為-∞，即線性表L的第一個元素是L^.next^
procedure Selection_Sort_II(var L:PList);
var
i,j,tmp:Position;
begin
1 if L^.next=nil then exit; //如果鏈表L為空則直接退出
2 i:=L^.next; //i指向L的第一個元素，注意，L有一個哨兵元素，因此L^.next^才是L的第一個元素
3 while i^.next<>nil do
begin
4 tmp:=i^.next; //tmp指向L[i]的下一個位置
5 j:=L;
6 while (j<>i)and(tmp^.data>=j^.next^.data) do //從前向後找到tmp的位置，tmp應該插在j後麵
7 j:=j^.next;
8 if j<>i then //j=i說明不需要改變tmp的位置
begin
9 i^.next:=tmp^.next; //將tmp從i後麵摘除
10 tmp^.next:=j^.next; //在j後麵插入tmp
11 j^.next:=tmp;
end
12 else i:=i^.next; //否則i指向下一個元素
end;
end;
上述改進算法主要是利用鏈表刪除和插入元素方便的特性，對於數組則不適用。
插入排序法是一個原地置換排序法，也是一個穩定排序法。插入法雖然在最壞情況下複雜性為θ(n2)，但是對於小規模輸入來說，插入排序法是一個快速的原地置換排序法。許多複雜的排序法，在規模較小的情況下，都使用插入排序法來進行排序，比如快速排序和桶排序。
下麵是一個Java Applet製作的插入排序演示程序。
快速排序 Quick Sort
我們已經知道，在決策樹計算模型下，任何一個基於比較來確定兩個元素相對位置的排序算法需要Ω(nlogn)計算時間。如果我們能設計一個需要O(n1ogn)時間的排序算法，則在漸近的意義上，這個排序算法就是最優的。許多排序算法都是追求這個目標。
下麵介紹快速排序算法，它在平均情況下需要O(nlogn)時間。這個算法是由C.A.R.Hoare發明的。
算法的基本思想
快速排序的基本思想是基於分治策略的。對於輸入的子序列L[p..r]，如果規模足夠小則直接進行排序，否則分三步處理：
分解(Divide)：將輸入的序列L[p..r]劃分成兩個非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大於L[q+1..r]中任一元素的值。
遞歸求解(Conquer)：通過遞歸調用快速排序算法分別對L[p..q]和L[q+1..r]進行排序。
合並(Merge)：由於對分解出的兩個子序列的排序是就地進行的，所以在L[p..q]和L[q+1..r]都排好序後不需要執行任何計算L[p..r]就已排好序。
這個解決流程是符合分治法的基本步驟的。因此，快速排序法是分治法的經典應用實例之一。
算法的實現
算法Quick_Sort的實現：
注意：下麵的記號L[p..r]代表線性表L從位置p到位置r的元素的集合，但是L並不一定要用數組來實現，可以是用任何一種實現方法（比如說鏈表），這裏L[p..r]隻是一種記號。
procedure Quick_Sort(p,r:position;var L:List);
const
e=12;
var
q:position;
begin
1 if r-p<
最後更新：2017-04-02 00:06:15