chapter_sorting/quick_sort/

[giscus[bot]]

chapter_sorting/quick_sort/

Your first book to learn Data Structure And Algorithm.

https://www.hello-algo.com/chapter_sorting/quick_sort/

[jimmie-wang]

js版本错的有点严重啊

[jimmie-wang]

我看错了，打扰了

[krahets]

感谢反馈！如果发现错误评论 or 提交 issues or 点击页面右上角铅笔图标修改，谢谢

[PeixiZ]

此部分的尾递归优化能否有图说明呢，看文字简短描述实在是想象不出来

[krahets]

收到，我后面画一下！

[muzishuiji]

10.6蹲一个1.7的图～

[feiaiyue]

为什么里面的循环还需要i<j

[krahets]

因为设定是 i == j 时终止并跳出。如果不加判断条件，可能还会继续 j-- i++ ，i 就在 j 的右边了。

[feiaiyue]

图的文章啥时候出来～等了一个月啦 K神

[krahets]

哎抱歉，前段时间🐑了，现在加足马力了

再给我两分钟，让我把堆图结成冰...

[wupf-code]

k佬，排序算法这块能不能加上链表的，犹记得第一次面试，被问道链表的逆序，之前从来没考虑过，懵掉了🤣🤣🤣🤣

[krahets]

好的，链表用归并排序比较方便，这个后续加上！

[FangYuan33]

K神，插入排序定义了base基准数，快排里也使用了基准数，但是并没有用局部变量来保存基准数，而在是在哨兵划分中定义了i和j，下边儿这种写法会不会更容易让读者理解呢？

    int partition(int[] nums, int left, int right) {
        // 以 nums[left] 作为基准数，并记录基准数索引
        int base = nums[left];
        int baseIndex = left;

        while (left < right) {
            while (left < right && nums[right] >= base)
                right--;             // 从右向左找首个小于基准数的元素
            while (left < right && nums[left] <= base)
                left++;              // 从左向右找首个大于基准数的元素
            swap(nums, left, right); // 交换这两个元素
        }
        swap(nums, baseIndex, left); // 将基准数交换到两子数组的分界线
        return left;                 // 返回基准数索引
    }

[krahets]

哈喽，从我角度看，两种写法差不多

[yy1781051483]

刚发现哨兵划分这里，先 从右往左 还是 从左往右 寻找，结果是不一样的。显然，先 从右往左 是正确的

[krahets]

是的，当我们以最左端元素为基准数时，必须先“从右往左”再”从左往右“。这个结论有些反直觉，我来详细剖析一下原因。

哨兵划分 partition() 的最后一步是 nums[left] 与 nums[i] 交换，完成交换后基准数左边的元素都小于等于基准数，这也就要求 交换前 nums[left] >= nums[i] 必须要成立。

假设我们先“从左往右寻找第一个比基准数大的元素”，那么如果找不到，则会在 i == j 时跳出循环，此时 nums[j] == nums[i] > nums[left] ；也就是说，这种情况下执行最后一步交换就会出问题了，会把一个比基准数更大的元素交换至数组最左端，导致哨兵划分失败。而如果我们先“从右往左”，就不会发生这个问题了。

[bnufw]

如果是选最右那个为基准数，则要先从左往右？

[SunAlsoRise97]

基准数优化，Java代码，' < '本身优先级高于' ^ '，可略去括号
改后代码

if (nums[left] < nums[mid] ^ nums[left] < nums[right])
        return left;
else if (nums[mid] < nums[left] ^ nums[mid] < nums[right])
        return mid;

[yzd11]

快排的C语言实现中swap函数是已经自己实现了吗？我并没有查到C语言有封装好的swap函数

[krahets]

谢谢指出，已添加～

[GyBernstein]

K神，关于尾递归优化，为什么选短的数组能保证递归深度不超过 $\log n$，有点反直觉

[krahets]

哈喽～递归深度就是当前未返回的递归方法的数量。

每轮哨兵划分我们将原数组划分为两个子数组。在尾递归优化后，向下递归的子数组长度最大为原数组的一半长度。假设最差情况，一直为一半长度，那么最终的递归深度就是 log n 。

回顾原始的快速排序，我们有可能会连续地递归长度较大的数组，最差情况下为 n, n - 1, n - 2, ..., 2, 1 ，从而递归深度为 n 。尾递归优化可以避免这种情况的出现。

[GyBernstein]

明白了，排短的能尽快返回，所以深度小一些，谢谢解答

[muzishuiji]

每轮哨兵划分我们将原数组划分为两个子数组。在尾递归优化后，向下递归的子数组长度最大为原数组的一半长度。假设最差情况，一直为一半长度，那么最终的递归深度就是 log n 。

这部分描述的「假设最差情况，一直为一半长度」，有点没明白，感觉一直为一半长度是最好的情况哎～

