資料結構排序演算法

一、概論
對於數據的處理工作，排序是其最基本的運算之一。在當今的計算機系統中，花費在排序上的時間佔系統CPU運行時間的很大比重。有資料表明，在一些商用計算機上，在排序上的CPU時間達到20％至60％。為了提高計算機的工作效率，人們提出了各種各樣的排序方法和算法。這些算法有力地發展、並充分地展示了算法設計的某些重要原則和高超技巧。因此，對於計算專業人員來說掌握排序算法是十分重要的。

二、排序算法簡介
本次課程中我們將介紹六種排序方法：插入排序，選擇排序，冒泡排序，希爾排序，快速排序及二路歸併。

<1>直接選擇排序(Selection Sort)：簡單的選擇排序，它的比較次數一定：n(n-1)/2。也因此無論在序列何種情況下，它都不會有優秀的表現（從上100K的正序和反序數據可以發現它耗時相差不多，相差的只是數據移動時間），可見對數據的有序性不敏感。它雖然比較次數多，但它的數據交換量卻很少。所以我們將發現它在一般情況下將快於冒泡排序。

<2>直接插入排序(Insertion Sort)：簡單的插入排序，每次比較後最多移掉一個逆序，因此與冒泡排序的效率相同。但它在速度上還是要高點，這是因為在冒泡排序下是進行值交換，而在插入排序下是值移動，所以直接插入排序將要優於冒泡排序。直接插入法也是一種對數據的有序性非常敏感的一種算法。在有序情況下只需要經過n-1次比較，在最壞情況下，將需要n(n-1)/2次比較。

<3>冒泡排序(Bubble Sort)：將相鄰的兩個數據元素按關鍵字進行比較，如果反序，則交換。對於一個待排序的數據元素序列，經一趟排序後最大值數據元素移到最大位置，其它值較大的數據元素向也最終位置移動，此過程為一次起泡。然後對下面的記錄重複上述過程直到過程中沒有交換為止，則已完成對記錄的排序。

<4>快速排序(Quick Sort)：是冒泡排序的改進，它通過一次交換能消除多個逆序，這樣可以減少逆序時所消耗的掃描和數據交換次數。在最優情況下，它的排序時間複雜度為Ｏ(nlog2n)。即每次劃分序列時，能均勻分成兩個子串。但最差情況下它的時間複雜度將是Ｏ(n^2)。即每次劃分子串時，一串為空，另一串為m-1（程序中的100K正序和逆序就正是這樣，如果程序中採用每次取序列中部數據作為劃分點，那將在正序和逆時達到最優）。從100K中正序的結果上看“快速排序”會比“冒泡排序”更慢，這主要是“冒泡排序”中採用了提前結束排序的方法。有的書上這解釋“快速排序”，在理論上講，如果每次能均勻劃分序列，它將是最快的排序算法，因此稱它作快速排序。雖然很難均勻劃分序列，但就平均性能而言，它仍是基於關鍵字比較的內部排序算法中速度最快者。

<5>希爾排序(Shell Sort)：增量的選擇將影響希爾排序的效率。但是無論怎樣選擇增量，最後一定要使增量為１，進行一次直接插入排序。但它相對於直接插入排序，由於在子表中每進行一次比較，就可能移去整個經性表中的多個逆序，從而改善了整個排序性能。希爾排序算是一種基於插入排序的算法，所以對數據有序敏感。

<6>歸併排序(Merge Sort)：歸併排序是一種非就地排序，將需要與待排序序列一樣多的輔助空間。在使用它對兩個己有序的序列歸併，將有無比的優勢。其時間複雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。對數據的有序性不敏感。若數據節點數據量大，那將不適合。但可改造成索引操作，效果將非常出色。

三、排序方法的選擇
因為不同的排序方法適應不同的應用環境和要求，所以選擇合適的排序方法很重要
(1)若n較小，可採用直接插入或直接選擇排序。
當記錄規模較小時，直接插入排序較好，它會比選擇更少的比較次數；
但當記錄規模較大時，因為直接選擇移動的記錄數少於直接插人，所以宜用選直接選擇排序。
這兩種都是穩定排序算法。

