思路
有数组[26, -3, 14, -15, 0, 324, 98, 1, 22]
现对该数组进行排序，使用快速排序算法。
先来屡一下思路和步骤：
- 选出基准数；
- 小于基准数的，放在基准数左边，大于基准数的，放在基准数右边；
- 以基准数为分隔，左右两边的子数组继续进行排序（迭代）；
- 直至整个数组排序完成。
讲解
下面上图：
原数组如下：
image.png
先选出一个基准数，比如我们先选 0 为基准数，那么用数组中的数挨个去跟 0 做对比，小的放左边，大的放右边：
image.png
经过了第一次的调整，以 0 为基准，现在就分成了小于 0 和大于 0 两部分，然后，我们再分别对这两部分进行排序。
那么什么时候结束这个递归操作呢？分两种情况：
- 当分出来的子数组长度小于 2 时，也就是元素个数是0或1时，肯定就不需要排序了；
- 分数来的子数组长度等于 2 时，直接CAS就可以了。
那0左边就只有 -3 和 -15了，直接对比大小，把小的交换到前面就可以了：
image.png
然后呢，继续对 0 右边的元素进行一个快速排序，选出基准数比如 26 ：
image.png
经过又一次的调整，0 右边的子数组中，又以 26 为分界线分成了左右两块。那么 26 右边呢，324 和 98 直接对比交换位置就可以了。左边的14、1、22，就继续进行快速排序。
后面就不继续画了，讲到这里，后面发生了什么相信大家都明白了。
在生产应用中，一般这么小的数组是不会使用快排的。大的数组分隔子数组时，一般子数组分到15个左右元素的时候，就会使用其他排序方式（比如插入排序）去进行一个排序，而不会真的一直切到两个元素。
实现
原理说完了，那么应该怎么实现呢？这里使用一个双指针的方式，来对快速排序进行实现。
还是先画一下，便于理解：
首先选出一个基准数，并移植数组末尾。比如还按照刚才的，我们选出 0 ：
image.png
然后创建两个指针，第一个 P1 指针指向开始的位置减 1，也就是-1，另一个 P2 指针指向下标为0的位置：
image.png
然后把 P2 指向的元素跟基准数，也就是末尾的数进行对比，如果小于等于基准数，P1 后移一格，否则 P1 不移动；
在 P1 后移的基础上，如果 P1 下标小于 P2 指向的下标，则 P1、P2 指向的两个数值进行交换。
比如第一个数 26，不小于等于基准数0，那么P1不动，然后P2往后走：
image.png
发现 -3 小于基准数了，那么 P1 后移一格：
image.png
这时候对比 P1 跟 P2 的下标，P1 指向的是下标 0，而 P2 指向下标1，P1 < P2，那么，两个元素进行交换：
image.png
后面以此类推，中间就省略了。
直到最后P2移动到末尾基准数，基准数跟自己对比，小于等于自己，然后 P1 后移一格，肯定是小于 P2 的，然后交换，就把基准数放在了小于它和大于它的数中间：
image.png
image.png
这样就完成了第一次调整。
后面的步骤就都一样的，重复就可以了。
下面就上一下代码：
@Test
public void sortTest() {
int[] nums = new int[]{26, -3, 14, -15, 0, 324, 98, 1, 22};
fastSort(nums, 0, nums.length - 1);
System.out.println(Arrays.toString(nums));
}
private void fastSort(int[] nums, int start, int end) {
if (end - start < 1 || start < 0 || end >= nums.length || start > end) {
return;
}
if (end - start == 1) {
if (nums[start] > nums[end]) {
swap(nums, start, end);
}
return;
}
// 选出基准数，并将基准数移到数组末尾
int reference = (int) (start + Math.random() * (end - start + 1));
swap(nums, reference, end);
// 声明P1：divideIndex
int divideIndex = start - 1;
// 声明P2：i
for (int i = start; i <= end; i++) {
// 如果P2指向的元素小于基准数，P1后移。
// 如果P1小于i，交换位置。
if (nums[i] <= nums[end] && ++divideIndex < i) {
swap(nums, i, divideIndex);
}
}
// 递归左右子数组
if (divideIndex > start) {
fastSort(nums, start, divideIndex - 1);
}
if (divideIndex < end) {
fastSort(nums, divideIndex + 1, end);
}
}
private void swap(int[] numbers, int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
这样就实现了一个简单的快速排序，看一下运行结果：
image.png
排序也是OK的。
