当前位置：首页 > article >正文

C++优选算法七分治-快排

article 2024/11/6 0:52:46

一、基本思想

快速排序采用分治法策略，将一个大数组（或子数组）分为两个小数组，然后递归地对这两个小数组进行排序。其基本思想可以概括为“分解、解决、合并”三个步骤：

分解：将原问题（即待排序的数组）分解为若干个规模较小、相互独立且与原问题形式相同的子问题（即子数组）。
解决：若子问题规模较小而容易被解决（即子数组的长度较小），则直接进行排序；否则，递归地解各个子问题。
合并：由于快速排序是就地排序（即在原数组上进行排序，不需要额外的存储空间），所以子数组排序完成后，原数组也就排序完成了，不需要额外的合并步骤。

二、具体实现

快速排序的具体实现包括以下几个关键步骤：

选择基准：从待排序序列中选择一个元素作为基准（Pivot）。基准的选择可以影响排序的效率，常见的选择方法包括选择第一个元素、最后一个元素、中间元素或随机选择。
分区：通过一趟扫描，将数组分为两个部分。在分区完成后，基准元素将处于其最终位置（即左侧的元素都小于等于基准，右侧的元素都大于基准）。分区过程通常使用两个指针（i和j）来进行：i指针从左到右扫描数组，找到第一个大于基准的元素；j指针从右到左扫描数组，找到第一个小于等于基准的元素。然后交换i和j指向的元素，直到i和j相遇或交错。
递归排序：对基准元素左侧和右侧的子数组进行递归调用快速排序。

三、示例题目

1.颜色分类. - 力扣（LeetCode）

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

解法(快排思想-三指针法使数组分三块):
算法思路:
类比数组分两块的算法思想，这里是将数组分成三块，那么我们可以再添加一个指针，实现数组分三块。
设数组大小为 n，定义三个指针 left，cur，right:

left:用来标记 0 序列的末尾，因此初始化为 -1;
cur:用来扫描数组，初始化为0;
right:用来标记 2 序列的起始位置，因此初始化为n。

在cur 往后扫描的过程中，保证:

[0，left]内的元素都是 0;
[left +1，cur -1]内的元素都是 1;
[cur，right-1]内的元素是待定元素。
[right，n]内的元素都是 2。

算法流程:
a.初始化cur =0，left =-1,right = numsSize;
b.当 cur < right 的时候(因为 right 表示的是 2 序列的左边界，因此当 cur碰到right 的时候，说明已经将所有数据扫描完毕了)，一直进行下面循环:

根据 nums[cur]的值，可以分为下面三种情况:

nums[cur]== 0;说明此时这个位置的元素需要在 left +1的位置上，因此交换 left +1与 cur 位置的元素，并且让 left++(指向 0 序列的右边界)，(为什么可以 ++呢，是因为 left +1 位置要么是0，要么是 cur ，交换完毕之后，这个位置的值已经符合我们的要求，因此cur++）；
nums[cur]== 1;说明这个位置应该在 left 和 cur 之间，此时无需交换，直接让cur++，判断下一个元素即可;
nums[cur]== 2;说明这个位置的元素应该在 right -1 的位置，因此交换right-1与cur 位置的元素，并且让right-- (指向 2 序列的左边界)cur 不变(因为交换过来的数是没有被判断过的，因此需要在下轮循环中判断)

c.当循环结束之后:

[0，left]表示0序列;
[left + 1, right-1]表示 1 序列;

[right, numsSize-1]表示 2 序列。

class Solution {
public:
    void sortColors(vector<int>& nums) 
    {
        int n=nums.size();
        int cur=0,left=-1,right=n;
        while(cur<right)
        {
            if(nums[cur]==0)
            {
                swap(nums[++left],nums[cur++]);
            }
            else if(nums[cur]==1)
            {
                cur++;
            }
            else if(nums[cur]==2)
            {
                swap(nums[--right],nums[cur]);
            }
        }
    }
};

2.快速排序. - 力扣（LeetCode）

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

解法(数组分三块思想+随机选择基准元素的快速排序)

算法思路:
快排最核心的一步就是 Partition(分割数据):将数据按照一个标准，分成左右两部分。

如果我们使用荷兰国旗问题的思想，将数组划分为 左中右 三部分:左边是比基准元素小的数据，中间是与基准元素相同的数据，右边是比基准元素大的数据。然后再去递归的排序左边部分和右边部分即可(可以舍去大量的中间部分)

在处理数据量有很多重复的情况下效率会大大提升。
算法流程:
随机选择基准算法流程:
函数设计:int randomKey(vector<int>& nums, int left, int right)

a.在主函数那里种一颗随机数种子;
b.在随机选择基准函数这里生成一个随机数;
c.由于我们要随机产生一个基准，因此可以将随机数转换成随机下标: 让随机数 % 上区间大小，然后加上区间的左边界即可。

快速排序算法主要流程:

定义递归出口;
利用随机选择基准函数生成一个基准元素;
利用荷兰国旗思想将数组划分成三个区域;
递归处理左边区域和右边区域。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(nullptr));//种下一个随机数种子
        qsort(nums,0,nums.size()-1);
        return nums;
    }

    void qsort(vector<int>&nums,int l,int r)
    {
        if(l>=r)
            return;

        //数组分三块
        int key=getRand(nums,l,r);
        int i=l,left=l-1,right=r+1;
        while(i<right)
        {
            if(nums[i]<key)
            {
                swap(nums[i++],nums[++left]);
            }
            else if(nums[i]>key)
            {
                swap(nums[i],nums[--right]);
            }
            else
                i++;
        }
        //[l,left]  [left+1,right-1]  [right,r]
        qsort(nums,l,left);
        qsort(nums,right,r);
    }
    int getRand(vector<int>&nums,int left,int right)
    {
        int r=rand();
        return nums[r%(right-left+1)+left];
    }
};

