Java实现快速排序算法

1. 介绍：

快速排序是由东尼霍尔所发展的一种排序算法，是对冒泡排序的一种改进。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。

2. 算法思想。

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此 法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

3. 实现思路。

① 以第一个关键字 K 1 为控制字，将 [K 1 ,K 2 ,…,K n ] 分成两个子区，使左区所有关键字小于等于 K 1 ，右区所有关键字大于 等于 K 1 ，最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。

② 把左区作为一个整体，用①的步骤进行处理，右区进行相同的处理。（即递归）

③ 重复第①、②步，直到左区处理完毕。

4. 三个指针:

第一个指针称为pivotkey指针（枢轴），第二个指针和第三个指针分别为left指针和right指针，分别指向最左边的值和最右边的值。left指针和right指针从两边同时向中间逼近，在逼近的过程中不停的与枢轴比较，将比枢轴小的元素移到低端，将比枢轴大的元素移到高端，枢轴选定后永远不变，最终在中间，前小后大。

5. 排序效果：

6. 适用场景：请看本文第一张图片

7. 实现代码：