(2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜(這裡的隨機是指基準取值的隨機，原因見上的快速排序分析)；這裡快速排序算法將不穩定。

(3)若n較大，則應採用時間複雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸併排序序。
快速排序是目前基於比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分佈時，快速排序的平均時間最短；
堆排序雖不會出現快速排序可能出現的最壞情況。但它需要建堆的過程。這兩種排序都是不穩定的。
歸併排序是穩定的排序算法，但它有一定數量的數據移動​​，所以我們可能過與插入排序組合，先獲得一定長度的序列，然後再合併，在效率上將有所提高。

(4)特殊的箱排序、基數排序
它們都是一種穩定的排序算法，但有一定的局限性：
1>關鍵字可分解。
2>記錄的關鍵字位數較少，如果密集更好
3>如果是數字時，最好是無符號的，否則將增加相應的映射複雜度，可先將其正負分開排序。


四、AS中排列數組
1.申請一個長度為n的數組A：
var n:Number = 400;
var A:Array = new Array(n);
for (i=0; i < n; i++) {
 A[i] = i;
}
trace(A);

2.將長度為n的數組打亂次序：
for (i=0; i < n; i++) {
 var ran = int(Math.random()*n);
 var temp = A[i];
 A[i] = A[ran];
 A[ran] = temp;
}
trace(A)

3.將數組中的所有元素倒排序：
A.reverse();
trace(A)


 五、AS實現排序算法：

在執行各各排序算法之前，已經默認存在一個亂序的數組A[400]，默認代碼：

var n:Number = 400;
var A:Array = new Array(n);
for (i=0; i < n; i++) {
 A[i] = i;
}
for (i=0; i < n; i++) {
 var ran = int(Math.random()*n);
 var temp = A[i];
 A[i] = A[ran];
 A[ran] = temp;
}
 

1.直接插入排序

for (i = 0; i < n; i++) {
 var temp = A[i];
 for (j = i; j > 0 && temp < A[j - 1]; j--) {
  A[j] = A[j - 1];
  A[j - 1] = temp;
 }
}


2.直接選擇排序

for (i = 0; i < n - 1; i++) {
 var s:Number = i;
 for (j = s + 1; j < n; j++) {
  if (A[j] < A[s]) {
   s = j;
  }
 }
 var temp = A[i];
 A[i] = A[s];
 A[s] = temp;
}


3.冒泡排序

for (i = 0; i < n; i++) {
 for (j = i; j < n; j++) {
  if (A[i] > A[j]) {
   var temp = A[i];
   A[i] = A[j];
   A[j] = temp;
  }
 }
}


4.希爾排序

var increment = 6;
while (increment > 1) {
 increment = int(increment / 3 + 1);
 Shellpass(increment);
}
function Shellpass(c) {
 for (i = c; i < n; i++) {
  if (A[i] < A[i - c]) {
   var temp = A[i];
   j = i - c;
   do {
    A[j + c] = A[j];
    j = j - c;
   } while (j > 0 && temp < A[j]);
   A[j + c] = temp;
  }
 }
}


5.快速排序

function QuickSort(A, low, hig) {
 var i = low, j = hig;
 var mid = A[int((low + hig) / 2)];
 do {
  while (A[i] < mid) {
   i++;
  }
  while (A[j] > mid) {
   j--;
  }
  if (i <= j) {
   var temp = A[i];
   A[i] = A[j];
   A[j] = temp;
   i++;
   j--;
  }
 } while (i <= j);
 if (low < j) {
  arguments.callee(A,low,j);
 }
 if (i < hig) {
  arguments.callee(A,i,hig);
 }
}
QuickSort(A,0,n - 1);


6.二路歸併

var B:Array = new Array(A.length);
for (k = 1; k < n; k *= 2) {
 MergePass(k);
}
function MergePass(len) {
 for (i = 0; i + 2 * len < n; i = i + 2 * len) {
  MergeA(i,i + len - 1,i + 2 * len - 1);
 }
 if (i + len < n) {
  MergeA(i,i + len - 1,n - 1);
 }
}
function MergeA(low, m, hig) {
 var i = low, j = m + 1, z = 0;
 while (i <= m && j <= hig) {
  B[z++] = (A[i] <= A[j]) ? A[i++] : A[j++];
 }
 while (i <= m) {
  B[z++] = A[i++];
 }
 while (j <= hig) {
  B[z++] = A[j++];
 }
 for (z = 0, i = low; i <= hig; z++, i++) {
  A[i] = B[z];
 }
}