有意思的排序算法-快速排序

　　快速排序對于含有n個元素的數組，最壞情況的運作時間為O(n2)，雖然這個最壞情況的運作時間比較差，但是快速排序通常是用于排序的最佳的實用選擇，這是因為其平均性能相當好，而且我們可以采用随機化的快速排序算法，來減少出現最壞情況的機會，其期望運作時間為O(nlgn)，而且該記号中含的常數因子很小。

　　像合并排序算法一樣，快速排序也是基于分治法進行排序的。其排序過程分為三個步驟：

　　分解：數組A[p..r]被劃分為兩個（可能空）子數組A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每個元素都小于等于A(q)，而且小于等于A[q+1..r]中的元素。下标q也在這個劃分過程中計算。

　　解決：通過遞歸調用快速排序，對子數組A[p..q-1]和A[q+1..r]排序。

　　合并：因為兩個子數組是就地排序的，将它們合并不需要操作：整個數組A[p..r]已排序。

　　Java實作為：

1 import java.util.Random;
 2 
 3 public class QuickSort implements SortAlgorithm {
 4 
 5     private Random rand = null;
 6 
 7     public QuickSort() {
 8         rand = new Random();
 9     }
10 
11     @Override
12     public void sort(int[] A) {
13         randomizedQuickSort(A, 1, A.length, true);
14     }
15 
16     @Override
17     public void sort(int[] A, boolean isInc) {
18         randomizedQuickSort(A, 1, A.length, isInc);
19     }
20     
21     /**
22      * 随機化的快速排序
23      * @param A 要排序的int數組
24      * @param p 起始位置
25      * @param r 終止位置
26      * @param isInc 是否升序，true為升序，false為降序
27      */
28     private void randomizedQuickSort(int[] A, int p, int r, boolean isInc) {
29         if (p < r) {
30             int q = randomizedPartition(A, p, r, isInc);
31             randomizedQuickSort(A, p, q - 1, isInc);
32             randomizedQuickSort(A, q + 1, r, isInc);
33         }
34     }
35     
36     /**
37      * 随機化的對數組的劃分
38      * @param A 要劃分的int數組
39      * @param p 起始位置
40      * @param r 終止位置
41      * @param isInc 是否升序，true為升序，false為降序
42      * @return 劃分數組的下标
43      */
44     private int randomizedPartition(int[] A, int p, int r, boolean isInc) {
45         int i = rand.nextInt(r - p);
46         exchange(A, r, i + p);
47         return partition(A, p, r, isInc);
48     }
49     
50     /**
51      * 對數組進行劃分
52      * @param A 要劃分的int數組
53      * @param p 起始位置
54      * @param r 終止位置
55      * @param isInc 是否升序，true為升序，false為降序
56      * @return 劃分數組的下标
57      */
58     private int partition(int[] A, int p, int r, boolean isInc) {
59         int x = A[r - 1];
60         int i = p - 1;
61         for (int j = p; j <= r - 1; j++) {
62             if (isInc ? A[j - 1] <= x : A[j - 1] >= x) {
63                 i++;
64                 exchange(A, i, j);
65             }
66         }
67         exchange(A, i + 1, r);
68         return i + 1;
69     }
70 
71     private void exchange(int[] A, int i, int j) {
72         int temp = A[i - 1];
73         A[i - 1] = A[j - 1];
74         A[j - 1] = temp;
75     }
76 }      

　　到此為止，寫完了比較排序的幾種最常用的排序算法，不對的地方，請大家批評指正。