前言
快速排序相对于插入排序, 冒泡排序等排序算法稳定性不高. 但快速排序目前来说是基于比较的内部排序中被认为是最好的算法, 当 N 较大且元素为随机分布时, 快速排序平均速度最快. 在算法竞赛中处理较大且元素较随机的序列时, 用冒泡和插入排序很可能会超时, 比如 N=100000, 则时间会 > 3000ms, 这时就要用到快速排序.
快速排序时对冒泡排序的一种改进, 它的时间复杂度为 O(nlog?n), 最坏情况 O(n2), 实际操作时基本不可能达到最坏情况, 所以效率很高, 由 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 的放左边{5,4,6},4 的左右两部分均剩下一个元素, 且都到达了边界, 现在整个序列为{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).
来源: http://www.bubuko.com/infodetail-2823884.html