【cpp】快速排序&优化

标题：【cpp】快速排序

@水墨不写bug

---

正文开始：

 快速排序的局限性：

虽然快速排序是一种高效的排序算法，但也存在一些局限性：

1. 最坏情况下的时间复杂度：如果选择的基准元素不合适，或者数组中存在大量重复的元素，快速排序的时间复杂度可能退化为O(n^2)。这种情况发生在每次划分之后，基准元素都是当前子数组中的最小或最大元素。

2. 对于小规模数据的排序效果较差：当数组规模较小时，例如只有几个元素，快速排序的性能可能不如其他简单的排序算法，如插入排序或选择排序。

3. 对于有序数组的排序效果较差：如果待排序的数组已经接近有序，快速排序的性能会下降。因为在划分过程中，基准元素的选择可能会导致子数组的不平衡，使得算法执行的时间增加。

4. 快速排序是一种不稳定的排序算法：当原始数组中存在相等元素时，算法执行过程中可能会改变它们的相对顺序。

        如何优化重复元素的问题，以免快排的时间复杂度退化为O（N^2）？

        通过下面这一问题，我们或许会得到一些启发。 

（一）颜色分类（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 == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

        颜色分类思想：

        定义三个指针（left，cur，right）：

        在排序过程中，这三个指针（left，cur，right），将数组分为四个部分，接下来希望你拿出纸笔跟我一起画一下：

        四个部分：

        一：【0，left】 

        二：【left+1，cur-1】 

        三：【cur，right-1】 

        四：【right，len-1】  

主体思路是：

        cur向后遍历，将小于1的元素放在left左边，等于1的元素不变位置，大于1的元素放在right的右边。

        需要注意的细节是，对于（nums[cur] == 0 ）由于left是右闭区间，其指向的元素满足要求，所以要先自增再交换；交换之后cur++向后遍历。

        对于（nums[cur] == 1）cur直接向后遍历；

        对于（nums[cur] == 2）由于left是左闭区间，其指向的元素满足要求，所以要先自减再交换；right在交换之前指向的元素本身就是未遍历的元素，所以交换之后不需要cur自增，直接判断cur交换得到的未遍历的元素即可。

        

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

（二）排序数组（leetcode）

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 5 * 10^4
• -5 * 10^4 <= nums[i] <= 5 * 10^4

        根据颜色分类的主体思想，如果用颜色分类来优化快排，那么这时再出现大量重复元素，就可以一次将他们排好序，不会再出现 在每次划分之后，基准元素都是当前子数组中的最小或最大元素的情况。

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums,0,nums.size()-1);
        return nums;
    }
    void qsort(vector<int>& nums,int l,int r)
    {
        //递归出口
        if(l >= r) return;
 
        //数组分三块
        int key = GetRandom(nums,l,r);
        int cur = l,left = l-1,right = r+1;
        while(cur < right)
        {
            if(nums[cur] < key) swap(nums[++left],nums[cur++]);
            else if(nums[cur] == key) cur++;
            else swap(nums[--right],nums[cur]); 
        }
        //递归排序子区间
        qsort(nums,l,left);
        qsort(nums,right,r);
    }
    int GetRandom(vector<int>& nums,int left,int right)
    {
        int r = rand();
        return nums[ r % ( right - left + 1 ) + left];
    }
};

代码理解： 

         上述代码是用C++实现的快速排序算法，用于对一个整数数组进行排序。sortArray函数接收一个输入向量nums，并使用qsort函数对其进行排序。

1.函数参数

qsort函数是一个递归函数，用于执行快速排序算法。它接收三个参数：输入向量nums、左边界索引l和右边界索引r。

2.递归出口的定义

        函数有一个基本情况，即如果左边界索引大于或等于右边界索引，那么只有一个元素或没有元素需要排序，所以函数返回。

3.key的选取

        使用GetRandom函数选择一个随机的轴元素（key），该函数在当前分区的范围内生成一个随机的索引。

4.递归主体

        然后，函数将数组分为三部分：小于轴元素（key）的元素、等于轴元素（key）的元素和大于轴元素（key）的元素。它使用三个指针：cur、left和right。

cur指针从左边界索引开始，向右边界索引移动，并相应地交换元素。如果当前元素小于轴元素，则将其与left指针处的元素交换，并同时递增这两个指针。如果当前元素等于轴元素，则递增cur指针。如果当前元素大于轴元素，则将其与right指针处的元素交换，并递减right指针。

        分区完成后，函数在左子数组和右子数组上递归调用自身以进行排序。

5.GetRandom函数

GetRandom函数在给定的左边界和右边界索引范围内生成一个随机的索引。它使用rand函数生成一个随机数，然后通过对右边界和左边界索引之间的差值加一取模，并加上左边界索引来计算索引值。

6.sortArray函数

        最后，在sortArray函数中，在开始排序过程之前，调用srand函数以用当前时间初始化随机数生成器，以确保每次运行程序时都会生成不同的随机数。

然后返回排序后的数组。

---

完~

未经作者同意禁止转载