C++:十大排序

目录

时间复杂度分析

选择排序

引言

算法思想

动图展示

代码实现 (升序)

优化 

代码实现

分析 

冒泡排序

引言

算法思想

动图展示

代码实现

插入排序

引言

算法思想

动图展示

代码实现

计数排序

引言

算法思想

动图展示

代码实现

桶排序

引言

算法思想

动图展示

代码实现

基数排序

引言

算法思想

动图展示

代码实现

希尔排序

引言

算法思想

动图展示

代码实现 

快速排序

引言

算法思想

动图展示

动图分析 

代码实现

堆排序

引言

大堆和小堆

算法思想 

动图展示

代码实现

归并排序

引言

算法思想

动图展示

代码展示

 


时间复杂度分析

选择排序

引言

选择排序(Selection Sort)是一种简单直观的排序算法。他首先在未排序的序列中找到最小元素,存放到排序序列的起始位置,然后再找到剩下序列中最小的元素,放到排好序列的下一个位置。以此类推,直到所有元素排序完毕。

算法思想

第一步、在未排序的序列中找到最小(最大)的元素,存放到排序序列的起始位置。
第二步、再从剩余未排序元素中找到最小(最大)的元素,然后放到已排序的序列的末尾。
重复第二步,直到所有元素都排序完毕。

动图展示

代码实现 (升序)

void  Select(int* a, int n)
{for (int i = 0; i < n - 1; i++)//排前n-1的数{for (int j = i + 1; j < n; j++){if (a[j] < a[i]){swap(a[i], a[j]);//未排序的序列中比目标小的就交换。}}}
}

优化 

上述代码在未排序的序列中找最小(最大)的元素,每一轮只能找到一个,还可以将其进行优化,一轮中可以同时找到最小和最大的元素,分别将其交换到未排序序列的头部和尾部.

代码实现

//选择排序
void chosesort(int* a, int n)
{int begin = 0; int end = n - 1;int mini = begin;int maxi = begin;while (begin < end){maxi = begin; mini = begin;for (int i = begin + 1; i <=end; i++){if (a[i] > a[maxi])maxi = i;if (a[i] < a[mini])mini = i;}if (begin ==maxi && end ==mini)swap(a[begin], a[end]);else{swap(a[begin], a[mini]);swap(a[end], a[maxi]);}begin++; end--;}
}

分析 

将未排序的序列的两端使用下标begin,end表示出来,注意我们找未排序序列中的最大值和最小值的时候找的是其下标并不是值,找到后将最大值(下标为maxi)和下标为end的值进行交换,将最小值(下标为mini)和下标为begin的值进行交换。

如果最大值恰好在begin位置,最小值恰好在end位置那么就只需要交换一次就可以了、

冒泡排序

引言

冒泡排序(Bubble Sort)是一种简单的排序算法,同过多次比较和交换相邻的元素,将数组中的元素按升序或降序排序。

算法思想

冒泡排序的基本思想是:每次遍历数组,比较相邻的两个元素,如果他们的顺序错误,就将他们交换,直到数组的所有元素都被遍历过。

动图展示

代码实现

//冒泡排序
void bubllesort(int* a, int n)
{for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++){if (a[j] > a[j + 1])swap(a[j], a[j + 1]);}}
}

插入排序

引言

插入排序(Insertion Sort)是一种简单直观的排序算法,它的工作原理是通过构有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应的位置并插入,直到整个数组有序。

算法思想

第一步:从第一个元素开始,将其看做已排序部分.
第二步:取出下一个元素,与已排序的元素进行比较。
第三步:如果该元素小于已排序部分的最后一个元素,则将其插入到已排序的适当位置。
重复步骤二和三,知道整个数组都排好。

动图展示

代码实现

//插入排序void Insertsort(int* a, int n)
{for (int i = 1; i < n; i++){int j;int tmp = a[i];for (j = i - 1; j >= 0; j--){if (a[j] > tmp){a[j + 1] = a[j];}elsebreak;}a[j + 1] = tmp;}
}

计数排序

引言

计数排序(Counting Sort)是一种基于哈希的排序算法。它的基本思想是通过统计每个元素的出现次数,然后根据统计结果将元素一次放到排序后的序列中。这种算法使用与元素范围较小的情况,例如0到k之间。

算法思想

计数排序的核心是创建一个计数数组。用于记录没每个元素出现的次数、然后根据计数数组对原始数组进行排序。具体步骤如下:
第一步:初始化一个长度为最大元素加1的计数数组,所有元素初始化为0.
第二步:遍历数组,将每个元素的值作为索引,在计数师叔祖的对应位置加1。
第三步;将原数组清空。
第四步:遍历计数器数组,按照数组中元素的个数放回到原数组中。

