疾速排序

疾速排序（Quicksort）是对冒泡排序算法的一种改良。

排序流程

疾速排序算法通过屡次比拟和替换来实现排序，其排序流程如下：

1. 首先设定一个分界值，通过该分界值将数组分成左右两局部。
2. 将大于或等于分界值的数据集中到数组左边，小于分界值的数据集中到数组的右边。此时，右边局部中各元素都小于或等于分界值，而左边局部中各元素都大于或等于分界值。
3. 而后，右边和左边的数据能够独立排序。对于左侧的数组数据，又能够取一个分界值，将该局部数据分成左右两局部，同样在右边搁置较小值，左边搁置较大值。右侧的数组数据也能够做相似解决。
4. 反复上述过程，能够看出，这是一个递归定义。通过递归将左侧局部排好序后，再递归排好右侧局部的程序。当左、右两个局部各数据排序实现后，整个数组的排序也就实现了。

劣势

综合能力较强的算法，在大部分状况下体现优异（对近乎排序好的数组排序时，不如插入排序）

疾速排序问题和优化

优化 1

• 问题：在对近乎排序好的数组进行排序时，效率很差。
• 起因：最后设计时，分界值设定为子数列的第一个元素，在一般数组中，这没什么问题，但对于一个曾经排序好的数组，这就导致排序过程中，简直所有的元素都被分到了左边，这样就不能体现出疾速排序【分治】的成果，这时疾速排序会被进化为 O(N2) 的算法。
• 优化：分界值用随机的办法选取。尽管最差的状况还是很慢，但最差状况产生的概率曾经升高到靠近于 0。

优化 2

• 问题：在对反复度很高的数组排序时，效率很低。
• 起因：有很多的元素和分界值元素相等时，也会导致一边长一边短的景象，算法也会进化。
• 优化：多加一个指针，把等于分界值的元素汇合在两头，这是两头局部相当于曾经排序好，下一步只对小于和大于分界值的元素进行排序即可。

演示动画

对惯例数组排序

查看慢速演示、代码、测试用例

对近乎排序好的数组排序

查看慢速演示、代码、测试用例

对反复度很高的数组排序

查看慢速演示、代码、测试用例