【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] 为 01 或 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)的元素。它使用三个指针:curleftright

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

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

5.GetRandom函数

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

6.sortArray函数

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

然后返回排序后的数组。


完~

未经作者同意禁止转载

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/520267.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【C++】c++11新特性(一)

目录 { }列表初始化 内置类型---对单值变量及数组的初始化 列表初始化时进行的类型转换 自定义类型---对类对象或结构的初始化 initializer_list 1. 定义接受 initializer_list 参数的构造函数 2. 在函数中使用 initializer_list 参数 3. 使用 initializer_list 与 vect…

教你网络安全

如今&#xff0c;组织的信息系统和数据面临着许多威胁。而人们了解网络安全的所有基本要素是应对这些威胁的第一步。 网络安全是确保信息完整性、机密性和可用性(ICA)的做法。它代表了应对硬盘故障、断电事故&#xff0c;以及来自黑客或竞争对手攻击等防御和恢复能力。而后者包…

Android14应用启动流程(源码+Trace)

1.简介 应用启动过程快的都不需要一秒钟&#xff0c;但这整个过程的执行是比较复杂的&#xff0c;无论是对手机厂商、应用开发来说启动速度也是核心用户体验指标之一&#xff0c;本文采用Android14源码与perfetto工具进行解析。 源码参考地址&#xff1a;Search trace分析工…

基于单片机多功能MP3播放器系统设计

**单片机设计介绍&#xff0c;基于单片机多功能MP3播放器系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机多功能MP3播放器系统设计是一个结合了硬件和软件设计的复杂项目。以下是对该系统设计的概要描述&#…

初识二叉树和二叉树的基本操作

目录 一、树 1.什么是树 2. 与树相关的概念 二、二叉树 1.什么是二叉树 2.二叉树特点 3.满二叉树与完全二叉树 4.二叉树性质 相关题目&#xff1a; 5.二叉树的存储 6.二叉树的遍历和基本操作 二叉树的遍历 二叉树的基本操作 一、树 1.什么是树 子树是不相交的;…

Github 2024-04-06Rust开源项目日报Top10

