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/

[picturesque-software]

js版本错的有点严重啊

[picturesque-software]

我看错了，打扰了

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

[symnczc60628]

尾递归优化关注的是空间复杂度，使得最大不超过O(logn)，反过来讲，如果只递归大的，有可能需要递归n次，使得空间复杂度升至O(n)

[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 中有讲

[JameRoyar]

关于尾递归 其实大家只要关注 left = pivot + 1 这一个条件就好了 在递归完短的左子数组的时候 你会想对应长的右子数组去哪了 其实就在这里被划分到 下一个while left<right 的整体数组里面去了 然后会生成新的pivot再重复这个过程 就像是在不断的削苹果到只剩苹果核的过程 每次都把削完的部分看做一个新的整体 再次进行短的削除 不知道说明白了没有 希望可以提供一点微小的帮助

[madoka-incubator]

你干的好啊

[izip-aTLa2]

讲得好好！

[Tttdotd]

就是说，这里的尾递归优化其实是用一个while循环来降低了递归栈的深度

[symnczc60628]

尾递归优化关注的是空间复杂度，使得最大不超过O(logn)，反过来讲，如果只递归大的，有可能需要递归n次，使得空间复杂度升至O(n)

[GoGoGo13579]

我不太理解尾递归优化这个名字，这个递归函数也是在函数体最后执行的递归啊，应该不是尾递归把

[krahets]

确实，尾递归（Tail call）特指返回前最后一步才执行递归操作的情况。而这里的尾递归优化（Tail call optimization）不符合这个定义。

然而，“快速排序的尾递归优化“是一个广泛使用的概念，它的核心思想是“每轮递归调用处理长度较短的那部分”，可能这便是“尾（Tail）”在这个语境下的含义。

[symnczc60628]

确实是哦

[MambaFly]

感觉自适应并不一定就是好处，数据规律好自适应了可以提高效率，但也意味着需要忍受极端数据样例下的效率降低，归并的非自适应就可以总是nlogn，而快排自适应的nlogn在大部分情况适用

[ChineseCz]

// 选取三个候选元素的中位数
int med = medianThree(nums, left, (left + right) / 2, right);
// 将中位数交换至数组最左端
swap(nums, left, med);

为什么要交换到最左端，不能将后续left改成med吗

[ChineseCz]

想了下，后续i,j指针的遍历，如果不换到最左端，无法保证哨兵效果。
划分边界卡在最左侧时，
原先写法：最左端与边界交换即不变
换成med：可能造成错误交换

[IL-CHEN]

def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)

print(quick_sort([3,6,8,10,1,2,1]))

[AlstonX]

第一次做贡献，写一个我认为更容易记忆的Python版本吧。

这个版本不需要单独定义partition函数，也不需要记忆复杂的指针移动规则，本质原理和官方版本是一样的，所以理论上时间复杂度应该是一样的，都是O(nlogn)，但空间复杂度应该是O(n*n) = O(n^2)，因为最多n层递归栈帧，每层需要额外保存left, mid, right三个数组，长度加起来是n。但考虑到面试的时候一般不要求空间复杂度，写出来最重要。。。