[muzishuiji]

哦哦，看了小结后理解了，这里说的最差情况是指空间复杂度（深度）的最差情况。

[woLQL]

尾递归优化的那个 未排序的子数组再怎么去处理？

[limuzi9806]

我的理解是这样的，拿2 4 1 0 3 5举例， 第一次哨兵后是 1 0 2 4 3 5 ，对 1 0 递归，此时pivot是等于 2，递归结束执行，left = pivot +1，此时left = 3 right = 5 ,while条件符合，就开始新一轮，也就是第一次未排序的子数组，每次效果类似

[krahets]

Hi，需要注意 while (left < right) 这一行，在递归完较短的子数组后，会重新计算一个新的 pivot ，再递归较短数组，以此类推…… 直至整个数组排序完成。

[muzishuiji]

感觉「尾递归优化」是把并行执行的递归操作变成了串行执行？
这样不会牺牲时间效率吗？本质上还是「用时间换空间」？

[krahets]

@muzishuiji 尾递归优化并不是时间换空间。它只是更改了递归调用的顺序，避免过大的递归深度累积。执行代码时都是“串行”的，系统不能同时进入两个递归，得按顺序执行。

[Loonngg]

请问, 如果数据全是一样的, 是不是会退化到n^2, 这该咋办

[krahets]

是的。这种情况可以考虑通过哨兵划分将数组划分为三个部分：小于、等于、大于基准数。仅向下递归小于和大于的两部分。在该方法下，输入元素全部相等的数组，仅一轮哨兵划分即可完成排序。

[WuYuJJ]

k神，可以写一下怎么划分为三段嘛~

[RediYo]

格式出现点问题，例如 (0)，都多了“\”，我使用的是edge浏览器

[krahets]

这个应该是 mathjax 组件没有正常加载导致的乱码，请尝试更换至 chrome 浏览器或更换网络环境

[zhuasdfg]

这尾递归也牛逼了吧，这是怎么想出来的，我拿着241035自个推了一遍，实在是妙不可言。while (left < right)这个循环太牛了。对内递归，对外跳出递归。

[xhmanong]

为什么在查找元素的时候，需要先要找出比基准数大的值呢？如果先找比基准数小的值的话，排序的结果是不正确的（即交换j--和i++的执行顺序）

[xhmanong]

输入示例：[5,2,3,1]。
输出为：[2,1,3,5]。
而结果应该是：[1,2,3,5]。

[krahets]

这个问题在小结 Q&A 中有讲

[MoRongsi]

js中一个更容易理解快排思想的代码：

function quickSort(arr){
  // 一个元素直接返回
  if(arr.length < 2) return arr;
  // 比基准小的放左边
  let left = new Array();
  // 比基准大的放右边
  let right = new Array();
  // 基准选第一个元素并删除原数组，剩下的arr就是未排序的数组
  let point = arr.splice(0, 1)[0];
  for(let i = 0; i < arr.length; i++){
    if(arr[i] > point){
      right.push(arr[i]);
    } else {
      left.push(arr[i]);
    }
  }
  // 再对左、右分别递归快排，再拼回有序数组就好了。
  return quickSort(left).concat([point],quickSort(right));
}

（因为要新开left和right数组，所以更废空间？）

[2893197486]

哨兵划分里面，while循环的条件，怎么判断是该有i<j还是i<=j呢？有时候总是分不清要不要加等号条件

[YiChau]

可以直接用例子验证两种情况，实际操作过一次就能分清了，同时直接用例子画出来，也比用脑袋想更容易。

[mjhu0]

d第三步是怎么解释的，看不懂

[fhm233]

基准数是2，因为j要寻找比基准数小的元素，所有找到0，i找到4，进行交换

[FreakWwjh]

请问 为什么尾递归优化后的快速排序比普通的快速排序多了一层循环？

[xxyxpy]

为了在少的一部分数组处理完之后还能再处理另外大的部分。这样的话小的数组递归快速弹栈结束，达到栈帧优化的目的。

[symhsym]

作者应该重点说明一下 partition函数中两个while的顺序问题，先后呼唤会报错

[BeyondWang]

+1

[FeifanLu]

为什么最后一部分叫做尾递归优化？ 这里面left or right =pi+1;才是最后一句,也就是说子函数返回以后还需要原来函数的环境, 不满足尾递归严格定义。并且虽然栈的深度得到优化，但还是有递归深度。不像尾递归递归深度一直是1？

引入迭代，与递归混合，来降低递归深度这一思想倒是能体现。

请高人解答为什么这叫做尾递归优化？

[LogicalMonster]

快排的尾递归优化，感觉rust版本可以改为用saturating_add、saturating_sub实现，这样left和right的类型是usize就可以了：

