排序算法——梳理总结

news/2024/4/21 1:47:02/文章来源:https://blog.csdn.net/2201_76033304/article/details/136524037

✨冒泡
✨选择
✨插入
 ✨标准写法
 🎭不同写法
✨希尔排序——标准写法
✨快排
✨归并
✨堆排

在这里插入图片描述

冒泡

在这里插入图片描述

void Bubble(vector<int>& nums)
{// 冒泡排序只能先确定最右边的结果,不能先确定最左边的结果for (int i = 0; i < nums.size(); i++){// 确定的右边的就不用排了并且不能让j+1越界// 所以判断条件是nums.size()-i - 1for (int j = 0; j < nums.size()-i - 1; j++)if (nums[j] > nums[j + 1])swap(nums[j], nums[j + 1]);}
}

选择

选择排序重要的是选,先选出来,再将这个数交换进去
在这里插入图片描述

void Select(vector<int>& nums)
{for (int i = 0; i < nums.size(); i++){int t = i;// 记录需要交换的数的位置for (int j = i + 1; j < nums.size(); j++)if (nums[t] > nums[j])t = j;swap(nums[t], nums[i]);}
}

插入

在这里插入图片描述

标准写法

插入排序是一个一个往后挪,最后再插入

void Insert(vector<int>& nums)
{for (int i = 0; i < nums.size(); i++){int t = nums[i];// 注意j表示需要检查的位置,这个位置必须遵循j>=0for (int j =i-1; j >= 0; j--){if (nums[j] > t)nums[j + 1] = nums[j];else{nums[j + 1] = t;break;}}}
}

注意j的范围

🎭不同写法

这种写法类似于冒泡排序,他是往前冒,虽然能对,但是这已经不是插入排序的思想

int* sortArray(int* nums, int numsSize, int* returnSize)
{//插入排序:在已经排好序的数组中进行插入*returnSize=numsSize;for(int i=0;i<numsSize;i++){//从此位置向前比for(int j=i;j>0;j--){if(nums[j]<nums[j-1]){int tem=nums[j];nums[j]=nums[j-1];nums[j-1]=tem;}elsebreak;}}return nums;
}

希尔——标准写法

在这里插入图片描述

希尔排序是在插入排序的基础上发展而来,所以要遵循插入排序的逻辑
他和插入排序不同在于,插入排序的gap=1,这个gap是从大到小变化

void Shell(vector<int>& nums)
{for (int gap = nums.size()/2; gap >0; gap/=2)// 间隔	{//每次向后跳间隔个长度for (int i = 0; i < nums.size(); i++) {int t = nums[i];// 注意j的范围for (int j = i-gap; j >= 0; j -= gap){if (nums[j] > t)nums[j + gap] = nums[j];else{nums[j + gap] = t;break;}}}}
}

注意j的范围


快排

我们使用三段式进行排序
[l,left] [left+1,right-1] [right,r]
[l,left]——小于key
[left + 1 , right-1]—— 等于key,等于key的是不用排序
[right , r]——大于key

int getNum(vector<int>& nums, int l, int r)
{srand(time(nullptr));return nums[l + rand() % (r - l + 1)];
}
void quicksort(vector<int>& nums, int l, int r)
{if (l >= r) return;int key = getNum(nums, l, r);int left = l - 1, right = r + 1, g = l;// 采用三段式进行while (g < right){if (nums[g] == key) g++;else if (nums[g] < key) swap(nums[g++], nums[++left]);else swap(nums[g], nums[--right]);}// [l,left][left+1,right-1][right,r]quicksort(nums, l, left), quicksort(nums, right, r);
}

归并

归并排序需要一个辅助数组,我们使用的是vector,使用之前需要进行resize,开足够大的空间的同时要运行进行随机访问

vector<int> tem;
void mergesort(vector<int>& nums, int l, int r)
{if (l >= r) return;int mid = l + r >> 1;mergesort(nums, l, mid), mergesort(nums, mid + 1, r);int left = l, right = mid + 1;int t = 0;while (left <= mid && right <= r){if (nums[left] < nums[right]) tem[t++] = nums[left++];else tem[t++] = nums[right++];}while (left <= mid) tem[t++] = nums[left++];while (right <= r) tem[t++] = nums[right++];t = 0;left = l;while (left <= r) nums[left++] = tem[t++];
}

堆排

void up(vector<int>& nums,int t)
{while (t > 0){int parent = (t - 1) / 2;// 大根堆if (nums[parent] < nums[t])swap(nums[parent], nums[t]);t = parent;}
}
void down(vector<int>& nums,int t)
{// 需要从这个位置开始向下down到底int child = t * 2 + 1;while (child < nums.size()){// 找到左右孩子中最小的位置//if (child + 1 < nums.size() && nums[child] > nums[child + 1])//	child++;//if(nums[t]>nums[child]) //	swap(nums[t], nums[child]);if (child + 1 < nums.size() && nums[child] < nums[child + 1]) child++;if (nums[t] < nums[child])swap(nums[t], nums[child]);t = child;child = t * 2 + 1;}
}
void Heap(vector<int>& nums)
{//筛选法建立初始堆——小大根堆都可以//for (int i = nums.size()/2; i >= 0; i--) down(nums, i);//for (int i = 0 ; i < nums.size(); i++) up(nums, i);// 如果想用up初始化堆,只能从头开始
}
  1. 筛选法建堆——先将所有数据加入构成堆,在从中间位置开始进行down(只能down,不论是建大堆还是小堆)
    什么时候使用up,为什么up不能在筛选法建堆中使用
    请添加图片描述
    就像上图中的情况,在建小堆的过程中,2是一定不能访问到的,就不能建成小堆,所以不能在筛选法中使用up(关键是筛选法起点是中间位置)
    如果想使用up,必须将每一个进行up,或者是某个位置上面的已经成堆,那么就可以在这个位置直接使用up
    对于down来说,如果某个位置下面已经成堆,那么就可以直接使用down

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

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

相关文章

Spark Core

Spark Core 一、Spark RDD RDD概述 1.RDD基础 2.RDD源代码描述 3.RDD特性 4.Spark宽窄依赖 RDD创建 在驱动器中创建RDD 1.parallelize 读取外部数据集创建RDD 2.textFile RDD操作 缓存rdd到内存 1.RDD转化操作 2.常见的转化操作 3.RDD行动操作 4.常见的行动操作 Spark…

力扣-数组题

1. 两数之和 找出map中是否有target-nums[i]&#xff0c; class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;for(int i 0 ;i < nums.size(); i){if(hash.find(target - nums[i]) ! hash…

Service Mesh:如何为您的微服务架构带来可靠性和灵活性

在云原生架构中&#xff0c;Service Mesh 技术成为了微服务架构中不可或缺的一环。本文灸哥将和你一起探讨 Service Mesh 技术的原理、功能和实践&#xff0c;帮助架构师和开发人员更好地理解和应用这一关键技术。 1、Service Mesh 技术概述 Service Mesh 又称为服务网格&…

【STM32】HAL库 CubeMX 教程 --- 高级定时器 TIM1 定时

实验目标&#xff1a; 通过CUbeMXHAL&#xff0c;配置TIM1&#xff0c;1s中断一次&#xff0c;闪烁LED。 一、常用型号的TIM时钟频率 1. STM32F103系列&#xff1a; 所有 TIM 的时钟频率都是72MHz&#xff1b;F103C8不带基本定时器&#xff0c;F103RC及以上才带基本定时器。…

代码随想录 回溯算法-分割

目录 131.分割回文串 93.复原IP地址 131.分割回文串 131. 分割回文串 中等 给你一个字符串 s&#xff0c;请你将 s 分割成一些子串&#xff0c;使每个子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正着读和反着读都一样的字符串。 示例 1&#xff1a; 输…

【PHP+代码审计】PHP基础——变量和常量的定义和使用

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【Java、PHP】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收…

【算法沉淀】刷题笔记:并查集 带权并查集+实战讲解

&#x1f389;&#x1f389;欢迎光临&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;特别推荐给大家我的最新专栏《数据结构与算法&#xff1a;初学者入门指南》&#x1f4d8;&am…

使用modinfo对比内核版本号

加载内核&#xff0c;出现版本不一样 cat /proc/verison查看内核板本 模块版本&#xff1a;显示模块的版本号。 $ modinfo [OPTIONS] [MODULE] 参数说明-F, --field <field>: 指定要显示的字段&#xff0c;可以使用逗号分隔多个字段。-k, --kernel <kernel>: 指定…

如何解决微服务的数据一致性分发问题?

介绍 系统架构微服务化以后,根据微服务独立数据源的思想,每个微服务一般具有各自独立的数据源,但是不同微服务之间难免需要通过数据分发来共享一些数据,这个就是微服务的数据分发问题。Netflix/Airbnb等一线互联网公司的实践[参考附录1/2/3]表明,数据一致性分发能力,是构…

OpenHarmony教程指南—ArkUI中组件、通用、动画、全局方法的集合

介绍 本示例为ArkUI中组件、通用、动画、全局方法的集合。 本示例使用 Tabs容器组件搭建整体应用框架&#xff0c;每个 TabContent内容视图 使用 div容器组件 嵌套布局&#xff0c;在每个 div 中使用 循环渲染 加载此分类下分类导航数据&#xff0c;底部导航菜单使用 TabCont…

基于springboot+vue的企业员工薪酬关系系统

博主主页&#xff1a;猫头鹰源码 博主简介&#xff1a;Java领域优质创作者、CSDN博客专家、阿里云专家博主、公司架构师、全网粉丝5万、专注Java技术领域和毕业设计项目实战&#xff0c;欢迎高校老师\讲师\同行交流合作 ​主要内容&#xff1a;毕业设计(Javaweb项目|小程序|Pyt…

【Spring底层原理高级进阶】Spring Batch清洗和转换数据,一键处理繁杂数据!Spring Batch是如何实现IO流优化的?本文详解!

&#x1f389;&#x1f389;欢迎光临&#xff0c;终于等到你啦&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;持续更新的专栏《Spring 狂野之旅&#xff1a;从入门到入魔》 &a…

猫毛过敏又不想扔掉猫怎么办?如何养猫?热门宠物空气净化器分享

养了猫咪一年多&#xff0c;忽然发现自己患上了过敏性鼻炎和结膜炎&#xff0c;就是那种一靠近猫咪就会不断打喷嚏、流鼻涕、流眼泪的症状。有时候还会感到眼睛发痒&#xff0c;发红。有没有什么好的方法治疗过敏性鼻炎呢&#xff1f; 医生建议&#xff0c;从根本上解决问题需…

【C++ 编程指南】

C 编程指南 ■ C环境安装■ C 基本语法■ 预定义宏■ # 和 ## 运算符■ C 引用■ C 命名空间■ 定义命名空间■ using 指令■ 嵌套的命名空间 ■ String类■ 类■ 类的static静态成员 ■ C 继承■ 继承类型 public、protected 或 private■ 访问控制和继承■ 多继承■ 数据抽象…

微信小程序-生命周期

页面生命周期 onLoad: 页面加载时触发的方法&#xff0c;在这个方法中可以进行页面初始化的操作&#xff0c;如获取数据、设置页面状态等。 onShow: 页面显示时触发的方法&#xff0c;在用户进入页面或从其他页面返回该页面时会调用此方法。可以在此方法中进行页面数据刷新、动…

医药行业五大难题深度剖析:CRM解决方案助力突围

医疗行业关系着民生、经济乃至战备&#xff0c;是国民经济的重要组成部分。虽然近20年来我国医疗行业年均增长率维持在15%之上&#xff0c;但行业发展仍存在诸多问题。引进CRM管理系统可能是一个行之有效的解决方法。文中将为您整理医疗行业目前的五大挑战&#xff0c;以及CRM如…

MPLS(多协议标签交换)-基础原理与配置

标签交换--包交换&#xff08;路由数据传递) 数据包在进入到的 MPLS 的域内后.转发该数据包时&#xff0c;最初在包交换仅支持原始交换时 将在第2层和3层中间压入标签号&#xff0c;使得域内的路由器在基于 2.5 层的标签号仅需要查询本地的一张(LFIB 表(标签转发信息数据库) 标…

01背包问题 刷题笔记

思路 dp 用f[i][j]来表示当体积为j时 考虑前i件物品可以获得的 最大值 记住f[i][j]本身是个价“价值” 考虑两种状态 是否将第i件物品放入背包里面 将背包的体积从小到大递增来进行考虑 首先 考虑条件 如果当前增加的体积放不下下一件物品 则该体积 可以获得的最大值可以直接…

c++复习

基础 内存分区 栈&#xff1a; 存放函数的局部变量、函数参数、返回地址等&#xff0c;由编译器自动分配和释放。 堆&#xff1a; 动态申请的内存空间&#xff0c;就是由 malloc 分配的内存块&#xff0c;由程序员控制它的分配和释放&#xff0c;如果程序执行结束还没有释放…

YOLO-World:实时开放词汇目标检测

摘要 Open Vocabulary&#xff1a;开放词汇 论文链接&#xff1a;https://arxiv.org/pdf/2401.17270.pdf You Only Look Once (YOLO) 系列检测器已经确立了自己作为高效和实用工具的地位。然而&#xff0c;它们对预定义和训练过的对象类别的依赖限制了它们在开放场景中的适用…