一、排序思想

• 将数组中的一个数作为基准，比该数小的放到左边，比该数大的放到右边；
• 对左右两边再进行上述操作，即把左边当成一个新数组，找新的基准数，右边也一样；
• 直到不能再分割下去为止。

---

欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新，且简书上的付费文章在公众号上将免费。

---

案例：

假如待排序列如下：

初始状态

• 选定6为基准数，然后先从右边开始遍历，找到一个比基准数小的数，如下图：

找到比基准数小的5

• 右边找到比基准数小的时候，右边先停下，再从左边开始遍历，找到比基准数大的，如下图：

找到比基准数大的7

• 这个时候，左右两边都先停下，交换5和7的位置，结果如下：

第一次交换完成

• 然后继续从右边开始遍历，即从7的位置开始，找到比基准数小的数，如下：

找到比基准数小的4

• 找到后停下，再从左往右找比基准数大的，即从5开始找，结果如下：

找到比基准数大的9

• 这个时候，左右两边都停下，交换9和4的位置，结果如下：

第二次交换完成

• 再从右边开始找比基准数小的，找到了3，然后从左边找比基准数大的，左边指针移动到3的时候，左右指针重合了，如下：

指针重合

• 指针重合了，就将基准数和指针重合时所指的数交换位置，即交换6和3的位置，如图：

第一躺排序完成

• 此时6左边的都是比它小的，右边的都是比它大的。左边部分和右边部分看成是两个新的待排序列，两个序列都按照上述方式再进行排序，先排左边，再排右边。

二、代码实现

结合上面的案例，以及代码中的注释，可以说是思路十分清晰了，完整代码如下：

public static void sort(int[] arr, int left, int right) {
        if (arr == null || arr.length == 1) {
            return;
        }
        if (left > right) {
            return;
        }
        int base = arr[left]; // 最左边的数当作基准数
        int i = left; // 从左往右遍历的指针
        int j = right; // 从右往左遍历的指针
        int temp = 0; // 用来保存临时变量
        // 当左右指针不相遇的时候，就进行检索
        while(i != j) {
            // 先从右往左检索，直到检索到比基准数小的
            while (arr[j] >= base && i < j) {
                j--;
            }
            // 再从左往右检索，直到检索到比基准数大的
            while (arr[i] <= base && i < j) {
                i++;
            }
            // 跳出了上面两个while循环，表示右边找到了基准数小的，左边找到了比基准数大的，交换位置
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        // 跳出了最外层while循环，表示i和j相等，左右指针相遇了，交换基准数和此时指针指的元素
        arr[left] = arr[i];
        arr[i] = base;
        // 此时，第一躺排序完成，左边和右边看成新数组，重复上述步骤
        sort(arr, j+1, right); // 排右边
        sort(arr, left, i-1); // 排左边
}

快速排序之所以成为快速排序，那就是因为它快，经测试，排1千万数据大概是1秒的样子，还真是有两把刷子。