fn quick_sort_tail(nums: &mut [i32], mut left: usize, mut right: usize) {
    // 子数组长度为 1 时终止
    while left < right {
        // 哨兵划分操作
        let pivot = partition(nums, left, right);
        // 对两个子数组中较短的那个执行快速排序
        if pivot - left < right - pivot {
            assert!(right > pivot);
            quick_sort_tail(nums, left, pivot.saturating_sub(1)); // 递归排序左子数组
            left = pivot + 1; // 剩余未排序区间为 [pivot + 1, right]
        } else {
            assert!(left < pivot);
            quick_sort_tail(nums, pivot.saturating_add(1), right); // 递归排序右子数组
            right = pivot - 1; // 剩余未排序区间为 [left, pivot - 1]
        }
    }
}

[LunFengChen]

#include <iostream>
#include <random>
#include <algorithm>

#include <vector>

// 寻找3数中位数的索引
int calc_median_three(std::vector<int> &vec, int left, int mid, int right) {
    int l = vec[left], m = vec[mid], r = vec[right];
    if((l < m && m < r) || (r < m && m < l)) return mid;
    if((m < l && l < r) || (r < l && l < m)) return left;
    else return right;
}

// 寻找基准元素所在位置
int partition(std::vector<int> &vec, int left, int right) {
    // 基准元素: vec[left]
    // 1. 计算中位数索引
    int pivot_index = calc_median_three(vec, left, (right + left) / 2, right);
    // 2. 交换基准元素与第一个元素
    std::swap(vec[left], vec[pivot_index]);
    // 3. 进行划分
    int i = left, j = right;
    while(i<j){
        while(i<j && vec[j] >= vec[left]) j--;
        while(i<j && vec[i] <= vec[left]) i++;
        std::swap(vec[i], vec[j]);
    }
    std::swap(vec[left], vec[j]);
    return i; // 基准元素所在位置
}

// 快排实现
void qucik_sort(std::vector<int> &vec, int left, int right) {
    // 终止递归条件
    while(left<right){ // 改成循环->显式控制子数组范围，避免了递归调用的隐式问题，因此结果正确。
        // 寻找划分(partition)索引: 中心点(pivot)
        int pivot = partition(vec, left, right);
        // 尾递归优化: 选择较小的子数组进行递归排序，较大的子数组进行迭代排序
        // 这样可以减少递归的深度，避免栈溢出
        if ( pivot - left < right - pivot ) {
            qucik_sort ( vec , left , pivot - 1 ); // 递归排序左子数组
            left = pivot + 1 ; // 剩余未排序区间为 [pivot + 1, right]
        } else {
            qucik_sort ( vec , pivot + 1 , right ); // 递归排序右子数组
            right = pivot - 1 ; // 剩余未排序区间为 [left, pivot - 1]
        }
    }
}

int main() {
    std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::random_device rd;
    std::mt19937 gen(rd());
    std::shuffle(arr.begin(), arr.end(), gen);

    std::cout << "====================== Before sorting:\t======================\n";
    for (const auto& i : arr) std::cout << i << " ";

    std::cout << "\n====================== After sorting(upper):\t======================\n";
    qucik_sort(arr, 0, arr.size() - 1);
    for (const auto& i : arr) std::cout << i << " ";

    return 0;
}

====================== Before sorting: ======================
7 2 9 1 5 4 3 8 6
====================== After sorting(upper): ======================
1 2 3 4 5 6 7 8 9

[CheShiping]

为什么还用std::

[xiaozhuge123]

day09

[ustcxmz]

重要的一点是右哨兵先移动

[yyym2017]

为啥

[LostStar0128]

一点点理解，希望对大伙有帮助，如有不对希望指正^_^

//快速排序（quick sort）是一种基于分治策略的排序算法，运行高效，应用广泛。
/*
* 快速排序的核心操作是“哨兵划分”，其目标是：
* 选择数组中的某个元素作为“基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧
*
* thinking:从某种程度上来说也是进行“某种选择”，并不将其限定为最大值或是最小值，每一轮结束后也相当于哨兵恰好被移动到自己该去的位置，
* 且顺便将待排数组区分为low/high半区，过程上类似于某种“变异”的二分？
*
* 1、选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端
* 2、设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
* 3、循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。
* */


import java.util.Arrays;