动图展示

代码实现

int * countingSort1(int arr[],int count,int max) {int index = 0;int *tmpArr = (int *)malloc(max*sizeof(int));int *result = (int *)malloc(max*sizeof(int));for(int k = 0;k<max;k++) {tmpArr[k] = 0;}for (int i = 0; i<count; i++) {tmpArr[arr[i]]++;}for (int j = 0; j<max; j++) {while (tmpArr[j]) {result[index++] = j;tmpArr[j]--;}}free(tmpArr);tmpArr = NULL;return result;
}

桶排序

引言

桶排序(Bucket Sort)是一种基于计数的排序算法,工作原理是将数据分到有限数量的桶子里,然后将桶子在分别排序(有可能在使用别的排序算法或者是以递归方式继续使用桶排序进行排序)。

算法思想

第一步:设置固定的空桶。
第二步:把数据放到对应的桶中。
第三步:把每个不为空的桶中的数据进行排序。
第四步:拼接不为空的桶中的数据,得到结果。

动图展示

代码实现

void bucketsort(vector<int>& nums) {int n = nums.size();int mn = nums[0], mx = nums[0];for (int i = 1; i < n; i++) {mn = min(mn, nums[i]);mx = max(mx, nums[i]);}int size = (mx - mn) / n + 1;   // size 至少要为1int cnt = (mx - mn) / size + 1; // 桶的个数至少要为1vector<vector<int>> buckets(cnt);for (int i = 0; i < n; i++) {int idx = (nums[i] - mn) / size;buckets[idx].push_back(nums[i]);}for (int i = 0; i < cnt; i++) {sort(buckets[i].begin(), buckets[i].end());}int index = 0;for (int i = 0; i < cnt; i++) {for (int j = 0; j < buckets[i].size(); j++) {nums[index++] = buckets[i][j];}}
}

基数排序

引言

基数排序(Radix Sort)是一种非比较型的排序算法,他根据数字的每一位来进行排序,通常用于整数排序,基数排序的基本思想就是通过对所有元素进行若干次“分配”和“收集”操作来实现排序。

算法思想

基数排序的算法思想可以概括为以下步骤:
第一步:获取待排序元素的最大值,并确定其位数。
第二步:从最低位开始,依次对所有的元素进行“分配”和“收集”操作。
第三步:在每一位上,根据该位置上的值将元素分配到相应的桶中。
第四步:在每个桶中的元素进行顺序收集,得到排序后的部分结果、
重复上述操作,直到所有所有位都排好。

动图展示

代码实现


int main()
{int a[] = { 1,6,4,12,32,16,10,89,100,120 };int b[10];int sum[256] = { 0 }, sum1[256] = { 0 }, sum2[256] = { 0 }, sum3[256] = { 0 };for (int i = 0; i <= 9; i++) {++sum[a[i] & 255];++sum1[(a[i] >> 8) & 255];++sum2[(a[i] >> 16 )& 255];++sum3[(a[i] >> 24) & 255];}for (int i = 1; i <= 255; i++){sum[i] += sum[i - 1];sum1[i] += sum[i - 1];sum2[i] += sum[i - 1];sum3[i] += sum[i - 1];}for (int i = 0; i <9; i++)b[--sum[a[i] & 255]] = a[i];for (int i = 9; i >= 0; i--)a[--sum1[(a[i] >> 8) & 255]] = b[i];for (int i = 9; i >= 0; i--)b[--sum2[(a[i] >> 16) & 255]] = a[i];for (int i = 9; i >= 0; i--)a[--sum3[(a[i] >> 24) & 255]] = b[i];for (int i = 0; i <= 9; i++)printf("a[%d]=%d\n", i, a[i]);getchar();return 0;}

希尔排序

引言

希尔排序(Shell Sort):是直接插入排序的一种优化,希尔排序通过基于直接插入排序间隔性的将非顺序序列的元素进行排序。需要进行多次排序,每次都更加的接近顺序,直到排好。

算法思想

首先创造变量gap作为将每隔gap个数分到一组中,将序列分为若干组,然后在每组中使用直接插入排序,同时每次使用完直接插入排序后都要减小gap的值(通常是gap/=2或者是gap=gap/3+1);直到最后gap为1,此时就是将一个十分接近顺序的序列进行插入排序,就排好啦。

动图展示

代码实现 

