Leetcode 561. 数组拆分 I (C++) 快速排序写法复习（小白学习之路）

ゝ一世哀愁。 2023-07-14 10:54 2阅读 0赞

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pbnQyeXg0_size_16_color_FFFFFF_t_70][]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/array-partition-i  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

最近按数据结构刷的题，不少简单题都可以直接调用有些语言里的内置函数解决，这道题挑出来写纯粹是复习一下快速排序的写法，题目乍一看题意有点奇怪，仔细一分析就能发现要达到Min（ai,bi）总和最大，就必须让最小的数跟次小的数凡在一个Pair里，否则次小数会作为另一个Pair里的较小数出现，从而使得最后总和不能达到最大；

因此这题最直观的思路就是把数组排序，将下标为偶数的所有数求和输出即可。

这里贴一下自己写的快速排序的代码：

void myQuickSort(int left, int right, vector<int> &nums)
    {
        if(left>=right) return ;  // 递归结束条件
        int flag = nums[left];
        int alert=1;   //alert==1表示从右开始，alert==0表示从左开始
        int templeft=left, tempright=right;  
        while(templeft<tempright)       // 一趟遍历下来，flag的最终位置确定
        {
            if(alert)                             //从右开始
            {
                if(nums[tempright]>=flag)             //右边的数大于基准数
                {
                    tempright--; alert=1;continue;    //右指针--，不交换数字
                }
                else                                  //右边的数小于基准数，
                {
                    nums[templeft] = nums[tempright]; //与左指针数字交换
                    templeft++;alert=0;continue;      //左指针++，并且下一趟从左边开始
                }
            }
            else
            {
                if(nums[templeft]<flag)          //从左开始
                {
                    templeft++; alert=0;continue;
                }
                else
                {
                    nums[tempright]=nums[templeft];
                    tempright--;alert=1;continue;
                }
            }
        }
        if(tempright==templeft) nums[templeft] = flag;    //循环结束是，左指针应该等于右指针，未基准数的最终位置
        myQuickSort(left,templeft-1,nums);    //递归遍历基准数左边
        myQuickSort(templeft+1,right,nums);   //递归遍历基准数右边
    }

一开始写快排的时候参数没有left,right指针，发现怎么写都很别扭，后来查了一下发现快排是不能原地排序的，因为递归的时候会发现要以原数组的一部分初始化为一个新数组，可能会出现意想不到的问题，后来加了left,right指针，一切就通顺多啦；

还有一个有意思的地方，我用vector的内置函数sort提交后发现比我写的快排速度要更快，内存消耗也少一些，以前一直以为STL内置sort函数就是快速排序，查阅了一些资料后发现并不只是快排，还结合了归并排序和插入排序，

当数据量过大的时候，sort函数会使用归并排序的思想先将大数组分为规模中等的数组，分别排序好后再进行归并；

当递归深度过深时，我们知道当数组基本有序时快排的效率很低，因为递归深度很深，而此时插入排序就接近最好的情况，于是sort函数会使用插入排序；

查看了一下STL sort（）的源码，有点头晕，模板很多，准备有精力研究的时候再看看吧。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pbnQyeXg0_size_16_color_FFFFFF_t_70]: /images/20230529/65933154d26940fb9ec6693b5dacc5e9.png