public class Quick {
    static void oneQuick(int[] arr, int left, int right) {
        //以数组左边第一个元素为哨兵
        int sentry = arr[left];
        int lowH = left;
        int highL = right;

        //控制排序区间，不用=是因为
        //1、我们想要的最好的退出条件就是lowH==highL
        //2、lowH和highH两个指针加起来==全扫描整个数组，没必要越界插手
        while(lowH < highL) {
            //顺序很重要，必须先从highL指针开始找！！！
            //为什么？
            //因为我们是以左边第一个元素为哨兵，左边是小于哨兵的区域，所以进行最后一次哨兵归位的交换的时候，
            // 我们一定要确保最后的索引位置是恰好小于等于右边第一个元素的
            //若我们先从lowH向上找时，当出现这样的场景时就会出错[2]...0 ? 4
            //当这个？是一个<= [2]的值时，它就会满足while向上查询的判断条件(lowH < highL && arr[lowH] <= sentry)
            //这时执行lowH++; lowH == highL ，两个指针重合，但指向的是一个大于[2]的值
            //此时进行交换就会将一个大于哨兵的值换到左边
            //从上向下找时其实有同样的问题，但这个算法是以左边第一个元素为哨兵为例，因此必须要先去找第一个大于哨兵的位置

            //这样就会引出一个问题，其实这个算法本身谁是哨兵是不重要的，那为什么会存在与哨兵位置相关的这样的bug呢？
            //thinking：其实只有最后一次的交换可能会出问题，最后情况可能有两种
            //1、[2]... 4  1...
            //在这种情况下交换后为[2]... 1  4...
            //此时算法中先找的那个指针会先“向前”一步，这样，lowH == highL ，第二个指针不会动。
            //此时若要与low区的元素交换【即哨兵本身目前处在low区】则应当先寻highL指针，若要与high区的元素交换则需要先寻lowH
            //无解？？？
            //2、[2]...4 ? 1...
            //交换后任然取决于哨兵本身的位置情况和？的值的情况。
            //所以先尽量以最左或者最右元素为哨兵，最左时先寻highL，最右时先寻lowH

            //核心问题在于哨兵本身即为左右半区分界点，它既可以是low区，也可以是high区，这个时候就要看哨兵的初始位置在划分成型时的哪个半区


            //high指针做的是找出第一个小于sentry的元素索引
            while(lowH < highL && arr[highL] >= sentry)
                highL--;
            //lowH指针做的是找出第一个大于sentry的元素索引，控制寻找区间
            while(lowH < highL && arr[lowH] <= sentry)
                lowH++;

            //交换
            int temp = arr[lowH];
            arr[lowH] = arr[highL];
            arr[highL] = temp;

            //各自“前进”？
            // 答：不用，上面的循环很巧妙的可以使指针“前进”。两边交换后“刚好”满足各自的循环里的判定条件，
            // 所以可以自己再向前蠕动一步。
        }

        //哨兵归位
        arr[left] = arr[lowH];
        arr[lowH] = sentry;

    }
    public static void main(String[] args) {
        int[] arr = Selection.randomArray(20);
        System.out.println("Before sort:"+ Arrays.toString(arr));
        oneQuick(arr, 0, arr.length-1);
        System.out.println("After sort: "+ Arrays.toString(arr));
    }
}

/*运输结果
Before sort:[906, 359, 165, 998, 563, 134, 816, 758, 725, 174, 650, 677, 77, 25, 244, 42, 27, 613, 121, 380]
After sort: [121, 359, 165, 380, 563, 134, 816, 758, 725, 174, 650, 677, 77, 25, 244, 42, 27, 613, 906, 998]

进程已结束，退出代码为 0
*/

[fug-0117]

贴一个b站董晓老师的板子

int n, a[100005];  // 全局变量：n是数组长度，a[]存数据

void quicksort(int l, int r) {  // [l, r] 是当前要排序的区间
    if (l == r) return;  // 递归终止：区间只有1个元素，已有序
    
    // 1. 初始化指针、选基准
    int i = l - 1, j = r + 1;  // 指针初始在区间外，方便后续自增/自减后进入区间
    int x = a[(l + r) / 2];    // 选中间位置的数当基准（也可用随机、首/尾元素）
    
    // 2. 分区：把数组分成“≤x”和“≥x”两部分
    while (i < j) {
        // i 向右找 ≥x 的数：遇到 <x 的就跳过，直到找到 ≥x 的停下
        do i++; while (a[i] < x);  
        // j 向左找 ≤x 的数：遇到 >x 的就跳过，直到找到 ≤x 的停下
        do j--; while (a[j] > x);  
        
        if (i < j) {  // 如果 i、j 没交叉，交换两者位置
            swap(a[i], a[j]);  
        }
    }
    
    // 3. 递归处理左右子区间
    quicksort(l, j);    // 左子区间：[l, j]
    quicksort(j + 1, r); // 右子区间：[j+1, r]
}

[yezigege]

贴一个递归版

def quick_sort(arr: list):
   if len(arr) <= 1:
       return arr

   p = arr[0]
   less = [i for i in arr[1:] if i <= p]
   greater = [i for i in arr[1:] if i > p]

   return quick_sort(less) + [p] + quick_sort(greater)

[zxc177950]

问一下AI,AI现在很聪明

[PixelDana]

这个代码无法通过leetcode912. 排序数组，浪费时间……

[jiabingxiing]

是的，有错误的