快速排序

快速排序通过多次划分操作实现排序。
以升序为例，每趟选择当前所有子序列中的一个关键字（通常是第一个）作为枢纽，将子序列中比枢纽小的移到枢纽前面，比枢纽大的移到枢纽后面；当本趟所有子序列都被枢纽以上述规则划分后会得到新的一组更短的子序列，它们成为下一趟划分的初始序列集。

代码：

#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)。快速排序的排序趟数和初始序列有关。
说明：还有多个时间复杂度为O(nlog2^n)的排序，但仅本算法叫做快速排序，因为这些算法的基本操作执行次数的多项式最高次项为XO(nlog2^n)（x为系数），快速排序的x最小，可见它在同级别的算法中是最好的，因此叫快速排序。*

2. 空间复杂度：
快速排序的空间复杂度是O(log2^n)。快速排序是递归进行的，递归需要栈的辅助，因此它需要的辅助空间比前面几类排序算法大。