原文地址：https://xeblog.cn/articles/17
快速排序基本思想
快速排序使用的是
分治思想，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
image
实现思路
- 设置一个基准值
k，一般取数组第一个元素，以此值分割数组； - 设置两个扫描员，分别为
i和j，i指向数组的最低位，j指向数组的最高位； - 首先由
j开始从数组最高位往数组最低位(j--)扫描比k小的值，扫描到后停止扫描，并将该值填入i所处的位置，然后再由i开始从数组最低位往数组最高位(i++)扫描比k大的值，扫描到后停止扫描，并将该值填入j所处的位置，j和i依次扫描，直至j与i的位置相互重合后，将k的值填入重合处，此时，数组左侧的值均小于k，右侧值均大于k，完成此次排序； - 分别对数组左右两边的值做如上操作后即可完成快速排序。
演示图
快速排序演示图.gif
代码实现
/**
* 快速排序
* @param array 待排序数组
* @param begin 起点索引
* @param end 终点索引
*/
private static void fastSort(int[] array, int begin, int end) {
// 递归终止条件，起点索引大于等于终点索引
if (begin >= end) {
return;
}
// 起点索引
int i = begin;
// 终点索引
int j = end;
// 基准值
int k = array[begin];
// 循环条件：起点索引小于终点索引
while (i < j) {
/*
这个循环是要扫描小于基准值的值，扫描到后退出循环,
循环条件：当前索引位的值大于等于基准值k(加等于号是防止相同数字交换而陷入死循环中),
且起点索引小于终点索引(防止数组下标出界)
*/
while (array[j] >= k && i < j) {
// 终点索引位从右至左逐个递减
j--;
}
if (i < j) {
// 将小于基准值的数移至左侧
array[i] = array[j];
}
/*
这个循环是要扫描大于基准值的值，扫描到后退出循环,
循环条件：当前索引位的值小于等于基准值k(加等于号是防止相同数字交换而陷入死循环中),
且起点索引小于终点索引(防止数组下标出界)
*/
while (array[i] <= k && i < j) {
// 起点索引位从左至右逐个递增
i++;
}
if (i < j) {
// 将大于基准值的数移至右侧
array[j] = array[i];
}
}
if (array[j] != k) {
// 基准值归位（数组的中间某个位置），归位后，基准值左侧都是小于基准值的数，右侧都是大于基准值的数
array[j] = k;
}
// 递归将基准值左侧的数排序
fastSort(array, begin, j - 1);
// 递归将基准值右侧的数排序
fastSort(array, j + 1, end);
}
测试排序
int[] array = {5, 6, 6, 4, 3, 5, 5};
System.out.println("排序前：" + Arrays.toString(array));
fastSort(array, 0, array.length - 1);
System.out.println("排序后：" + Arrays.toString(array));
输出结果
排序前：[5, 6, 6, 4, 3, 5, 5]
排序后：[3, 4, 5, 5, 5, 6, 6]
快速排序的时间复杂度
平均时间复杂度： O(nlogn) 。
最坏时间复杂度： O(n^2) ，这种情况发生在排序数组为正序或逆序的时候。
稳定性： 不稳定。
