[数据结构与算法]快速排序 QuickSort

产生原因

排序方法千千万，算法不断在更新进步。
可以说，希尔排序是插入排序的升级版；堆排序是选择排序的升级版。
而快速排序，是冒泡排序的升级版。
我们知道，冒泡排序通过不断比较和移动交换来实现排序，每次至多移动相邻两个元素的位置，像泡泡一样，一点点往上升。
而快速排序，则是通过增大元素的移动距离，使较大的元素从前面直接移动到较后的位置，较小的值直接移动到较前面的位置。从而大大减小了时间复杂度。

原理

通过一趟排序将待排记录分割成独立的两部分，其中一部分元素值均比另一部分元素值小，则可分别堆这两部分进行排序（递归地），以达到整个序列有序的目的。

代码实现

#include <iostream>
#include <algorithm>
using namespace std;
void QuickSort(int a[], int n);
void QSort(int a[], int low, int high);
int Partition(int a[], int low, int high);

void QuickSort(int a[], int n) { QSort(a, 0, n - 1); }

void QSort(int a[], int low, int high) {
  int pivot;
  if (low < high) {
    pivot = Partition(a, low, high); //将数组一分为二，算出枢轴值pivot
    QSort(a, low, pivot - 1);        //对低子表递归排序
    QSort(a, pivot + 1, high);       //对高子表递归排序
  }
}
//交换顺序表a中子表的记录，是枢轴记录到位，并返回其所在位置
int Partition(int a[], int low, int high) {
  int pivotkey;
  pivotkey = a[low];   //用子表的第一个记录作枢轴记录
  while (low < high) { //从表的两端交替向中间扫描
    while (low < high && a[high] >= pivotkey)
      high--;
    swap(a[low], a[high]); //将比枢轴记录小的记录交换到低端
    while (low < high && a[low] <= pivotkey)
      low++;
    swap(a[low], a[high]); //将比枢轴记录大的记录交换到高端
  }
  return low; //返回枢轴所在的位置
}
int main() {
  int a[9] = {5, 1, 9, 3, 7, 4, 8, 6, 2};
  QuickSort(a, 9);
  for (int i = 0; i < 9; i++)
    cout << a[i] << " ";
  return 0;
}

细节解释

代码实现的核心是函数Partition（a,low,high)
它的作用是，选取一个合适的元素值，在我的栗子中是第一个元素5，把它放到一个合适的位置，是的5左边的元素都比它小，右边的值都比它大。这个5被称为枢轴(pivot)
(看到pivot的时候，懵了一下，赶紧学起英语哈哈哈)

之后再Qsort函数之中，就是不断对数组一份为二，递归地调用Qsort就完事。

举栗图解

拿我在代码里的栗子来说，对初始数组{5, 1, 9, 3, 7, 4, 8, 6, 2}来说

时间复杂度

O(N*logN)

缺陷

空间复杂度略大（递归造成栈空间的使用，有1说1，这点我没搞懂）
且，元素值的比较和交换是跳跃进行的，所以，快速排序是一种相对不稳定的排序方法。