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

[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]

[JameRoyar]

很简单的 就是不要在意中间细节 就关注结果你做了什么 最后你是用left元素和相遇的pivot位置元素交换对吧 那换位之后的pivot位置元素是不是到左子数组去了 那是不是它得原来就是小于基准的 你先从右往左再左往右 相遇的位置就是小于基准的第一个元素 反之就是大于基准的第一个元素 所以left交换肯定要选小于基准的元素 所以是先从右往左再左往右 你非要反过来 那你去用最右边元素做基准去交换 也可以实现的

[Avengekkk]

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

[krahets]

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

[zhangben0408]

哈哈哈，只要这样，然后这样，再这样。优雅的代码就出来了

[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 ，而此时整个数组已经完成排序了。

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

[zhangben0408]

只是对较短的子数组进行递归，而较长的子数组则在本次函数调用中已经得到了排序（虽然也是递归处理）。

[summerBreeze03]

非递归快速排序

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);//右子数组递归为左子数组<=基准数<=右子数组
}

[summerBreeze03]

给你指出一点，排序过程中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。

[summerBreeze03]

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

[summerBreeze03]

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

[YMMdrq]

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

[csuslm]

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

[eattomatoeveryday]

如果不用前面的基准数优化的话，感觉即使是尾递归，它的递归深度仍然是n-1啊，不太理解

[eattomatoeveryday]

明白了，完全有序的情况下，并没有进行递归操作，而是通过循环不断处理剩下较大的数组

[MambaFly]

同，有点不明白，mark一下

[MambaFly]

说下目前的想法，还是看小标题，尾递归优化的是空间复杂度，也就是通过while循环来替代栈递归（循环比递归更节省空间），但时间复杂度并没有优化，如果是完全有序，那还是会落入最差的n^2，只能通过基准值的选择来尽量避免最差时间复杂度

[csuslm]

研究了尾递归的概念之后理解了，其实本质是迭代优化递归的一种方式

[luruifeng-div]

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

哪位大佬帮我看看哪里错了？找了好久找不到，谢谢

[luruifeng-div]

翻评论找到问题所在了

[Serendipity-hjn]

两个while顺序不能交换
while (i < j && nums[j] >= nums[left])
j--;
while(i < j && nums[i] <= nums[left])
i++;

[lai-handsome]

while (i < j) {
        while (i < j && nums[j] >= nums[left]) j--; // 从右向左找首个小于基准数的元素
        while (i < j && nums[i] <= nums[left]) i++; // 从左向右找首个大于基准数的元素
        this.swap(nums, i, j); // 交换这两个元素
    }

我将从右向左找首个小于基准数的元素，这个while循环放在下面，改成

while (i < j) {
        while (i < j && nums[i] <= nums[left]) i++; // 从左向右找首个大于基准数的元素
        while (i < j && nums[j] >= nums[left]) j--; // 从右向左找首个小于基准数的元素
        this.swap(nums, i, j); // 交换这两个元素
    }

排序得到的结果，就不正确了，这是为什么，有同学知道吗

[SoulMist666]

基准元素选的第一个，得先从右边找元素。因为你保存了基准元素，说明基准元素的下标处的值其实已经没有意义了（可以理解为只是留个它的空间，值已经被拿出去了，准备最后再放回去），但是你从左边开始判断，就把这个无意义的数又给放入自己的位置，导致基准元素出现了两次。 后面每次交换同理，把自己的值放入另一边那个“空的”下标，自己的下标的数已经无意义了，只是留空间。 个人是这样理解的，不知道对不对。

[SoulMist666]

不好意思，看错了。。我说成别的快排的原理了...下面有大佬回答了，别看我的回答了，看下面的吧。。

[lai-handsome]

这个问题已经想清楚了，本想在这里说明下的，但忘了，实在抱歉；其实很好理解，快速排序，就是把小于基准数的数放在基准数的左边，而如果是先从左向右寻找首个大于基准数的元素，i的值增加，可能会和j的位置重合，而下面一个while循环从右向左找首个小于基准数的元素不执行，直接this.swap(nums, i, j)，和基准数交换位置，这时就把比基准数大的元素放在了基准数的左边，导致排序的结果发生错误

[Chenzuhao]

从右到左 和 从左到右 的执行顺序问题
1.当最左边元素作为基数时，先执行 从右到左，再执行从左到右
2.当最右边元素作为基数时，先执行 从左到右，再执行从右到左

分析一下：
因为我们取左边元素作为基准数，最后的一步是将i=j时，i索引对应的元素和最左边元素基准数交换，然后作为基准数的
换句话说，i=j时，i就是基准数，基准数最后一次交换是向右交换，如果i=j时，左边还是存在比基准数大的元素，那这个排序就是有问题的，
因为i这个时候不满足 左子数组<=基准数<=右子数，例如：2,1,3,4，当i=j时，i指向3
换句话说
1.如果左边元素作为基准数，基准数最后一次交换是向右交换，要求右子数据都大于/都小于基准数，则一定时先执行 从右向左，因为这样右边元素都对比过了
2.如果右边元素作为基准数，基准数最后一次交换是向左交换，要求左子数据都大于/都小于基准数，则一定时先执行 从左向右，因为这样左边元素都对比过了

[JameRoyar]

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

[madoka-incubator]

你干的好啊

[GoGoGo13579]

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

[krahets]

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

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

[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);
}