void slove(int* a, int n)
{int gap = n;//通常将gap初始化为数组的长度while (gap > 1)//最后一次gap=1,就是直接插入排序{gap = gap / 3 + 1;//每次都要减少对应的间距for (int i = 1; i < n; i++)//直接插入排序{int j;int tmp = a[i];for (j = i - gap; j >= 0; j -= gap){if (a[j] > tmp){a[j + gap] = a[j];}elsebreak;}a[j + gap] = tmp; }}
}

快速排序

引言

快速排序(Quick Sort)是一种分而治之的排序算法。它通过选择一个基准元素,将数组分为两部分,一部分比基准销小,另一部分比基准大,然后对这两部分进行快速排序,最终得到有序的数组。

算法思想

第一步、选择基准元素;从数组中选择一个元素作为基准。
第二步、分割数组:将比基准小的元素放在基准的左边,比基准大的元素放在基准的右边。
第三步、递归排序:对基准左边和右边的子数组分别进行快速排序。
重复步骤一、二、三、直到子数组的长度为1或0。

动图展示

动图分析 

这里选择数组首元素6的位置作为基准元素的位置,接下来目的就是把数组分左边小于基准元素右边大于基准元素。

左边指针为L右边指针为R,这里注意远离基准元素位置的指针要先走,R先走,从右向左找比a[keyi]小的数然后停下,L走,L从左向右走,找到比a[keyi]大的数然后停下。将两者位置上的值进行交换。然后继续R走,L走,直到两个指针相遇。

相遇后将这个位置的数与基准位置上的数进行交换。

然后再递归左边和右边的序列即可。

代码实现


void Quicksort(int* a, int left, int right)
{//改为左边先走即可(keyi右端点)if (left >= right)return;int keyi = left; //选取基准位置int begin = left; int end = right; while (left < right){ while (left < right && a[right] > a[keyi] ){ right--;               }while (left < right && a[left] < a[keyi])        {left++;   }swap(a[left], a[right]);}   swap(a[left], a[keyi]);   keyi = left;  Quicksort(a, begin, keyi - 1);  Quicksort(a, keyi + 1, end);
}

堆排序

引言

堆排序(Heap Sort)就是对直接选择排序的一种改进。此话怎讲呢?直接选择排序在待排序的n个数中进行n-1次比较选出最大或者最小的,但是在选出最大或者最小的数后,并没有对原来的序列进行改变,这使得下一次选数时还需要对全部数据进行比较,效率大大降低。堆排序算法是Floyd和Williams在1964年共同发明的,同时他们发明了“堆”这种数据结构。

大堆和小堆

这里简单的说下什么是小堆什么是大堆。小堆就是父节点的值比两个孩子节点的值都要小,孩子节点之间无大小比较;大堆就是父节点比两个孩子的节点的值都要大,孩子节点之间无比较。

算法思想 

堆排序使用到二叉树的调整算法,由于向下调整算法更优,这里只给出向下调整算法,向下调整算法的目的是为了建堆;建小堆排好是降序,建大堆排好是升序。

第一步、建好大堆:使用向下调整算法实现建堆。
第二步、交换头尾元素:每次建好堆之后我们可以确定的是堆顶一定是值最大的元素,将他交换到数列的末尾。
第三步、再次建堆:交换首尾之后,原来的堆就遭到了破坏,因此我们需要再次重新建堆,需要注意的是这一次建堆元素的个数就减一,因为刚才交换到最后的最大值已经算是排好的了,因此我们需要将剩下的元素建堆。
重复上述操作n-1次就排好了。

动图展示

代码实现

//堆排序(升序)
void adjustdown(int* a, int parent,int n)
{int child = 2 * parent + 1;while (child < n){if (child + 1 < n && a[child] < a[child + 1])child++;if (a[child] > a[parent]){swap(a[child], a[parent]);parent = child;child = child * 2 + 1; }elsebreak;}
}
void heapsort(int* a, int n)
{int end = n;while (end > 0)//堆不为空时{for (int i = (end - 2) / 2; i >= 0; i--)adjustdown(a, i, end);//先向下调整end--;//调整完之后swap(a[0], a[end]);//下一次要调整的堆的个数就是这一次要交换的目标值}
}

归并排序

引言

归并是一种常见的算法思想,在许多领域都有广泛的应用。归并排序的主要目的是将两个已排序的序列合并成有序的序列。

算法思想

当然,对于一个非有序的序列,可以拆成两个非有序的序列。然后分别调用归并排序,然后对两个有序的序列在执行合并的过程。所以这里的“归”其实是递归,“并”就是合并。
整个算法的执行过程用mergeSort(a[],l,r)描述,代表当前代排序的数组a,左下标i,右区间下标r,分为以下几步。