def quick_sort(nums: list[int]) -> list[int]:
    
    n: int = len(nums)
    
    # 如果传入的nums只剩下一个数字或者没有数字，则说明已经排序好了，直接返回即可
    if n <= 1:
        return nums
    
    # 这个pivot的基本上是随机选的，不用这个中间的数也没关系
    pivot: int = nums[n//2]
    
    # 把传入的nums分成三组，左边的都小于刚刚选的pivot，右边的都大于pivot，中间的都等于pivot。
    # mid也需要是list是因为：1. 需要保持形式的一致性，否则语法上后面return部分没办法拼起来。2. 因为等于pivot的元素可能不止有1个。
    left, mid, right = [], [], []
    for num in nums:
        if num < pivot:
            left.append(num)
        elif num > pivot:
            right.append(num)
        else:
            mid.append(num)
    
    # 现在已经做到，left里的数字 < mid里的数字 < right里的数字
    # mid里的所有数字都是一个值，等于pivot，所以已经排序好，不需要再管了。
    # left和right里的数字还没有排序，所以把它们各自再当作一个子问题，递归应用quick_sort排序，这样它们也可以排好了。    
    return quick_sort(left) + mid + quick_sort(right)

[tstanon]

快速排序算法的递归和非递归C语言版本

// 快速排序
int mid3(float *x, int low, int high) { // 三数取中法，选取low, mid, high三个位置的元素，取其中值作为pivot
    int mid = (low + high) / 2;
    if (x[low] > x[mid]) swap(&x[low], &x[mid]); if (x[low] > x[high]) swap(&x[low], &x[high]); if (x[mid] > x[high]) swap(&x[mid], &x[high]);
    return mid;
}
void partition(float *x, int size, int *pivot) { // 根据pivot将数组分为两部分，左边的元素小于等于pivot，右边的元素大于pivot
    int low = 0, high = size - 1, i = low - 1, j = low, pivotIndex = mid3(x, low, high);
    float pivotValue = x[pivotIndex]; swap(&x[pivotIndex], &x[high]);
    for (j = low; j < high; j++) { if (x[j] <= pivotValue) { i++; swap(&x[i], &x[j]); } }
    swap(&x[i + 1], &x[high]); *pivot = i + 1;
}
void q_sort_rec(float *x, int size) { if (size > 1) { int pivot; partition(x, size, &pivot); q_sort_rec(x, pivot); q_sort_rec(x + pivot + 1, size - pivot - 1); } }
void q_sort_nrec(float *x, int size) {
    int *stack, top_idx = -1, left, right, pivot;
    // 最坏情况通常发生在每次分区时，枢轴总是选择到最小或最大的元素，递归深度会达到最大，即等于数组的大小 n，每次处理一个子数组时，会向栈中压入左右边界，即栈空间的需求为两倍。
    stack = (int *)malloc(2 * size * sizeof(int)); stack[++top_idx] = 0; stack[++top_idx] = size - 1;
    while (top_idx >= 0){
        right = stack[top_idx--]; left = stack[top_idx--]; partition(x + left, right - left + 1, &pivot); pivot += left;
        if (pivot - 1 > left) {stack[++top_idx] = left; stack[++top_idx] = pivot - 1;} if (pivot + 1 < right) {stack[++top_idx] = pivot + 1; stack[++top_idx] = right;}
    }
    free(stack);
}

[checkma-xh]

def partition(nums, left, right):
    i, j = left, right

    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1
        while i < j and nums[i] <= nums[left]:
            i += 1
        nums[i], nums[j] = nums[j], nums[i]

    nums[left], nums[i] = nums[i], nums[left]
    return i


def sort(nums, left, right):
    if left >= right:
        return
    
    idx = partition(nums, left, right)
    sort(nums, left, idx - 1)
    sort(nums, idx + 1, right)


nums = [1,3,32,4,1,-100,23,17,23,6,-7,2,9,-1000]
left = 0
right = len(nums) - 1

sort(nums, left, right)
print(nums)

[zxc177950]

关于尾递归优化理解,建议附上Idea的代码截图

[KF-14]

partition函数中必须先从右向左遍历，然后再从左向右遍历，反之就会出现错误。这个怎么解释呢？

[3Ajfdjsdsk2]

和代码执行顺序有关。在while循环中首先是从右向左找首个小于基准数的元素，然后是从左向右找首个大于基准数的元素。接着进行第一次交换。而最后结束循环进行的交换是针对基准元素左侧的，也就是把一个小于基准元素的数和基准元素的位置互换。【while循环结束条件是i和j相遇，如果按本节顺序来遍历，j停止的位置小于基准数的元素，i随后也停在这个位置。这样交换才有意义，不然就变成大于基准数的元素放在左子树组了】。自己运行更好理解，你可以用本节的例子去测试你会发现第一轮完成后并没有达到左子数组、基准数、右子数组顺序的效果。

[akiradavidsong]

尾递归优化有些复杂，以后再看看吧

[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呢？有时候总是分不清要不要加等号条件

[symnczc60628]

我的理解是只有一个数就不用进行哨兵划分了，所以不用加等号。

[YiChau]

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

[mjhu0]

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

[FreakWwjh]

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