第十关 | 天上的明月——快速排序和归并排序：1. 青铜挑战 —

1. 快速排序的基本过程

快速排序是将分治法运用到排序问题的典型例子

快速排序的基本思想是：通过一个标记 pivot 元素将 n 哥元素序列划分为左右两个子序列 left 和 right，其中left 中的元素都比 pivot 小，right 都比pivot 大，然后再次堆 left 和 right 各自执行快速排序，在将左右子序列排序好之后，整个序列就有序了。这里排序进行左右划分的时候一直划分到子序列只包含一个元素的情况，然后再递归返回。

我们以关键字序列{26,53,48,15,13,48,32,15}看一下一次划分的过程：

上面红框位置表示当前已经被赋值给了 pivot 或者其他位置，可以空出来放移动来的新元素了，我们可以看到 26 最终被放到属于自己的位置上，不会再变化，此时左侧都比15小，右侧都比 15 大，因此 26 的左右两侧可以分别再进行排序。

这一轮的过程是什么呢？就是数组增删改查的时候经常使用的双指针策略，我们在数组部分已经讲过了，这里不在赘述了。而这里的每一轮都是一个相向的双指针而已，没有任何神秘的东西。

根据上述原理，我没弄就可以写代码了，在实现过程中，为了方便实现，会对部分代码进行调整，详细代码如下：

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int pivot = arr[right];
        int i = left - 1;
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 将哨兵移动到为止 pivotIndex 上
        int pivotIndex = i + 1;
        int temp = arr[pivotIndex];
        arr[pivotIndex] = arr[right];
        arr[right] = temp;

        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
}

2. 第二种实现方式

至于实现，有很多中种方式，下面再给一种方式

public static void quickSort(int[] q, int l, int r) {
        if (l >= r) return;
        int x = q[l+r>>1];

        //Define positions of two pointers
        int i = l - 1;
        int j = r + 1;

        while (i < j) {
            do i++; while (q[i] < x);
            do j--; while (q[j] > x);
            //do Swap
            if (i < j) {
                int temp = q[i];
                q[i] = q[j];
                q[j] = temp;
            }
        }

        quickSort(q, l, j);
        quickSort(q, j + 1, r);
    }

复杂度分析

快速排序的时间复杂度计算比较麻烦一些。从原理来看，如果我们选择的pivot每次都正好在中间，效率是最高的，但是这是无法保证的，因此我们需要从最好、最坏和中间情况来分析

最坏情况就是如果每次选择的恰好都是low结点作为pivot，如果元素恰好都是逆序的，此时时间复杂度为O(n^2)
如果元素恰好都是有序的，则时间复杂度为O(n)
折中的情况是每次选择的都是中间结点，此时序列每次都是长度相等的序列，此时的时间复杂度为(O(nlogn))

第十关 | 天上的明月——快速排序和归并排序：1. 青铜挑战 —— 快速排序并不难-灵析社区

1. 快速排序的基本过程

2. 第二种实现方式

复杂度分析