第一步:计算中点mid=(l+r)/2;
第二步:递归调用mergeSort(a[],l,mid)和mergeSort(a[],mid+1,r).
第三步:将第二步中的两个数组进行合并,在储存在a[l:r]。
调用时,调用mergeSort(a[],0,n-1)就能得到整个数组的排序结果了。

动图展示

代码展示

void merge(int*a,int begin,int mid,int end)
{int* b=new int[end-begin+1];//开辟区间所占整形大小的空间 int i=begin,j=mid+1;int k=0;//设置遍历下标初始值 while(i<=mid&&j<=end)//对辅助数组处理 {if(a[i]<a[j])b[k++]=a[i++];elseb[k++]=a[j++];}while(i<=mid)//把多余的一半放到辅助数组中 b[k++]=a[i++];while(j<=end)b[k++]=a[j++];k=0;for(int i=begin;i<=end;i++)a[i]=b[k++];
} void mergesort(int*a,int begin,int end)
{if(begin<end){int mid=(begin+end)/2;mergesort(a,begin,mid);//裂开! mergesort(a,mid+1,end);merge(a,begin,mid,end);//合体! }elsereturn;
}

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

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

相关文章

基于条件谱矩的时间序列分析(以轴承故障诊断为例,MATLAB)

谱矩方法可以对数据的表面形貌做较为细致的描述&#xff0e;它以随机过程为理论基础&#xff0c;用各阶谱矩及统计不变量等具体的参数表征表面的几何形态&#xff0c;算术平均顶点曲率是一种基于四阶谱矩的统计不变量。 鉴于此&#xff0c;采用条件谱矩方法对滚动轴承进行故障诊…

HCIA12 NAT网络地址转换实验

NAT&#xff08;Network Address Translation&#xff09;是将 IP 报头中的 IP 地址转换为另一个 IP 地址的过程。主要俩好处&#xff1a; • 有效避免来自外网的攻击&#xff0c;可以很大程度上提高网络安全性。 • 控制内网主机访问外网&#xff0c;同时也可以控制外网…

黑苹果睡眠唤醒后屏幕上的耳机输出总是丢失

文章目录 问题解决方案参考 问题 我的黑苹果睡眠唤醒后&#xff0c;总是会丢失屏幕上音频输出&#xff0c;屏幕重新点亮也不行&#xff0c;一般是重启电脑解决。因为在家里&#xff0c;不能总是外放&#xff0c;有时候需要屏幕上耳机听歌&#xff0c;很麻烦。 这是我解决后&a…

C语言详解(预编译)

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~~ &#x1f4a5;&#x1f4a5;个人主页&#xff1a;奋斗的小羊 &#x1f4a5;&#x1f4a5;所属专栏&#xff1a;C语言 &#x1f680;本系列文章为个人学习…

ESP32S3中使用按键控制LED灯亮灭

// 定义 LED 与 按键引脚 int led_pin 4; int button_pin 5;// 定义 LED 逻辑值 int led_logic 0; // 判断 LED 的状态是否改变过 bool status false;void setup() { pinMode(led_pin, OUTPUT);pinMode(button_pin, INPUT_PULLDOWN); }void loop() {// 按键消抖if (digita…

Java应用中文件上传安全性分析与安全实践

✨✨谢谢大家捧场&#xff0c;祝屏幕前的小伙伴们每天都有好运相伴左右&#xff0c;一定要天天开心哦&#xff01;✨✨ &#x1f388;&#x1f388;作者主页&#xff1a; 喔的嘛呀&#x1f388;&#x1f388; 目录 引言 一. 文件上传的风险 二. 使用合适的框架和库 1. Spr…

《大道平渊》· 拾叁 —— 失眠?忍不住乱想?不如反其道而行之!

《平渊》 拾叁 "睡觉的时候就是要胡思乱想" 声明&#xff1a;以下内容针对非失眠症人群&#xff0c;如果失眠不是偶尔发生&#xff0c;而是长期存在&#xff0c;以下内容和你无关&#xff0c;请尽早治疗&#xff0c;遵循医嘱。 失眠的本质是什么&#xff1f;心理因素…

stable diffusion中的negative prompt是如何工作的

https://stable-diffusion-art.com/how-negative-prompt-work/https://stable-diffusion-art.com/how-negative-prompt-work/https://zhuanlan.zhihu.com/p/644879268

机器学习常见知识点 2:决策树

文章目录 决策树算法1、决策树树状图2、选择最优决策条件3、决策树算法过程→白话决策树原理决策树构建的基本步骤常见的决策树算法决策树的优缺点 【五分钟机器学习】可视化的决策过程&#xff1a;决策树 Decision Tree 关键词记忆&#xff1a; 纯度、选择最优特征分裂、熵、基…

【源码】校园小情书小程序最新版 校园小程序开发 微信情书小程序 校园小情书小程序源代码

校园小情书微信小程序源码 | 社区小程序前后端开源 | 校园表白墙交友小程序 功能&#xff1a; 表白墙 卖舍友 步数旅行 步数排行榜 情侣脸 漫画脸 个人主页 私信 站内消息 今日话题 评论点赞收藏 服务器环境要求&#xff1a;PHP7.0 MySQL5.7 …

【PB案例学习笔记】-20制作一个超链接按钮

写在前面 这是PB案例学习笔记系列文章的第19篇&#xff0c;该系列文章适合具有一定PB基础的读者。 通过一个个由浅入深的编程实战案例学习&#xff0c;提高编程技巧&#xff0c;以保证小伙伴们能应付公司的各种开发需求。 文章中设计到的源码&#xff0c;小凡都上传到了gite…

PyTorch -- 最常见激活函数的选择

首先&#xff0c;简单复习下什么是梯度&#xff1a;梯度是偏微分的集合 举例说明&#xff1a;对于 z y 2 − x 2 : ∇ z ( ∂ z ∂ x , ∂ z ∂ y ) &#xff08; 2 x , 2 y &#xff09; z y^2-x^2: \nabla z (\frac{\partial z}{\partial x}, \frac{\partial z}{\partia…

第十四篇——互信息:相关不是因果,那相关是什么?

目录 一、背景介绍二、思路&方案三、过程1.思维导图2.文章中经典的句子理解3.学习之后对于投资市场的理解4.通过这篇文章结合我知道的东西我能想到什么&#xff1f; 四、总结五、升华![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/499cd9af2ea14cbf8d12813f6f…

互联网医院系统源码的创新应用:预约挂号小程序开发实战

预约挂号小程序作为互联网医院系统的创新应用&#xff0c;更加贴近用户需求&#xff0c;实现了预约挂号的便捷化和智能化。本篇文章&#xff0c;笔者将带领读者进入预约挂号小程序开发的实战过程&#xff0c;探索互联网医院系统源码在小程序开发中的创新应用。 一、互联网医院系…

50.Python-web框架-Django中引入静态的bootstrap样式

目录 Bootstrap 官网 特性 下载 在线样例 Bootstrap 入门 Bootstrap v5 中文文档 v5.3 | Bootstrap 中文网 在django中使用bootstrap 新建static\bootstrap5目录&#xff0c;解压后的Bootstrap文件&#xff0c;拷贝项目里就好。 在template文件里引用css文…

Perl语言入门学习

引言 Perl是一种功能强大的编程语言&#xff0c;广泛用于文本处理、系统管理和Web开发。它以其灵活性和强大的正则表达式处理能力著称。本篇博客将介绍Perl的基础知识&#xff0c;并通过多个例子帮助初学者快速上手。 1. 安装Perl 在开始学习Perl之前&#xff0c;您需要确保…

Stable Diffusion: ControlNet Openpose

上一文已经介绍了ControlNet的安装&#xff0c;点击右边的三角箭头。 拖放原始姿态图片。 勾选“启用”&#xff0c;“完美像素模式”&#xff0c;“允许预览” 控制类型选择“OpenPose(姿态&#xff09;” 预处理器选“openpose_full”&#xff0c;会对原始姿态图片做整体分…

opencv roi改进版

点击鼠标左键开始画roi,右键或者回车代表画框完毕 并且做了封装。 import cv2 import numpy as npclass ROIDrawer:def __init__(self, image_path):self.drawing = Falseself.ix, self.iy = -1, -1self.roi = Noneself.image_o = cv2.imread(image_path)self.image = self.…

[NCTF 2018]flask真香

打开题目后没有提示框&#xff0c;尝试扫描后也没有什么结果&#xff0c;猜想是ssti。所以尝试寻找ssti的注入点并判断模版。 模版判断方式&#xff1a; 在url地址中输入{7*7} 后发现不能识别执行。 尝试{{7*7}} ,执行成功&#xff0c;继续往下走注入{{7*7}}&#xff0c;如果执…

【网络编程】基于TCP的服务器端/客户端

TCP是Transmission Control Protocol(传输控制协议)简写。因为TCP套接字是面向连接的&#xff0c;因此又称为基于流的套接字。 把协议分为多个层次&#xff0c;设计更容易&#xff0c;通过标准化操作设计开放式系统 网络层介绍 链路层 链路层是物理连接领域标准化的结果&…