快速排序算法详解

1.2实现

private static int partition(int[] array, int left, int right) {
    int i = left;
    int j = right;
    int pivot = array[left];
    while (i < j) {
        while (i < j && array[j] >= pivot) {
            j--;
        }
        while (i < j && array[i] <= pivot) {
            i++;
        }
        swap(array, i, j);
    }
    swap(array, i, left);
    return i;
}

1.2.1>=

遇到与基准值相等大小的元素时 直接作为可行的 路过掉的，因为与基准值相等大小的元素 到最后排序在 此作为基准元素左右两边 都是可以的，所以此时排放在基准的左右两路 最后成两部分 都是可以的

1.2.2先右再左

基准为路的相遇点，要设置在属于左路的 因为最后基准交换 放到相遇点，基准值放到相遇点进去排序，相遇点的值 会交换放到第一个位置 即基准值的左边 需要是左路的部分，所以每轮的铺路都是 先进行右路的铺完到左边停 再进行左路的铺

2.双路双向覆盖 (修路) 铺（挖坑法）

2.1原理

要去排的元素基准值 在待排序区域内任意取好 并挖成坑，从左右端先左或右都行 往同向内 互相埋坑时 又挖坑地 推坑，推坑时始终是 一端路停在坑位 等着另一端路 往内铺路 挖到坑填上，所以左右路两端相遇时 一定遇在坑位，此位置就是 基准元素大小排序的位置 排好

2.2实现

private static int partition(int[] array, int left, int right) {
    int i = left;
    int j = right;
    int pivot = array[left];
    while (i < j) {
        while (i < j && array[j] >= pivot) {
            j--;
        }
        array[i] = array[j];
        while (i < j && array[i] <= pivot) {
            i++;
        }
        array[j] = array[i];
    }
    array[i] = pivot;
    return i;
}

3.双路单向交换铺（前后指针法）

3.1原理

要去排序的基准元素 在待排序区间 任意选好后，定义 prev 与 cur 两前后指针，在排序区间的一端开始 同向往另一端 通过前后交换 动态维护 prev 及之前的区间为小路、cur 及到 prev 之前的区间为大路，这样当 cur 遍历完排序区间时，数组就被分好了 小路与大路两部分，再将基准元素交换放到 prev 指针位置处，一个基准元素 就在待排序区间排好了

3.2实现

private static int partition(int[] array, int left, int right) {
    int prev = left;
    int cur = left + 1;
    while (cur <= right) {
        if (array[cur] < array[left] && array[++prev] != array[cur]) {
            swap(array, cur, prev);
        }
        cur++;
    }
    swap(array, prev, left);
    return prev;
}

4.三指针法

三、快速排序的复杂度

基准排序的特点

• 元素的直接位置排好 也排好着 其它元素的间接位置排好、减少着 其它元素剩下的 需要排的量
• 每一个节点的出现，就是其完成 它所在待排区域的基准排位 标志

1.时间复杂度

递归的调用语句 算的是 调用里面执行的内容 (调用本身不算)，每次调用里面的 常量次数执行语句不算 (因为乘常量 常量可忽略的)，只算里面的 找调基准排的 非常量级的时间复杂度，算时间复杂度时就 一层层地算 每层里面所有递归调用的 时间和：

1.1完全顺序逆序

1.1.1结构影响

当元素完全顺序或完全逆序 排时，其呈现的二叉树结构为单分支的二叉树：

• 一层层下来 **每层里面只划分出了一个的递归调用，**它这样排 能间接排出 而不用再去排的元素 只有一个(即只有一个叶子节点的元素)

1.1.2时间

每一层都是 n 次遍历 只能排好 1 个元素，对应共有 n 层

最开始第一层时间是 n-1，再下层一个元素已经排好了 时间是 n-2，到最后一层时 最后一个元素被间接排好 递归调用函数里面是直接 return 的，所以一共有 n 层，n-1 层要去算时间，从上往下 每层的时间从n-1 减到 1 的等差数列和，最后大 O 算成的时间复杂度为O(n^2)，实际上的时间会比 n^2 少

1.2完全二叉树序

1.2.1结构影响

当数组呈完全二叉树排列时：

• 每个节点排时都有 间接最大地去排着其它元素的位置，一层层下来 在每层里剩下区域 会越来越多地被划分着去排的，在一层中 将会去完成更多的在区间中的排序，到最后一层能间接排出 不用去排的元素会有很多
• 一个区间里，元素去基准排划分的次数 固定是元素个数少 1 的，划分成更多的 区间里去排，排序本身就会减这么区间多个的次数 完成

1.2.2时间

每一层都是 n 次遍历 对应排好 2 的 n 层次方个 元素，对应共有 log(n) 层

因为每一层往下 已排好的元素越来越多，每一层中 所有基准区间总的去排的次数 会越来越少，到最后一层里 会有许多通过间接排就排好的元素 不需要去排的，但大 O 算时的最后结果是 偏大地算为 每层所有找基准排的时间为固定的 n，然后树的高度为 log(n)，时间复杂度为O(n*log(n))，实际上的时间会比它少很多（根节点高度视为 0 的）

2.空间复杂度

因为递归调用的栈空间是动态复用的，所以空间复杂度为递归树的最大高度下算每层开辟的空间，因为这里每层递归函数里面开辟的空间是常量级的，所以大 O 算排序递归的空间复杂度就为递归调用栈的深度即二叉树的高度：

• 当数组完全顺序或逆序时，二叉树的高度为 n-1，空间复杂度为O(n)
• 当数组呈完全二叉树排列时，二叉树的高度为 log(n)，空间复杂度为O(log(n))

3.优化

二叉树每层分支得越多装得越满：

• 每个元素节点都会去间接排其它元素的两部分位置、更多的在区间的排序减的次数会更多、以层单位去算时间的层的量会更少、从上往下已排出剩下的待排序元素会越来越少很多、最后通过间接排出位置不用去排的元素就会更多，时间复杂度会更低
• 二叉树的高度更小下，空间复杂度也会更低

3.1三数取中

在每个待排序区间虽然是可以任意取元素作基准，但我们尽量取大小排在中间的元素使生成的树分支更多树更矮时间复杂度与空间复杂度都更低，我们采用三数取中法，即得到待排序区间后，在区间的首中尾的三个数比较下拿更小值更有可能得使得取的基准值大小更偏中一点

3.2插入排序

3.2.1栈溢出原因

当二叉树经上层已排好序节点能确定往下再分更多的更小的待排序区间去排序时，在二叉树下几层会分出很多的待排序子区间去排序，除了最底层的不需要去排序，其它在上层的每个区间的一次排序函数里都会执行到再调用下层的两个递归，在此时由于待排序子区间被分的特别多，会连续调用特别多的函数，一时间开辟特别多的函数栈帧，很有可能会造成栈溢出

3.2.2利与弊

因此在最后几层的许多待排序子区间去排序时，我们可以直接在倒数的上几层中就开始截断，不再往下通过分更多的子区间去基准排序了，直接在这一层将待排序区域用插入排序直接排好，因为经过上层的有很多元素已经排好了位置，剩下的待排序元素也是间接地比较有序的，用插入排序也可以高效地完成，就不用去开辟下层大量聚集的函数栈帧避免了栈溢出，降低了开辟空间的成本

但是由于快速排序原本最后一层的元素通过上层元素的排好序全部可以间接地不用去排直接排好的，改成了插入排序后时间复杂度可能会比原来的纯快速排序更高了