根据Github Trendings的统计,今日(2024-04-06统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Rust项目10HTML项目1Dart项目1RustDesk: 用Rust编写的开源远程桌面软件 创建周期:1218 天开发语言:Rust, Dart协议类型:GNU Affero General …

docker + miniconda + python 环境安装与迁移(详细版)

本文主要列出从安装dockerpython环境到迁移环境的整体步骤。windows与linux之间进行测试。 简化版可以参考&#xff1a;docker miniconda python 环境安装与迁移&#xff08;简化版&#xff09;-CSDN博客 目录 一、docker 安装和测试 二、docker中拉取miniconda&#xff…

C语言--指针终章

目录 1. sizeof和strlen的对⽐ 1.1 sizeof 1.2 strlen 1.3 sizeof 和 strlen的对⽐ 2. 数组和指针的理解——题目理解 2.1.sizeof 代码1&#xff1a; 代码2&#xff1a; 代码3&#xff1a; 代码4&#xff1a; 代码5&#xff08;二维数组&#xff09;&#xff1a; 2.2…

【蓝桥杯-单链表-网络寻路】

蓝桥杯-单链表-网络寻路 单链表基本操作操作一&#xff1a;向链表头插入一个数操作二:在第 k个插入的数后插入一个数操作三&#xff1a;删除第 k个插入的数后面的一个数&#xff1b; P8605 [蓝桥杯 2013 国 AC] 网络寻路 单链表基本操作 初始化有关操作 // head 表示头结点的…

Debian12 使用 nginx 与 php8.2 使用 Nextcloud

最近将小服务器升级了下系统&#xff0c;使用了 debian12 的版本&#xff0c;正好试试 nginx 和 php-fpm 这种方式运行 Nextcloud 这个私有云的配置。 一、基本系统及应用安装 系统&#xff1a;debian12 x86_64 位版本最小安装&#xff0c;安装后可根据自己需求安装一些工具&…

如何优化TCP?TCP的可靠传输机制是什么?

在网络世界中&#xff0c;传输层协议扮演着至关重要的角色&#xff0c;特别是TCP协议&#xff0c;以其可靠的数据传输特性而广受青睐。然而&#xff0c;随着网络的发展和数据量的激增&#xff0c;传统的TCP协议在效率方面遭遇了挑战。小编将深入分析TCP的可靠性传输机制&#x…

【C++初阶】 vector 在OJ中的使用

前言&#xff1a; &#x1f3af;个人博客&#xff1a;Dream_Chaser &#x1f388;博客专栏&#xff1a;C &#x1f4da;本篇内容&#xff1a;只出现一次的数字 和 杨辉三角 OJ 目录 一、只出现一次的数字 题目描述&#xff1a; 二、杨辉三角OJ 题目描述&#xff1a; 一、只…

vue快速入门(七)内联语句

注释很详细&#xff0c;直接上代码 上一篇 新增内容 button点击事件绑定内联语句写法与要求 源码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-wid…

phpstorm设置头部注释和自定义注释内容

先说设置位置&#xff1a; PhpStorm中文件、类、函数等注释的设置在&#xff1a;setting-》Editor-》FIle and Code Template-》Includes-》PHP Function Doc Comment下设置即可&#xff0c;其中方法的默认是这样的&#xff1a; /** ${PARAM_DOC} #if (${TYPE_HINT} ! "…

【第九篇】使用BurpSuite进行编码与解码

Burp存在一个功能&#xff0c;可以识别包含不透明数据&#xff08;例如会话令牌&#xff09;的消息。 如图&#xff1a;如果 Burp 识别所选内容的编码格式&#xff0c;它会自动解码数据。解码后的文本显示在 Inspector面板中。 在编码工具模块中&#xff0c;可对数据进行重复解…

C. MEX Game 1

本题如果我们去模拟这个算法的话会很麻烦&#xff0c;也会TLE&#xff0c;首先我们想 1&#xff0c;对于alice来说&#xff0c;先取小的&#xff0c;对于bob来说先删除alic想取的下一个小的 2&#xff0c;那如果这个数多于两个&#xff0c;那也就是说&#xff0c;alice肯定能…

电工技术学习笔记——正弦交流电路

一、正弦交流电路 1. 正弦量的向量表示法 向量表示方法&#xff1a;正弦交流电路中&#xff0c;相量表示法是一种常用的方法&#xff0c;用于描述电压、电流及其相位关系。相量表示法将正弦交流信号表示为复数&#xff0c;通过复数的运算来描述电路中各种参数的相互关系 …

C/C++预处理过程

目录 前言&#xff1a; 1. 预定义符号 2. #define定义常量 3. #define定义宏 4. 带有副作用的宏参数 5. 宏替换的规则 6. 宏和函数的对比 7. #和## 8. 命名约定 9. #undef 10. 命令行定义 11. 条件编译 12. 头文件的包含 13. 其他预处理指令 总结&#x…

IP地址:是给主机配置的,还是给网卡配置的?

在探索网络的奥秘时&#xff0c;我们经常会遇到一个看似简单但又复杂的问题&#xff1a;IP地址到底是配置在主机上&#xff0c;还是配置在网卡上&#xff1f;为什么我们通常说的是“主机IP地址”呢&#xff1f;让我们一起深入探讨。 1. 网卡与IP地址 &#x1f5a5;️&#x1f…

有同学和我说,深度学习不用特征工程,只有浅层机器学习方法采用特征工程,我说你误会了,我给你好好解释吧!!

1. 通俗解释 浅层机器学习算法&#xff08;如逻辑回归、决策树、支持向量机等&#xff09;和深度学习算法&#xff08;如神经网络&#xff09;在特征工程上的依赖性确实存在一些差异。 浅层机器学习算法的特征工程依赖性&#xff1a; 浅层算法通常需要手工选择和设计特征&…