快速排序--Java實作

算法特點：

某個記錄為界(該記錄稱為支點或樞軸)，将待排序列分成兩部分:

①一部分: 所有記錄的關鍵字大于等于支點記錄的關鍵字

②另一部分: 所有記錄的關鍵字小于支點記錄的關鍵字

算法描述：

1)任取待排序記錄序列中的某個記錄(例如取第一個記錄)作為基準(樞),按照該記錄的關鍵字大小,将整個記錄序列劃分為左右兩個子序列

2)左側子序列中所有記錄的關鍵字都小于或等于基準記錄的關鍵字

3)右側子序列中所有記錄的關鍵字都大于基準記錄的關鍵字

4)基準記錄則排在這兩個子序列中間(這也是該記錄最終應安放的位置)。

5)然後分别對這兩個子序列重複施行上述方法，直到所有的記錄都排在相應位置上為止。

基準記錄也稱為樞軸（或支點）記錄。取序列第一個記錄為樞軸記錄，其關鍵字為Pivotkey。指針low指向序列第一個記錄位置，指針high指向序列最後一個記錄位置。

// 劃分: 把數組a[p,r]劃分出左區和右區，傳回值為樞軸位置j。a[p,r] ==> a[p,j-1] a[j] a[j+1,r]
  // ---a[j]為樞軸，該元素已經排好
  private int partition(int a[], int p, int r) {
    int i = p;// 周遊左邊的遊标
    int j = r + 1;// 周遊右邊的遊标
    int x = a[p];
    while (true) {
      // 在左區中找一個比x大的數: a[i]
      while (a[++i] < x && i < r);// 經過該循環,a[i]就是左區中一個比x大的數 或者 遊标往右邊出界了
      // 在右區中找一個比x小的數: a[j]
      while (a[--j] > x);// 經過該循環,a[j]就是右區中一個比x小或相等的數
      // 如果出現i>=j,則跳循環
      if (i >= j) {
        break;
      }
      // 把a[i]和a[j]交換
      swap(a, i, j);
    }
    // 把樞軸(a[p])交換到j位置，傳回j
    swap(a, p, j);
    return j;
  }

  private void quickSort(int[] a, int p, int r) {
    if (p < r) {// 至少兩個數
      // 思路:把組數a[p,r]劃分成:a[p,q-1], a[q],a[q+1,r]
      int q = partition(a, p, r); // 中樞位置
      quickSort(a, p, q - 1);// 左區繼續
      quickSort(a, q + 1, r);// 右區繼續
    }
  }

  // @Test
  public void quickSort_test() {
    int a[] = { 21, 25, 49, 25, 16, 8, -1, 0, 23, 44 };
    print(a);
    quickSort(a, 0, a.length - 1);
    print(a);
  }      

測試結果如下:

21 25 49 25 16 8 -1 0 23 44 
-1 0 8 16 21 23 25 25 44 49      

算法分析：

1)快速排序是一個遞歸過程，快速排序的趟數取決于遞歸樹的高度。

2)如果每次劃分對一個記錄定位後, 該記錄的左側子序列與右側子序列的長度相同, 則下一步将是對兩個長度減半的子序列進行排序, 這是最理想的情況。

算法評價:

  1)時間複雜度：

       a.最好情況（每次總是選到中間值作樞軸）T(n)=O(nlogn)

       b.最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n²)

  2) 空間複雜度：需棧空間以實作遞歸

       最壞情況：S(n)=O(n)

       一般情況：S(n)=O(logn)

@@@@快速排序  優化

可以證明，快速排序算法在平均情況下的時間複雜性和最好情況下一樣，也是O(nlogn)，這在基于比較的算法類中算是快速的，快速排序也是以而得名。

快速排序算法的性能取決于劃分的對稱性。是以通過修改partition( )方法，可以設計出采用随機選擇政策的快速排序算法，進而使期望劃分更對稱，更低機率出現最壞情況。

是以，可在原劃分方法中加入如下代碼進行優化：

public static int partition(int a[], int p, int r){
    int rand = (int)(Math.random()*(r-p));
    swap(a,p,p+rand);  //把随機選中的元素換到首元素(樞軸)
    …//原算法代碼
}