快速排序

基本思想

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列。

左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值。

然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

挖坑法

一般把第一个元素作为坑位。L 和 R 分别从两端开始找对应的值填坑。

使用 java 代码实现为:

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int temp = arr[left];
        int i = left, j = right;
        while (i < j) {
            // 从右向左找，小于 temp 的数，找到则停止循环
            while (i < j && arr[j] > temp) {
                j--;
            }
            // 如果存在，则需要把右边的值换到左边来
            if (i < j) {
                arr[i] = arr[j];
                ++i;
            }
            // 从右向左找，大于等于 temp 的数，找到则停止循环
            while (i < j && arr[i] <= temp) {
                i++;
            }
            // 如果存在，则需要把左边的值换到右边来
            if (i <= j) {
                arr[j] = arr[i];
                j--;
            }
            // 最后把刚刚拿出来的那个值放入 当前指针处
            arr[i] = temp;
            // 继续下一轮，从左到 i-1 （因为left 到 i-1 仍然是无序的）
            quickSort(arr, left, i - 1);
            // 继续下一轮，从 i + 1 到 right （因为 i+1 到 right 仍然是无序的）
            quickSort(arr, i + 1, right);
        }
    }

算法总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定

详细的代码点击跳转