前言
快速排序相对于插入排序、冒泡排序等排序算法稳定性不高。但快速排序目前来说是基于比较的内部排序中被认为是最好的算法，当N较大且元素为随机分布时，快速排序平均速度最快。在算法竞赛中处理较大且元素较随机的序列时，用冒泡和插入排序很可能会超时，比如N=100000，则时间会>3000ms,这时就要用到快速排序。
快速排序时对冒泡排序的一种改进，它的时间复杂度为O(nlog₂n)，最坏情况O(n²)，实际操作时基本不可能达到最坏情况，所以效率很高，由Hoare于1962年提出，可以笼统的理解为：一划分，二递归。由于划分有多种形式，所以快速排序也有多种形式，所以下面只单针对一种方法讲解。
划分
把序列的各个元素重排（将在下面讲到）后分成左右两部分，使左边部分的任意元素都小于等于右边部分的任意元素。
递归
把左右两部分分别排序划分（重复操作）直到有序停止递归。
过程
从序列中选出一个中间值作为分割点，将分割点的左右两边分割成独立的两部分，通过一趟排序使一遍的元素比分割点小，另一边的元素比分割点大，则继续对这两部分进行重复操作，直到整个序列有序。
整个过程可用递归操作实现，假设一个待排序的序列为{5，8，4，6，2，9，1，3，7}，我们要对此序列进行升序排列，首先任意取一个元素作为分割点，通常我们都取序列的中间值作为分割点，这里就取元素2为分割点，然后排列其余元素，使所有小于2的元素都放在2的左边，且所有大于2的元素都放在2的右边，元素2的下标不是固定的，会根据大于小于2的元素个数进行改变，第一趟排序的结果为{1，2，4，6，8，9，5，3，7}，分割成了小于2和大于2的两部分，然后对每部分进行重复操作，直到整个序列有序。
为了能让读者容易掌握快速排序，我把此序列一步一步演示，如果上一段读懂的话请忽略此段。小于2的那部分只有一个元素，已经为有序部分且到达了边界，不需要再进行排序。下面我们对大于2的部分{4，6，8，9，5，3，7}进行重复操作，首先任意取一个分割点，这里选9作为分隔点。通过一趟排序我们把小于9的放在左边，大于9的放在右边{4，6，8，7，5，3，9}，注意，9目前是最大元素，他的右边没有元素且到达了边界，所以只需要对小于9的部分{4，6，8，7，5，3}进行重复操作，同样选取分割点，这次选7好了，一趟排序把小于7的部分放左边，把大于7的部分放右边{4，6，3，5，7，8}，7的右边部分到边界了，下面对左边部分{4，6，3，5}进行重复操作，选中间值3做分割点，一趟排序，大于3的放右边，小于3的放左边{3，6，4，5}，分割点左边部分到边界了，下面对右边部分{6，4，5}进行重复操作，选中间值4，一趟排序，大于4的放右边，小于4的放左边{4，6，5}的左边到达了边界，且右边只剩两个元素{6，5}，重复操作，分割点设6，5小于6所以交换为{5，6}，现在整个序列为{1，2，3，4，5，6，7，8，9}，已为有序序列。
具体做法
一趟排序的具体做法是：设置两个指针（下标）i 和 j ，初值分别是这个部分最左边元素的下标和最右边元素的下标（及第一位与最后一位的下标），设置分割点mid，首先从 j 下标所指的位置向前搜索找到第一个小于mid的记录，然后从 i 所指位置向后搜索，找到第一个大于mid的元素，将找到的这两个元素交换，重复这两个步骤直到 i > j 停止。通过这趟排序，所有小于mid的元素都会被交换到左边，大于mid的元素都会被交换到右边。
C++代码演示：
#include <iostream>
using namespace std;
int n, a[100001];
void qsort(int left, int right) { //通过递归实现快速排序
int i, j, mid, p;
i = left;
j = right;
mid = a[(left + right) / 2];
do {
while (a[i] < mid)i++;
while (a[j] > mid)j--;
if (i <= j) {
p = a[i]; a[i] = a[j]; a[j] = p;
i++; j--;
}
} while (i <= j);
if (j > left) qsort(left, j);
if (i < right) qsort(i, right);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
qsort(1, n);
for (int i = 1; i <= n; i++) {
cout << a[i] << ' ';
}
return 0;
}
后言
快速排序虽然不是稳定的排序方法，但是从时间上看，快速排序的平均性能优于各种算法，被认为是目前最好的一种内部排序。它需要一个栈的空间实现递归操作，栈的最大深度为log(n+1)。
- 还没有人评论，欢迎说说您的想法！
客服
