排序算法(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

3 t:=low;

4 for i:=low to up-1 do

5 if l[i]>l[i+1] then

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

11 swap(l[i],l[i-1]);

12 t:=i;

13 low:=t;

算法利用兩個變量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);

i,j,s:position;

1 for i:=first(l) to last(l)-1 do

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]

算法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 遍處理。下面的算法中将對目前位置進行判斷。

插入排序算法如下：

i,j:position;

v:elementtype;

1 for i:=first(l)+1 to last(l) do

2 v:=l[i];

3 j:=i;

4 while (j<>first(l))and(l[j-1]< v) do //循環找到插入點

5 l[j]:=l[j-1]; //移動元素

6 j:=j-1;

7 l[j]:=v; //插入元素

下 面考慮算法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);

i,j,tmp:position;

1 if l^.next=nil then exit; //如果連結清單l為空則直接退出

2 i:=l^.next; //i指向l的第一個元素，注意，l有一個哨兵元素，是以l^.next^才是l的第一個元素

3 while i^.next<>nil do

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的位置

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指向下一個元素

上述改進算法主要是利用連結清單删除和插入元素友善的特性，對于數組則不适用。

插入排序法是一個原地置換排序法，也是一個穩定排序法。插入法雖然在最壞情況下複雜性為θ(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;

q:position;

1 if r-p<