当前位置: 首页 > news >正文

【算法专题】快速排序

1. 颜色分类

75. 颜色分类 - 力扣(LeetCode)

        依据题意,我们需要把只包含0、1、2的数组划分为三个部分,事实上,在我们前面学习过的【算法专题】双指针算法-CSDN博客中,有一道题叫做移动零,题目要求是把0移动到数组的最后端,于是我们通过两个指针:一个用于遍历数组、另一个用于将数组划分为零区域和非零区域。类似的,我们可以通过三个指针:一个用于遍历、两个用于将数组划分为三部分,即0、1、2。

        接下来我们要考虑的是遍历数组时遇到不同的情况如何处理,我们可以画一个划分过程中的简单示意图:

接下来分析i遍历时会碰到的三种情况:

然后就是将算法原理转化为代码,建议大家可以拿出纸笔,找个例子来模拟一遍,这样能对原理有更深的理解,也有利于接下来代码的编写。

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

2. 排序数组

912. 排序数组 - 力扣(LeetCode)

        这道题目要求我们将给定数组进行升序排列,既然本文标题是快速排序,这里当然是用快排来解决啦!快排的原理是:选择一个基准元素,然后让数组中小于等于基准元素的元素都排在基准元素左侧,大于基准元素的元素都排在基准元素右侧,然后对左侧区间和右侧区间分别做同样的操作,体现了分而治之的思想。

        不过一般的快排可不能解决这道题,因为快排虽然在平均情况下挺高效的,但出现相同元素的个数会影响快排的稳定性。

如上图所示,在最极端的情况下,整个数组都是相同的元素,则每次排序只能确定一个元素的位置,此时快排的时间复杂读退化到了O(n^2)。而本题的用例正好就出现了许多相同元素的情况,所以常规快排是会超出时间限制的,我们需要优化过的快速排序。

        相信大家都发现了,普通快排没有单独考虑相同元素的情况,于是会被相同元素影响到效率,故而我们可以针对这一点进行优化。单独考虑相同元素的情况后,我们将数组划分为三个区域:小于基准元素、等于基准元素、大于基准元素。没错,实际上这里的划分方式和上一道颜色分类是一样一样的。接下来要做的就是确定基准元素,方法有很多,不过算法导论中证明了,随机选取基准元素的快速排序的效率是最高的,因此我们在这里使用随机基准元素。

        

class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL)); // 种下随机数的种子,之后我们就可以通过rand()函数得到随机数了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 i = l, left = l - 1, right = r + 1;while (i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}qsort(nums, l, left);qsort(nums, right, r);}int GetRandom(vector<int>& nums, int left, int right){int index = rand();// 随机数取模区间大小就是偏移量,再加上left,就得到了随机元素的下标return nums[index % (right - left + 1) + left]; }
};

http://www.lryc.cn/news/399596.html

相关文章:

  • debian 12 PXE Server 批量部署系统
  • 【Pytorch】RNN for Image Classification
  • 基于Java的飞机大战游戏的设计与实现论文
  • 初识影刀:EXCEL根据部门筛选低值易耗品
  • nginx的四层负载均衡实战
  • 中职网络安全B模块Cenots6.8数据库
  • BGP笔记的基本概要
  • 【Redis】复制(Replica)
  • 封装了一个仿照抖音效果的iOS评论弹窗
  • 【JavaWeb程序设计】Servlet(二)
  • php探针
  • 泰勒级数 (Taylor Series) 动画展示 包括源码
  • 蔚来汽车:拥抱TiDB,实现数据库性能与稳定性的飞跃
  • 【Django+Vue3 线上教育平台项目实战】构建高效线上教育平台之首页模块
  • 对比 UUIDv1 和 UUIDv6
  • 记一次饱经挫折的阿里云ROS部署经历
  • 代码运行故障排除:PyCharm中的问题解决指南
  • css实现渐进中嵌套渐进的方法
  • JavaWeb后端学习
  • VUE_TypeError: Cannot convert a BigInt value to a number at Math.pow 解决方法
  • Linux下mysql数据库的导入与导出以及查看端口
  • Open3d入门 一文读懂三维点云
  • pyinstaller系列教程(一)-基础介绍
  • echarts图表:类目轴
  • SSM贫困生申请管理系统-计算机源码84308
  • [C++]——同步异步日志系统(5)
  • Qt项目:基于Qt实现的网络聊天室---TCP服务器和token验证
  • 深入理解C++构造函数
  • J025_斗地主游戏案例开发(简版)
  • 路径规划 | 飞蛾扑火算法求解二维栅格路径规划(Matlab)