時(shí)間復(fù)雜度

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

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

基本示例：

原始數(shù)據(jù)：

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

第1步：選取第1個(gè)數(shù)據(jù)：3
第2步：將數(shù)據(jù)分成2部分，左邊≤3，右邊大于>3：

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

第3步：將各部分重復(fù)以上步驟，直到每部分只剩1個(gè)數(shù)據(jù)：

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

第4步：數(shù)據(jù)完成升序排列：

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

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

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

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

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

這里提出對(duì)快速排序的3點(diǎn)優(yōu)化思路：
對(duì)于小數(shù)組，可以采用插入排序，避免遞歸調(diào)用。例如，當(dāng)if(hi <= lo + M)時(shí)，就可以轉(zhuǎn)到插入排序。
采用子數(shù)組的一部分元素的中位數(shù)來(lái)切分?jǐn)?shù)組。這樣做得到的切分更好，但代價(jià)是需要計(jì)算中位數(shù)。
如果數(shù)組中含有大量的重復(fù)元素，可以采用三向切分。將數(shù)組切分為三部分，分別對(duì)應(yīng)于小于、等于和大于切分元素的數(shù)組元素。代碼實(shí)現(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);
  }
}

最新評(píng)論