Java編程中快速排序算法的實現(xiàn)及相關算法優(yōu)化

更新時間：2016年05月04日 16:06:57 作者：然則

這篇文章主要介紹了Java編程中快速排序算法的實現(xiàn)及相關算法優(yōu)化,快速排序算法的最差時間復雜度為(n^2),最優(yōu)時間復雜度為(n\log n),存在優(yōu)化的空間,需要的朋友可以參考下

時間復雜度

平均情況：O(nlgn)
最壞情況：O(n*n)，發(fā)生在當數據已經是排序狀態(tài)時
快排算法的基本原理

1、從數據中選取一個值a[i]作為參考
2、以a[i] 為參考，將數據分成2部分：P1、P2，P1中的數據全部≤a[i]，P2中的數據全部＞a[i]，數據變?yōu)椋鸓1｝｛a[i]｝｛P2｝｝
3、將P1、P2重復上述步驟，直到各部分中只剩1個數據
4、數據完成升序排列

基本示例：

原始數據：

  ｛3，9，8，5，2，1，6｝

第1步：選取第1個數據：3
第2步：將數據分成2部分，左邊≤3，右邊大于>3：

  ｛2，1｝ ｛3｝ ｛9，8，5，6｝

第3步：將各部分重復以上步驟，直到每部分只剩1個數據：

  ｛2，1｝ => ｛1｝ ｛2｝
  ｛9，8，5，6｝ => ｛8，5，6｝ ｛9｝=> ｛5，6｝ ｛8｝ ｛9｝=> ｛5｝ ｛6｝ ｛8｝ ｛9｝

第4步：數據完成升序排列：

  ｛1｝ ｛2｝ ｛3｝ ｛5｝ ｛6｝ ｛8｝ ｛9｝

程序中數據通常保存在數組中，以int類型的數組為例，可以將上面的步驟寫成一個quickSort函數原型：

quickSort(int begin, int end) { 
//begin為數組的第一個數據的索引值，end為數組的最后一個數據的索引值+1
  //如果只有1個數據或0個數據，則程序返回
  if( begin == end || begin == (end-1) ) return; 
  int p = in[begin];//p為選擇的參考數據，選擇第一個數據
  int a = begin +1; //a作為2部分數據分界線的索引值
  int b = a;//b為待比較的數據的索引值
  for( ; b < end; b++) {//將數組中的各個數據依次與參考數據進行比較
    if( in[b] < p) { //如果該數據<參考數據則將其移動到左邊
      if(a == b){a++; continue;} //如果該數據已經在左邊則不動
      int temp = in[a];//將數據移動到左邊
      in[a] = in[b];
      in[b] = temp;
      a++;//將分界線右移
    }
  }
  in[begin] = in[a-1];//講參考值移動到2組數據中間
  in[a-1] = p;
  if( a-1 > begin){ // 如果左邊有數據則將其重復上述步驟
    quickSort(begin, a);
  } 
  if( end-1 > a ) {// 如果右邊有數據則將其重復上述步驟
    quickSort(a, end);
  } 
  return; // 如果無數據返回
}

算法優(yōu)化
上面這個快速排序算法可以說是最基本的快速排序，因為它并沒有考慮任何輸入數據。但是，我們很容易發(fā)現(xiàn)這個算法的缺陷：這就是在我們輸入數據基本有序甚至完全有序的時候，這算法退化為冒泡排序，不再是O(n㏒n)，而是O(n^2)了。
究其根源，在于我們的代碼實現(xiàn)中，每次只從數組第一個開始取。如果我們采用“三者取中”，即arr[low],arr[high],arr[（low+high）/2]三者的中值作為樞軸記錄，則可以大大提高快速排序在最壞情況下的性能。但是，我們仍然無法將它在數組有序情形下的性能提高到O(n)。還有一些方法可以不同程度地提高快速排序在最壞情況下的時間性能。

此外，快速排序需要一個遞歸棧，通常情況下這個棧不會很深，為log(n)級別。但是，如果每次劃分的兩個數組長度嚴重失衡，則為最壞情況，棧的深度將增加到O(n)。此時，由棧空間帶來的空間復雜度不可忽略。如果加上額外變量的開銷，這里甚至可能達到恐怖的O(n^2)空間復雜度。所以，快速排序的最差空間復雜度不是一個定值，甚至可能不在一個級別。
為了解決這個問題，我們可以在每次劃分后比較兩端的長度，并先對短的序列進行排序（目的是先結束這些棧以釋放空間），可以將最大深度降回到O(㏒n)級別。

這里提出對快速排序的3點優(yōu)化思路：
對于小數組，可以采用插入排序，避免遞歸調用。例如，當if(hi <= lo + M)時，就可以轉到插入排序。
采用子數組的一部分元素的中位數來切分數組。這樣做得到的切分更好，但代價是需要計算中位數。
如果數組中含有大量的重復元素，可以采用三向切分。將數組切分為三部分，分別對應于小于、等于和大于切分元素的數組元素。代碼實現(xiàn)如下：

  private static void sort1(int[] a, int lo, int hi) {
  if (hi <= lo)
    return;
  int lt = lo, i = lo + 1, gt = hi;
  int v = a[lo];
  while (i <= gt) {
    if (a[i] < v) {
      swap(a, lt++, i++);
    } else if (a[i] > v) {
      swap(a, i, gt--);
    } else {
      i++;
    }
    sort(a, lo, lt - 1);
    sort(a, gt + 1, hi);
  }
}

您可能感興趣的文章: