快速排序

快速排序通過多次劃分操作實現(xiàn)排序。
以升序為例，每趟選擇當前所有子序列中的一個關鍵字（通常是第一個）作為樞紐，將子序列中比樞紐小的移到樞紐前面，比樞紐大的移到樞紐后面；當本趟所有子序列都被樞紐以上述規(guī)則劃分后會得到新的一組更短的子序列，它們成為下一趟劃分的初始序列集。

代碼：

#include <iostream>
using namespace std;

void print_array(int array[], int n) {
  for (int i = 0; i < n; ++i)
    cout<<array[i]<<" ";
  cout<<endl;
}

void QuickSort_array(int array[], int low, int high) {
  int i, j, temp, compare;
  i = low;
  j = high;
  compare = array[i];

  if (low < high) {
    while (i < j) {
      while (j > i && array[j] >= compare)
        --j;
    
      if (i < j){
        array[i] = array[j];
        ++i;
      }

      while(i < j && array[i] < compare)
        ++i;

      if (i < j) {
        array[j] = array[i];
        --j;
      }
    }

    array[i] = compare;

    QuickSort_array(array, low, i - 1);
    QuickSort_array(array, i + 1, high);
  }
}

void QuickSort(int array[], int n) {
  QuickSort_array(array, 0, n - 1);
}

int main() {
  int array[] = {1, 5, 3, 6, 2, 9, 4};
  print_array(array, 7);
  QuickSort(array, 7);
  print_array(array, 7);
  
  return 0;
}

復雜度分析：

1. 時間復雜度：
快速排序最好情況下的時間復雜度為O(nlog2^n)，待排序列越接近無序，本算法效率越高。 最壞情況下的時間復雜度為O(n2)，待排序列越接近有序，本算法效率越低。平均情況下時間復雜度為O(nlog2^n)?？焖倥判虻呐判蛱藬?shù)和初始序列有關。
說明：還有多個時間復雜度為O(nlog2^n)的排序，但僅本算法叫做快速排序，因為這些算法的基本操作執(zhí)行次數(shù)的多項式最高次項為XO(nlog2^n)（x為系數(shù)），快速排序的x最小，可見它在同級別的算法中是最好的，因此叫快速排序。*

2. 空間復雜度：
快速排序的空間復雜度是O(log2^n)?？焖倥判蚴沁f歸進行的，遞歸需要棧的輔助，因此它需要的輔助空間比前面幾類排序算法大。