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

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

[HangSeven]

这个尾递归优化相当于每次缩减了排序区间的这个的长度，只进行哨兵划分，每次子数组小的递归都没有进去就结束了，空间相当与没有递归。这样理解吗K神

[krahets]

Hi 递归仍然执行了，只是把递归深度控制在了 O(log n) 的级别

[bnufw]

对于倒序数组，这个尾递归优化所占的空间复杂度是2吧？

[want2knoww]

常数项应该是2，每次递归深度只处理那一次，后面都是循环

[Hyrmm]

关于左右指针的的执行顺序，先后都一样么

[Fulin-Gao]

不一样，从左边先执行的结果不太对

[KHydroxide]

不一样，这个应该跟（大小顺序）和（基准数选在左还是右）有关，比如 基准数在左边，排序从小到大，交换之后 分界线对应的数字被换到左边，那分界线的数就应该比基准数小，所以得先j再i，才能让i=j的时候分界线是一个比基准数小的数

[xiaochunfeng679304]

c++中自定义的swap函数与它内置的swap函数会有什么区别吗，为什么不直接使用内置的函数呢

[OrdinaryChen]

那为什么不直接使用第三方库做快速排序，一个展示不用纠结

[xxc111111]

hi！ 第一个条件如果返回left 说明left是最小的，那if条件判断里的语句就成立，但成立的话通过异或该条件结果又是false，不满足if的条件判断，就应该不执行返回left，这不是矛盾吗

[ferryboy001]

我对 15.4 小节中代码的一点小疑问：
条件判断利用抑或运算简化了条件，表达的逻辑是 nums[left] < nums[mid] 和 nums[left] < nums[right] 两个命题有且只有一个为真，这就保证了 nums[left] 是这三者中的中位数。
但这里有一个问题，就是当三个数中有且只有任意两个相等的情况：
最简单的情况就是三者都相等，此时中位数可以是三者中的任意一个；
拿三者中有且只有两个数相等的情况详细考虑一下，如果把 nums[left]、nums[mid]、nums[right]记做 a、b、c，按照15.4 小节中的条件，当 a 不等于 b 和 c，第一分支的条件始终不满足，所以没问题。
当 b 不等于 a 和 c，始终不满足分支2，没问题；
当 c 不等于 a 和 b ，c 小于 a 和 b 的情况，按照条件，不符合分支1和2，此时默认会返回 c，但按照中位数的定义，c 此时并不是三者中的中位数。

[ferryboy001]

写错了，是 11.5.4

[xinzaibuyan]

确实这样改吧：
// 比较三个数，直接返回中位数的索引
if ((nums[left] <= nums[mid] && nums[mid] <= nums[right]) || (nums[right] <= nums[mid] && nums[mid] <= nums[left]))
return mid;
else if ((nums[mid] <= nums[left] && nums[left] <= nums[right]) || (nums[right] <= nums[left] && nums[left] <= nums[mid]))
return left;
else
return right;

[ferryboy001]

的确很直白，但感觉如果可以把抑或的条件完善，应该还是很优雅的，而且也很容易理解。
在原来的比较运算符后面加上等号应该就可以。
不知道是不是我哪里考虑的有问题，这个问题有点简单。

[krahets]

@feiaiyue 谢谢指正！无论加不加等号都会遇到 corner case ，看来这段代码并不是可靠的。

不加等号：

def median_three(nums: list[int], left: int, mid: int, right: int) -> int:
    """选取三个候选元素的中位数"""
    # 此处使用异或运算来简化代码
    # 异或规则为 0 ^ 0 = 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1
    if (nums[left] < nums[mid]) ^ (nums[left] < nums[right]):
        return left
    elif (nums[mid] < nums[left]) ^ (nums[mid] < nums[right]):
        return mid
    return right

nums = [2, 2, 1]
print(nums[median_three(nums, 0, 1, 2)]) # 1

加等号：

def median_three(nums: list[int], left: int, mid: int, right: int) -> int:
    """选取三个候选元素的中位数"""
    # 此处使用异或运算来简化代码
    # 异或规则为 0 ^ 0 = 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1
    if (nums[left] <= nums[mid]) ^ (nums[left] <= nums[right]):
        return left
    elif (nums[mid] <= nums[left]) ^ (nums[mid] <= nums[right]):
        return mid
    return right

