【算法】快速排序

2401_86112610

2797人浏览 · 2025-04-12 21:31:21

2401_86112610 · 2025-04-12 21:31:21 发布

算法系列六-快速排序

3.2查验能实现基础结果（在最底层往上点时）

一、快速排序的递归探寻

1.思路

左断开结果与右断开结果加上突兀根如何实现上一层的结果：

左断开有序+右断开有序加突兀根实现它比左部分都大、它比右部分都小就可以实现上一层的有序

2.书写

书写时是突兀根先实现再递归实现左右断开结果：

书写时反着来先实现突兀根一个节点左边都比都比它小、右边都比它大，再用递归实现它断开的左右有序结果

3.搭建

突兀根从底层向上的回搭搭建二叉树：

3.1设计过掉不符情况（在最底层时）

if(array == null) return， 没有元素不用排，下面是有元素
if(strat == end) return，只有一个元素不用排，下面是多个元素
if(strat > end) return，排不了不要排的，之后下面是符合正常情况的多个元素

3.2查验能实现基础结果（在最底层往上点时）

当突兀根来到倒数第二层，当共有两个元素下突兀根去作为在上层的会去操作实现上层与下两层结果的表示连接时，左边、右边都是有序的结果，要实现它这层的有序结果要突兀根去操作实现为它的值比左边的都大、比右边的都小，操作具体实现为与1节点的值进行交换完成突兀根的实现操作，实现了突兀根所在的上层结果与下层左右两断开结果的连接表示，说明突兀根的实现操作在底层确实是能完成基础排序的

3.3跳转结果继续往上回搭

4.实质

用二叉树递归实现排序实质上还是确定元素大小排在的数组位置递归完一个个来排的：

它排的位置左边都比它小、右边都比它大，它排的位置就是它在数组中排的大小位置，同时也确定着其它元素的相对大小排位位置，所以最后一层元素不去找基准排位置也是相对已确定下来的不用去排，所以if(start == end)return的

二、快速排序的基准排序

待排序元素将其所在的待排序区域调整划分成以它为基准值左边都比它小、右边都比它大的两部分，并将它基准值放入两部分的中间就完成了此元素的排序

1.双路双向交换铺（Hoare法）

1.1原理

要去排的元素基准值在待排序区域里面任意取好后，在待排序区域左右两端往内相遇铺路，右端往内铺遇小不符等停，左端往内铺遇大换过去交换，直至路头遇相等，此时路头位置即基准元素大小排在的位置，最后将基准元素交换过去就完成了此元素的排序

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利与弊

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

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