十大排序算法C++实现

分类

在这里插入图片描述

复杂度

排序稳定性定义：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，A1=A2，且A1在A2之前，而在排序后的序列中，A1仍在A2之前，则称这种排序算法是稳定的；否则称为不稳定的。
在这里插入图片描述

原理

讲的很清楚的up主

小灰的讲解让你完全拿捏10大排序算法

C++代码实现

#include <iostream>
#include <vector>
#include <map>
#include <string>template<class T>
void swap(T &a, T &b) { T tmp = a;a = b;b = tmp; }
template<class T>
void print(std::vector<T> &v) { for(auto x : v) std::cout << x << " "; std::cout << std::endl; }// 1.冒泡排序 
// 算法描述：比较相邻的元素，如果第一个比第二个大，就交换它们两个；
// 对每一对相邻元素作同样的工作，从第一对到最后一对，这样在最后的元素应该会是最大的数
// 针对所有的元素重复以上的步骤，除了最后一个；
// 重复步骤 1~3，直到排序完成 
void BubbleSort(std::vector<int> &v, int n) {bool flag;for(int i = 0; i < n - 1; ++i) {flag = true;for(int j = 1; j < n - i; ++j) {if(v[j] < v[j-1]) {swap(v[j], v[j-1]);flag = false;}}if(flag) break;}print(v);
}// 2.插入排序 
// 算法描述：把区间分为左边已排序和右边未排序，初始已排序区间只有一个元素，就是数组第一个
// 每轮针对未排序区间的第一个元素，在已排序区间里找到合适的位置插入并保证数据一直有序
void InsertSort(std::vector<int> &v, int n) {for(int i = 1; i < n; ++i) {for(int j = i; j > 0 && v[j] < v[j-1]; --j) {swap(v[j], v[j-1]);}}
}// 3.选择排序
// 算法描述：把区间分为左边已排序和右边未排序， 初始已排序区间没有元素 
// 每轮从未排序区间中找到最小值，然后置换到已排序区间的末尾 
void SelectSort(std::vector<int> &v, int n) {int Min_pos;for(int i = 0; i < n - 1; ++i) {Min_pos = i;for(int j = i; j < n; ++j) {if(v[Min_pos] > v[j]) Min_pos = j;}swap(v[i], v[Min_pos]);}print(v);
}// 4. 堆排序 O(nlogn)
// 算法描述：利用堆这种数据结构所涉设计的一种排序算法。堆积是一个近似完全二叉树的结构
// 并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
// 堆排序可以用到上一次排序的结果，所以不像其他一般的排序方法一样，每次都要进行 n-1 此的比较 
void Heapify(std::vector<int> &v, int n, int i) { // 维护堆的性质 while(1) { // 循环代替递归，调整节点i位置 int Max_pos = i; // 判断节点 i 是否满足大顶堆的性质 if(i * 2 + 1 < n && v[Max_pos] < v[i * 2 + 1]) Max_pos = i * 2 + 1;if(i * 2 + 2 < n && v[Max_pos] < v[i * 2 + 2]) Max_pos = i * 2 + 2;if(Max_pos == i) break; // 节点 i 满足性质 swap(v[i], v[Max_pos]); // 将Max值上浮，i节点下沉，大顶堆 i = Max_pos; // 继续调整 }
}
void HeapSort(std::vector<int> &v, int n) {// 1. 建堆 复杂度O(n) ，从完全二叉树的末端的父节点开始维护堆的性质for(int i = (n - 1) / 2; i >= 0; --i) { Heapify(v, n, i);} std::cout << v[0] << std::endl; // 2. 进行堆排序, 将完全二叉树末端的元素与堆顶元素交换，然后删除完全二叉树末端的节点// 不断重复上述操作，直至堆中只有一个元素 // 排序过程中，就是从数组末端，不断放入当前堆顶的元素// 因此使用大顶堆排序出来就是升序 while(n > 1) {swap(v[0], v[n-1]);--n;Heapify(v, n, 0); // 对0号节点进行下沉调整，维护小顶堆性质 }print(v);
}// 5. 希尔排序  也称递减增量排序  
// 算法描述：通过不断缩小增量进行插入排序，算法的最后一步就是普通的插入排序
// 就是取越来越小的步长进行插入排序，这样在最后步长为 1 的时候，只需要调整很少的几次就可以完成 
// 对插入排序的改进   可以让一个元素可以一次性地朝最终位置前进一大步
void ShellSort(std::vector <int> &v, int n) {for(int len = n / 2; len >= 1; len /= 2) {for(int i = len; i < n; ++i) {for(int j = i; j - len >= 0 && v[j - len] > v[j]; j -= len) {swap(v[j - len], v[j]);}}}print(v);
} // 6. 计数排序  
// 算法描述：先确定数据范围range，然后统计每个数字的个数，然后依次输出即可得到有序序列
// 适用范围：数据范围比较集中且为整数序列
void CountSort(std::vector<int> &v, int n) {// 1.计算元素范围 int Max = v[0], Min = v[0];for(auto x : v) {if(x < Min) Min = x;if(x > Max) Max = x;}// 2.统计元素个数 int range = Max - Min + 1;std::vector <int> c(range, 0); // 统计数组 for(auto x : v) c[x - Min]++; // 映射一下 // 如果不考虑排序稳定性， 在这就可以直接从小到大按个数输出了 // 保证其稳定性需要继续操作 // 3.求统计数组前缀和，此时的 c[x]-1 就等于元素x在排序完的序列中的最大位置 for(int i = 1; i < range; ++i) c[i] += c[i-1];// 4.倒序遍历原始数据，从统计数组中找到正确位置并输出std::vector <int> tmp_v(v);for(int i = n - 1; i >= 0; --i) {int x = tmp_v[i] - Min; // 得到映射值 v[c[x] - 1] = tmp_v[i]; // 在 c[x]-1 的位置上填上 tmp_v[i] --c[x]; // 下个tmp_v[i]要在第c[x]-1个位置左边填上 }print(v);
} // 7. 桶排序
// 当数列取值范围过大，或者不是整数的时候，就无法用计数排序了 
// 类似于计数排序需要创建统计数组，桶排序需要创建若干个桶 
// 算法描述：分治的思想
template<class T>
void MergeSort(std::vector <T> &v, int l, int r); // 提前声明归并排序类模板 void BucketSort(std::vector <double> &v, int n) {// 1.确定数列的范围 double Max = v[0], Min = v[0];for(auto x : v) {if(x < Min) Min = x;if(x > Max) Max = x;}// 2.初始化桶 int bknum = n;	// 一般创建的桶数量等于原始数列的元素数量std::vector<std::vector<double> > bk_list(bknum);// 除了最后一个桶只包含数列最大值，其余的桶均分最大值和最小值的差值. 按照比例确定// 桶的区间范围 = (最大值-最小值) / (桶的数量 - 1) // 3.把元素都放入桶中double bk_range = (Max - Min) / (bknum - 1); for(auto x : v) {// num = (x-Min) 除以区间跨度 int num = (int)((x - Min) / bk_range);bk_list[num].emplace_back(x);}// 4. 对桶内部排序   可以采用归并排序，也可以采用快速排序之类的for(int i = 0; i < bknum; ++i) {MergeSort(bk_list[i], 0, bk_list[i].size() - 1);}int j = 0;for(auto &x : bk_list) {for(auto &d : x) {v[j++] = d;}} print(v);
}// 8. 基数排序
// 针对手机号，英文单词等复杂元素的排序 
// 算法描述：把排序工作拆分成多个阶段，每一个阶段只根据一个字符进行计数排序，一共排序k轮 (k是元素长度)
// 基数排序相当于通过循环进行了多次桶排序
void RadixSort(std::vector <std::string> &v, int n) {int Max = 0;for(auto s : v) if(s.size() > Max) Max = s.size();std::vector <std::string> tmp_v(n);// 如果要对序列进行排序，k 应该从个位开始枚举for(int k = Max - 1; k >= 0; --k) {// 进行计数排序 std::vector <int> c(128, 0); // 统计所有字符串的第k位for(int i = 0; i < n; ++i) {int x = '0'; // 先假设需要补 0 if(k < v[i].size()) x = v[i][k]; // 判断一下字符是否有 k 位 c[x]++;}for(int i = 1; i < c.size(); ++i) c[i] += c[i-1];// 倒序找到正确位置并输出，保证稳定性for(int i = n - 1; i >= 0; --i) {int x = '0';if(k < v[i].size()) x = v[i][k];tmp_v[c[x] - 1] = v[i];c[x]--;}v.swap(tmp_v);}print(v);
}// 9.快排 O(nlogn)，最坏 O(n^2) 
// 算法描述: 选定Pivot中心轴，在原来的元素里根据这个枢纽分
// 将小于Pviot的元素放到Pivot的左边, 将大于Pviot的元素放到Pivot的右边
// 递归处理左右子序列 
void QuickSort(std::vector<int> &v, int l, int r) {if(l >= r) return;int first = l, last = r, pivot = v[l];while(first < last) {	 while(first < last && v[last] >= pivot) --last;//将小于piv的放到左边v[first] = v[last];while(first < last && v[first] <= pivot) ++first;//将大于piv的放到右边v[last] = v[first];}v[first] = pivot; // 更新pivotQuickSort(v, l, first);QuickSort(v, first + 1, r);
}// 10.归并排序   O(nlogn)  稳定的排序算法，它不是原地排序算法
// 算法描述：将两个游标 i 和 j，分别指向 v[l, mid] 和 v[mid+1, r] 的第一个元素。比较这两个元素
// 如果 v[i]<v[j]，就把 v[i] 放到临时数组 tmp, 并且 i 后移一位，否则将 v[j] 放入 tmp，j后移一位 
template<class T>
void MergeSort(std::vector <T> &v, int l, int r) {if(l >= r) return;int mid = (l + r) >> 1;MergeSort(v, l, mid);	  // 对 [l, mid] 区间排序MergeSort(v, mid + 1, r);//  对 [mid+1, r] 区间排序// 双指针对把俩个数组合并成一个有序数组 T *tmp = new T[r-l+1];	  // 暂时存放合并出的数组 int i = l, j = mid + 1, c = 0;while(i <= mid && j <= r) {if(v[i] < v[j]) tmp[c++] = v[i++];else tmp[c++] = v[j++];}while(i <= mid) tmp[c++] = v[i++];while(j <= r) tmp[c++] = v[j++];for(int k = 0; k < c; ++k) v[l+k] = tmp[k];delete[] tmp;
}int main() 
{std::vector <int> v = {19, 97, 9, 17, 1, 8};
//	BubbleSort(v, v.size());
//	SelectSort(v, v.size());
//	SelectSort(v, v.size());
//	HeapSort(v, v.size());
//	ShellSort(v, v.size());CountSort(v, v.size());std::vector <double> d = {3.14, 2.66, 15.33, 20.0, 0.33};BucketSort(d, d.size());std::vector <std::string> v_s = {"121", "321", "12", "544", "312", "4354"};// 如果要对序列排序，不要用字符串的，用数字更方便，同时也要对函数进行修改 // 这种对字符串排序方式， 不足Max位的字符串，在末尾补 '0' std::vector <std::string> v_ss = {"banana","apple","orange","ape","he"};// 正确排序结果：ape apple banana he orange RadixSort(v_ss, v_ss.size());// 这俩函数是递归实现的，无法调用print,就放在最后了 
//	QuickSort(v, 0, v.size() - 1);
//	print(v);
//	MergeSort(v, 0, v.size() - 1);
//	print(v);return 0;
}

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

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

相关文章

Pytorch 快速参数权重初始化

Pytorch 快速参数权重初始化

定义一个函数&#xff1a; 这里比如要初始化2维卷积权重值&#xff0c;采用xaiver 数据分布&#xff0c;还有很多其他的数据分布可以探索 def weights_init(m):if isinstance(m, nn.Conv2d):xavier(m.weight.data)xavier(m.bias.data) 然后定义一个含2维卷积的网络&#xff…
阅读更多...
HTB——introduction to active directory

HTB——introduction to active directory

文章目录 一、Active directory structure二、Active Directory Terminology 一、Active directory structure Active Directory &#xff08;AD&#xff09; 是用于 Windows 网络环境的目录服务。它是一种分布式分层结构&#xff0c;允许集中管理组织的资源&#xff0c;包括用…
阅读更多...
Pytorch 里面torch.no_grad 和model.eval(), model.train() 的作用

Pytorch 里面torch.no_grad 和model.eval(), model.train() 的作用

torch.no_grad: 影响模型的自微分器&#xff0c;使得其停止工作&#xff1b;这样的话&#xff0c;数据计算的数据就会变快&#xff0c;内存占用也会变小&#xff0c;因为没有了反向梯度计算&#xff0c;当然&#xff0c;我哦们也无法做反向传播。 model.eval() 和model.train()…
阅读更多...
开源项目管理工具Helper的安装及汉化

开源项目管理工具Helper的安装及汉化

什么是 Helper &#xff1f; Helper 是基于 Laravel 和 Filament 的开源项目管理工具。 官方提供了在线演示&#xff1a;https://project-helper.net 安装 在群晖上以 Docker 方式安装。 数据库理论上是可以使用群晖自带的 MariaDB 的&#xff0c;但老苏为了省事&#xff0c…
阅读更多...
类和对象（一）

类和对象（一）

类和对象&#xff08;一&#xff09; 一&#xff1a;类的实例化1&#xff1a;什么是实例化2&#xff1a;类和对象的关系 二&#xff1a;类的初始化1&#xff1a;就地初始化2&#xff1a;默认初始化 三&#xff1a;this引用1:先看一个日期类的例子2&#xff1a;什么是this引用3&…
阅读更多...
基于单片机的智能饮水机系统

基于单片机的智能饮水机系统

收藏和点赞&#xff0c;您的关注是我创作的动力 文章目录 概要 一、系统设计方案分析2.1 设计功能及性能分析2.2设计方案分析 二、系统的硬件设计3.1 系统设计框图系统软件设计4.1 总体介绍原理图 四、 结论 概要 现在很多学校以及家庭使用的饮水机的功能都是比较单一的&#…
阅读更多...
【Mac开发环境搭建】JDK安装、多JDK安装与切换

【Mac开发环境搭建】JDK安装、多JDK安装与切换

文章目录 JDK下载与安装下载安装 配置环境变量安装多个JDK共存 JDK下载与安装 下载 Oracle官网提供了非常多个版本的JDK供下载&#xff0c;可以点击如下链接重定向到JDK下载页面 ORACLE官网JDK下载 安装 下面的官方文档可以点开收藏到浏览器的收藏夹&#xff0c;这样后续在开…
阅读更多...
高性能三防工业平板电脑 防摔防爆电容屏工控平板

高性能三防工业平板电脑 防摔防爆电容屏工控平板

HT1000是一款高性能工业三防平板&#xff0c;10.1英寸超清大屏&#xff0c;厚度仅14.9mm&#xff0c;超薄机身&#xff0c;可轻松插入袋中&#xff0c;方便携带&#xff0c;搭载8核2.0GHz高性能CPU&#xff0c;行业领先的Android 11.0&#xff0c;设备性能大幅提升&#xff0c;…
阅读更多...
leetcode2054

leetcode2054

leetcode 2054 #include <iostream> #include <vector> #include <tuple> #include <algorithm>using namespace std;struct Event {// 时间戳int ts;// op 0 表示左边界&#xff0c;op 1 表示右边界int op;int val;Event(int _ts, int _op, int _v…
阅读更多...
本周三商店更新：多款套装下线，四款升级武器带异色皮肤返厂

本周三商店更新：多款套装下线，四款升级武器带异色皮肤返厂

本周三将迎来26.2版本更新与11商店大更新&#xff0c;版本更新可点击26.2版本更新公告进行查看&#xff0c;这里不一一赘述了&#xff0c;下面大概罗列一下商店更新&#xff0c;有皮肤下架&#xff0c;大家还能趁最后时间入手&#xff0c;最重要的是四款升级武器返厂咯。 危险玩…
阅读更多...
Git 安全警告修复手册：解决 `fatal: detected dubious ownership in repository at ` 问题 ️

Git 安全警告修复手册：解决 `fatal: detected dubious ownership in repository at ` 问题 ️

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…
阅读更多...
Unity meta的一些常见属性

Unity meta的一些常见属性

Unity会项目文件夹中的每个文件分配一个同名后缀为.meta的文件。 我们可以将meta文件理解不同文件之间的桥梁&#xff0c;通过它引擎可以管理不同文件之间的依赖关系。 使用TXT文本文件打开之后&#xff0c;大致属性如下&#xff1a; 其中常用的属性有guid、 assetBundleName以…
阅读更多...
MYSQL：主从复制简述

MYSQL：主从复制简述

&#xff08;图片来自于马士兵教育&#xff09; 从节点的I/O线程会请求主节点的Binlog&#xff0c;并且将得到的Binlog写入到本地relay_log&#xff08;中继日志&#xff09;中&#xff0c;SQL线程会读取realy_log中的日志文件&#xff0c;并且解析成SQL逐行执行。 主库会生成…
阅读更多...
C-DS二叉树_另一棵树的子树

C-DS二叉树_另一棵树的子树

Description 给你两棵二叉树tree1和tree2&#xff0c;检验tree1中是否包含和tree2具有相同结构和结点值的子树。如果存在&#xff0c;输出true&#xff1b;否则&#xff0c;输出false。 Input 第一行输入t&#xff0c;表示有t个测试样例。 第二行首先输入n1&#xff0c;接着…
阅读更多...
WPS表格无法粘贴信息，原因是复制区域与粘贴区域形状不同

WPS表格无法粘贴信息，原因是复制区域与粘贴区域形状不同

WPS表格无法粘贴信息&#xff0c;原因是复制区域与粘贴区域形状不同 问题描述 我是选中了一整列&#xff0c;复制&#xff0c;但是无法粘贴到另一个EXCEL表格中 原因 首先我的数据量很大&#xff0c;有20万行&#xff0c;然后需要复制的EXCEL是.xls格式的&#xff0c;.xls格…
阅读更多...
【UART】UART QA

【UART】UART QA

UART常见知识点整理 定义&#xff1a;Universal Asynchronous Receiver/Transmitter - 通用异步收发传输器。 特点&#xff1a;速率不快、可全双工、结构上一般由波特率产生器、UART发送器、UART接收器组成&#xff0c;硬件2-3线。 线&#xff1a;RXD&#xff0c;TXD&#xff0…
阅读更多...
SonarQube的使用心得

SonarQube的使用心得

一、使用背景&#xff1a; SonarQube 是一个用于代码质量管理的开源平台&#xff0c;用于管理源代码的质量。 通过插件形式&#xff0c;可以支持包括 java, C#, C/C, PL/SQL, Cobol, JavaScrip, Groovy 等等二十几种编程语言的代码质量管理与检测。 Sonar可以从以下七个维度…
阅读更多...
LSTM缓解梯度消失问题

LSTM缓解梯度消失问题

关于LSTM https://easyai.tech/ai-definition/lstm/ https://towardsdatascience.com/illustrated-guide-to-lstms-and-gru-s-a-step-by-step-explanation-44e9eb85bf21 为何LSTM缓解梯度消失问题 为什么LSTM会减缓梯度消失&#xff1f; - 知乎 LSTM引入长短期记忆&#xf…
阅读更多...
【STL】：list的模拟实现

【STL】：list的模拟实现

朋友们、伙计们&#xff0c;我们又见面了&#xff0c;本期来给大家解读一下有关list的模拟实现&#xff0c;如果看完之后对你有一定的启发&#xff0c;那么请留下你的三连&#xff0c;祝大家心想事成&#xff01; C 语 言 专 栏&#xff1a;C语言&#xff1a;从入门到精通 数据…
阅读更多...
【Linux】编译安装nginx，手写service配置文件，深度理解systemd控制管理服务底层原理

【Linux】编译安装nginx，手写service配置文件，深度理解systemd控制管理服务底层原理

目录 一、了解服务 1、服务的本质 2、centos7的systemd的服务 3、service unit file配置文件的组成以及掌握常用选项 4、关于systemd管理的命令学习 5、运行级别 二、编译安装nginx&#xff0c;以及手写service配置文件&#xff0c;请看注释 ​编辑 一、了解服务 1、服…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023