nums = [2, 2, 3]
print(nums[median_three(nums, 0, 1, 2)]) # 3

[krahets]

还是老老实实用中位数的定义来做：

def median_three(a, b, c) -> int:
    """选取三个候选元素的中位数"""
    if (a <= b <= c) or (c <= b <= a):
        return b
    elif (b <= a <= c) or (c <= a <= b):
        return a
    return c

[SHENLAN-Li]

while (i < j && nums[j] >= nums[left])
j--;
while (i < j && nums[i] <= nums[left])
i++;
为啥这两个while位置调换一下就排序不成功啊

[krahets]

这个问题在本章小结的 Q&A 中有讲～

[ItsFated]

我来总结一下基准数优化和尾递归优化的作用和区别：
基准数取中位数：可以降低出现超过log n递归深度的概率
尾递归优化：可以避免出现超过log n递归深度的情况
K神，我这总结对不。

[krahets]

基准数取中位数：改善划分两个子数组的均匀性，避免时间复杂度劣化。

[OrdinaryChen]

基数优化解决的是树的不平衡问题，尾递归其实是解决深度问题，不尾递归优化那个应该是无脑展开一边，但是那一边有可能是n-1个到时候深度就是On了，但是你尾递归优化的那个是永远展开短的而短的必定小于n/2 所以会深度浅一点仅此而已。虽然我是初学者，不知道说的对不对，但是我感觉不应该叫尾递归，只是一个深度优化。尾递归应该是保证最后一步是调用函数自己，而这个尾递归最后一步是移动你的left和right指向 感觉不对

[wtw00928]

[4,3,5]怎么进行哨兵划分呀，第一开始哨兵是[4]，然后从右往左找到第一个小于4的数：3，从左往右走找到大于哨兵的数，没找到，只能跟3相等，这样下一次哨兵就是3，下一个递归中，左右都是长度为一，那么最后还是[4,3,5]，我哪里错了呀

[wtw00928]

明白了，原来两个基准数也要交换

[liweijian199011]

发现个问题，就是在partition方法中的while循环中，里面的while循环必须要是j--这个循环放在上面，而i++这个while要放在下面才可以，一旦交换位置，排序就不对，这是为什么？在逻辑上想不通这个道理。想着两个while子循环应该是彼此独立的，都是各干各的才对，为什么不能交换位置？

[krahets]

Hi，这个问题在本章的小结中有解释

[waibibabi]

i++放在上面两子数组分界线是在大于基准数的那一侧，这样交换后基准数左侧会出现一个大于基准数的数

[OrdinaryChen]

我开始也遇到了这个问题，然后我调试一步步下来发现如果你想从大到小的进行排序，且先进行左侧检查 。那在最后一个撞车的数字也就是left=right的时候，左侧数字就会在这个大的数字上等右侧数字过来撞车。这时候就会导致你真正要和基准数字换的数字其实在left-1的位置。但是右侧检查的时候right会先停在小于基准值的位置等left，这时候撞车就会在正确的数字上哈。所以说如果你是从大到小排序的话就要反一下，从左侧检查，差不多就是这么个原理~~~~~不知道你明白没。。。

[480284856]

因为如果先动i的话，i会可能会在一个大于基准数的元素上停止，此时我们假设j从最右边到i这里一直都没有找到一个小于基准数的元素，那么j就会直接跑到i这里，此时j=i，交换i，j元素；跳出循环；交换i与left的元素。但我们知道，此时i所在的元素是大于基准数的，交换到left那里会导致左子数组存在一个大于基准数的元素。

比如：[4, 9,8,7,6]
i开始动，i指向9
j开始动，j指向9
交换nums[i]与nums[j]： [4,9,8,7,6]
交换nums[i]与nums[left]： [9,4,8,7,6]

[Avengekkk]

K神是怎么做到代码写的这么优美又这么易懂的？我曾经以为二者不可兼得，直到我看到了你的代码。

[krahets]

我没有特别注意这个事诶，建议：遵守 style guide 、习惯使用 code formatter、多读写得好的代码

[HuaWang135608]

K神，尾递归优化没看懂，能不能举个例子说明一下🙏

[williamherry]