3.快速选择算法

数组中的第K个最大元素. - 力扣（LeetCode）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4],k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

解法(快速选择算法)

算法思路:
在快排中，当我们把数组「分成三块」之后:[l，left] [left + 1，right - 1] [right，r]，我们可以通过计算每一个区间内元素的「个数」，进而推断出我们要找的元素是在「哪一个区间」里面。
那么我们可以直接去「相应的区间」去寻找最终结果就好了。

class Solution {
public:
     int findKthLargest(vector<int>& nums, int k) {
        srand(time(nullptr));
        int ret = getKMax(nums, 0, nums.size() - 1, k);
        return ret;
    }

    int getKMax(vector<int>& nums, int l, int r, int k)
    {
        if (l == r)
            return nums[l];
        int key = getRand(nums, l, r);

        int i = l, left = l - 1, right = r + 1;
        while (i < right)
        {
            if (nums[i] < key)
            {
                swap(nums[i++], nums[++left]);
            }
            else if (nums[i] > key)
            {
                swap(nums[i], nums[--right]);
            }
            else
            {
                i++;
            }
        }

        //分情况讨论
        if (r - right+1 >= k)
        {
            return getKMax(nums, right, r, k);
        }
        else if (r - left >= k)
        {
            return key;
        }
        else
        {
            return getKMax(nums, l, left, k - (r - left));
        }
    }

    int getRand(vector<int>&nums,int left,int right)
    {
        int r=rand();
        return nums[r%(right-left+1)+left];
    }
};

4.库存管理Ⅲ. - 力扣（LeetCode）

仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。

示例 1：

输入：stock = [2,5,7,4], cnt = 1
输出：[2]

示例 2：

输入：stock = [0,2,3,6], cnt = 2
输出：[0,2] 或 [2,0]

解法(快速选择算法)
算法思路:
在快排中，当我们把数组「分成三块」之后:[l，left] [left +1，right - 1] [right，r]，我们可以通过计算每一个区间内元素的「个数」，进而推断出最小的k个数在哪些区间里面。
那么我们可以直接去「相应的区间」继续划分数组即可。

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& nums, int k) 
    {
        srand(time(NULL));
        getKmin(nums,0,nums.size()-1,k);
        return {nums.begin(),nums.begin()+k};
    }

    void getKmin(vector<int>&nums,int l,int r,int k)
    {
        if(l>=r)
            return;
        int key=getRand(nums,l,r);

        int left=l-1,right=r+1,i=l;
        while(i<right)
        {
            if(nums[i]<key)
            {
                swap(nums[i++],nums[++left]);
            }
            else if(nums[i]>key)
            {
                swap(nums[i],nums[--right]);
            }
            else
            {
                i++;
            }
        }
        int a=left-l+1,b=right-left-1;
        if(a>k)
        {
            getKmin(nums,l,left,k);
        }
        if(a+b>=k)
        {
            return;
        }
        else
        {
            getKmin(nums,right,r,k-a-b);
        }
    }

    int getRand(vector<int>&nums,int l,int r)
    {
        return nums[rand()%(r-l+1)+l];
    }
};

查看全文

http://www.kler.cn/a/380853.html