同没看懂，只对较短的子数组递归排序，较长的不管吗？

[OrdinaryChen]

刚开始我也没懂 知道下面有人提示我上面有个while (left < right) {，也就是说他先调用

if (pivot - left < right - pivot) {
            quickSort(nums, left, pivot - 1); // 递归排序左子数组

来调用短的那个数组（假设左边是短的），然后用left = pivot +1的方式把这个区间的指向移动到右侧区间的开头。此时right还在最右边。接着if结束后到了外头的while (left < right) {，这时候除非右边的和左边的撞车也就是区间只有一个数字了不然又会下来，就会开始递归右边的长的子数组了。也就是奥秘在于执行短数组后手动移动到右侧数组，然后用外面的while重启一个新的递归·····想明白了很容易，没想明白真的很难......

[krahets]

这段代码理解的关键是，不要陷入到向下递归（顺序执行）的步骤中。

我们先只看最顶层，传入的 left, right 参数代表未排序区间，由于存在 while (left < right) ，因此跳出循环时一定有 left >= right ，而此时整个数组已经完成排序了。

然后容易想到，每一层递归（每一个子问题）都同理，都可以解决当前子问题（排序好当前子数组）。

[summer-breeze123]

非递归快速排序

def partition(arr, left, right):
    i, j = left, right
    while i < j:
        while i < j and arr[j] >= arr[left]:
            j -= 1
        while i < j and arr[i] <= arr[left]:
            i += 1
        arr[i], arr[j] = arr[j], arr[i]
    arr[i], arr[left] = arr[left], arr[i]
    return i


def quick_sort(arr):
    s = [(0, len(arr) - 1)]
    while not len(s) == 0:
        left, right = s.pop()
        pivot = partition(arr, left, right)
        if left < right:
            s.append((left, pivot - 1))
        if pivot + 1 < right:
            s.append((pivot + 1, right))


if __name__ == '__main__':
    nums = [5, 2, 8, 3, 9, 1, 7]
    quick_sort(nums)
    print(nums)

[YMMdrq]

void QuickSorting(std::vector<int> &v,
                  std::vector<int>::size_type L,
                  std::vector<int>::size_type R)
{
    if (L >= R)
        return;                     // 左位置索引大于右位置索引,此数组已排完,函数退出
    int benchmark = v[L ]; // 设左索引值为基准
    auto i = L+1;
    auto j = R;
    /****************形成左子数组<=基准数<=右子数组****************/
    while (i < j)
    {
        while (v[i] <= benchmark && i < j) // 找到左数组大于基准的索引
            i++;
        while (v[j] >= benchmark && i < j) // 找到右数组小于基准的索引
            j--;
        if (i < j) {  
            std::swap(v[i], v[j]);  
        }
    }
    std::swap(v[L],v[i]);//将基准值交换到分界线
    /****************************************************************/
    QuickSorting(v,L,i-1);//左子数组递归为左子数组<=基准数<=右子数组
    QuickSorting(v,i+1,R);//右子数组递归为左子数组<=基准数<=右子数组
}

[summer-breeze123]

给你指出一点，排序过程中L和R可能变成负数，所以不要使用std::vector::size_type来定义变量，要用int，size_t实际上是无符号的，变成负数以后会溢出导致错误。

[YMMdrq]

我用std::vector::size_type这个主要是最近看c++primer，里面例子索引值相关变量都是用std::vector::size_type这种，应该是无符号长整形，因为vectorstd::vector::size_type代表的就是最大元素数量时索引值的数据类型，所以最大元素数量应该超过int范围。
应该不会有负数情况，因为我i是从 L+1开始的，所以i大于等于1，到QuickSorting(v,L,i-1)这步，所以L和R最小为0。

[summer-breeze123]

但是你这个算法依然是错的，自己试试就知道了

[summer-breeze123]

当只有两个元素的时候，你的i和j都是1，但是L是0，算法最后依然会交换v[0]和v[1]，所以出错

[YMMdrq]

知道了，测试用{0，1}，会排成{1，0}
主要时是没考虑基准值交换到分界线这步需要保证v[L]>=v[i],这和基准在右必须先右后左的问题一个意思。

[csuslm]

想请问一下，尾递归优化时，输入完全有序的数组的话，真的有优化吗，没有想明白