【C语言】选择排序及优化、冒泡排序、计数排序的实现

目录

  • 一、选择排序
    • 1.1 常规版(一次排好一个数)
      • 1.1.1 基本思想
      • 1.1.2 实现思路
      • 1.1.3 代码
    • 1.2 优化版(一次排好两个数)
      • 1.2.1 实现思路
      • 1.2.2 代码
    • 1.3 时间复杂度
  • 二、冒泡排序
    • 2.1 实现思路
    • 2.2 代码
    • 2.3 时间复杂度
  • 三、计数排序
    • 3.1 基本思想
    • 3.2 实现思路
    • 3.3 时间和空间复杂度
  • 总结


一、选择排序

1.1 常规版(一次排好一个数)

1.1.1 基本思想

每次从待排序的数据中选出一个最小(最大)值,从起始位置开始存放,每排好一个数,存放位置就会向后移一位,直到排所有的数据排完序。

在这里插入图片描述

1.1.2 实现思路

  1. 假设起始位置(i)是最小的,通过变量(minIndex)保存该下标
  2. a[mini]从该下标(i)的下一个位置(i+1)开始去数据中依次比较
  3. 找到比自己小的数据,就把mini设为小的下标,循环还没有结束,所以还会用mini位置的值去和后面的值比较。
  4. 数据都比较完后,minIndex位置的值就是全部数据中最小的,如果minIndex不等于i(一开始i和minIndex的值一样,找到最小了的值后minIndex的会被改变),就需要交换两个位置的值,相等i的位置就是最小值,不用动。(加这个判断是防止数据是有序的,有序就没有必要交换)
  5. i+1,为了把排好的数据给排除掉,i再去在找数据中最小的值,重复以上操作,直到i < n - 1结束。

注意:循环结束如果到i < n结束,在找数据时候就会越界如n = 1,i + 1就会越界,并且当已经排好了n-1个数后,最后一个元素已经是最大的元素,不需要再进行比较和交换操作了。

1.1.3 代码

// 选择判断(常规版,选一个数)
void SelectSort(int* a, int n)
{// n-1个数排好了,最后一个数就是正确的位置,不用在排序for (int i = 0; i < n - 1; i++){int minIndex = i;for (int j = i + 1; j < n; j++){if (a[j] < a[minIndex]){minIndex = j;}}// minIndex改变了需要交换,minIndex的位置就是最小值// 没有改变,i的位置就是最小值,不用动if (i != minIndex){Swap(&a[i], &a[minIndex]);}}
}

1.2 优化版(一次排好两个数)

选择排序的优化版和常规版,大体思路还是差不多的,只不过每次选出数据中的最小值和最大值。

1.2.1 实现思路

  1. begin和end标识数据的区间,注意是闭区间
  2. 最小值(minIndex)从begin(最左边)开始放,最大值(maxIndex)从end(最右边)开始放。
  3. 排好两个数据后,begin往后走,end往前走,排除已排好的数据(缩小区间),直到begin和end相遇就表示排好了。

特殊情况:
在这里插入图片描述

所以我们进行判断,max不等于begin,我们才进行交换,因为begin和min先交换,begin和max重叠,在begin位置的值就会被换走,如果让end和max先交换,还是会有这种问题,不过情况相反而已,所以这个条件必须要加

1.2.2 代码

// 选择判断(优化版,两个数)
void SelectSort_double(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){// 一次选出最小值和最大值int minIndex = begin, maxIndex = end;for (int i = begin; i <= end; i++){if (a[i] < a[minIndex]){minIndex = i;}if (a[i] > a[maxIndex]){maxIndex = i;}}if (minIndex != begin)Swap(&a[minIndex], &a[begin]);// max和begin重叠,maxIndex的值已被换到minIndex位置if (maxIndex == begin)maxIndex = minIndex;if (maxIndex != end)Swap(&a[maxIndex], &a[end]);begin++;end--;}
}

1.3 时间复杂度

时间复杂度为 O ( N 2 ) O(N^2) O(N2),最差的排序,最好情况下也是 O ( N 2 ) O(N^2) O(N2),数据有序的情况也要比较。


二、冒泡排序

2.1 实现思路

  1. 每次就排好一个数,第一个数据和第二数据先比较在交换,小的在前,大的在后,第二个数据在第三个数据交换,一直反复下去。a[j] > a[j + 1]
  2. 该过程会把小数据(不是最小,只是相比下小数据)交换到前面,直到交换到最后一个数据,最大的数据就在最后面了(比他小的数据都交换在他前面了),为了防止后面数据都是有序,用一个变量标识下(交换了没有),如果后面数据有序继续比较和交换效率低,我们做一下判断,如果有序(没有交换),我们就可以直接跳出。
  3. 排好一个数后,就排除已排好的数据(缩小区间),直到只剩最后一个数,如果有n个数,只需要交换n-1次j < n - 1 - i
  4. 一共只需要排n-1个数,和常规选择排序一个情况,n-1个数有序了,剩余的1个数肯定是有序的,就等于自己和自己比较在交换,无意义。

在这里插入图片描述

在这里插入图片描述

2.2 代码

// 冒泡排序
void BubbleSort(int* a, int n)
{// 最多排9个数(趟),9个数排好后,第10数就在排好的位置for (int i = 0; i < n - 1; i++){// 标识是否交换,默认是没交换int exchange = 1;	// 最多交换9次,最后一次是自己和自己交换,所以只需要排9次for (int j = 0; j < n - 1 - i; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);exchange = 0;	// 数据交换了}}// 数据没有交换,表示有序,就直接跳出if (exchange)break;}
}

冒泡和插入相比哪个更好?

插入排序,对有序,接近有序,局部有序,适应性更强
用一个接近有序的数据,对比执行次数,就能比较出来。


2.3 时间复杂度

时间复杂度为 O ( N 2 ) O(N^2) O(N2)

三、计数排序

计数排序属于非比较排序,只能排整形。

3.1 基本思想

先统计数据出现次数,写到相对的下标里,在通过数据对应的下标来进行从头依次排序,下标位置有几个数,就需要排几个数,数据值和下标相对的。
在这里插入图片描述

3.2 实现思路

  1. 计算出数据的范围区间,最大值减去最小值,这是相对范围min——max,绝对范围是0——max,太浪费空间。
  2. 创建一个计数数组count,因为是闭区间,大小是max-min+1,用来存放数据出现的次数,初始化都是0。
  3. 统计每个数出现的次数,放入到数据减去最小值的下标位置(计数数组的相对位置)。
  4. 把数据写到原数组里,只写次数不为0的,出现了几次就写入几个数据,数据通过count的下标+最小值还原出来。
// 计数排序
void CountSort(int* a, int n)
{// 找到最小值和最大值int min = a[0], max = a[0];for (int i = 1; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}// 计算出相对范围int range = max - min + 1;// 创建计数数组,初始化为全0// 方法1int* count = (int*)malloc(range * sizeof(int));	assert(count);memset(count, 0, range * sizeof(int));// 方法2,calloc申请的空间默认都是NULL或0(根据指针类型决定)//int* count = (int*)calloc(range * sizeof(int));	// 统计每个数出现的次数for (int i = 0; i < n; i++){count[a[i] - min]++;}// 把数组写入原数组// 数据出现了多少次就写入多少个值int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}

3.3 时间和空间复杂度

时间复杂度为 O ( N + K ) O(N+K) O(N+K),K是相对范围(计数数组)的大小。
空间复杂度为 O ( K ) O(K) O(K)


总结

  • 选择排序时间复杂度为 O ( N 2 ) O(N^2) O(N2),空间复杂度为 O ( 1 ) O(1) O(1)
  • 冒泡排序时间复杂度为 O ( N 2 ) O(N^2) O(N2),空间复杂度为 O ( 1 ) O(1) O(1)
  • 计数排序时间复杂度为为 O ( N + K ) O(N + K) O(N+K),K是相对范围(计数数组)的大小,空间复杂为 O ( K ) O(K) O(K)

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

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

相关文章

56页PPT | 大数据决策分析平台怎么建设?经典实践方案推荐

一、现状和目标 企业用户现状&#xff1a;数据分散&#xff0c;利用率低&#xff0c;业务需求变化快但IT响应慢。 问题&#xff1a;数据展示不及时、不准确&#xff0c;缺乏深入分析工具&#xff0c;报表制作效率低下。 目标&#xff1a;建设统一的数据整合平台&#xff0c;…

GS-SLAM论文阅读笔记--MM-Gaussian

介绍 这是一篇多模态的GS-SLAM&#xff0c;也已经被IROS2024录用。由于多传感器融合的GS-SLAM还是比较少的&#xff0c;所以应该仔细阅读一篇。 文章目录 介绍1.背景介绍2.关键内容2.1 跟踪2.2 重定位2.3 建图2.4总体流程 3.文章贡献 1.背景介绍 传统的SLAM方法往往受到地图…

Patch 35586779: WLS PATCH SET UPDATE 10.3.6.0.231017

以上补丁请自行去oracle官网下载&#xff0c;需要技术支持的请联系&#xff1a;https://item.taobao.com/item.htm?spm2013.1.w4023-17257245948.4.19611db9bzrKBx&id608692494369

软件质量保障:故障演练介绍

目录 背景&#xff1a;架构变化带来的问题 什么是故障演练 为什么需要故障演练 故障演练场景有哪些 不同演练类型和目标 如何对工具进行评估 功能评测项 告警评测项 观测指标评测项 总结 背景&#xff1a;架构变化带来的问题 随着架构越来越复杂、应用越来越多样&…

【设计模式】Template Method伪代码

1. 不好的代码 1.1 lib.cpp class Library{ public:void Step1(){//...}void Step3(){//...}void Step5(){//...} };1.2 app.cpp class Application{ public:bool Step2(){//...}void Step4(){//...} };int main() {Library lib();Application app();lib.Step1();if(app.Ste…

Python 从入门到实战12(流程控制-跳出循环语句)

我们的目标是&#xff1a;通过这一套资料学习下来&#xff0c;通过熟练掌握python基础&#xff0c;然后结合经典实例、实践相结合&#xff0c;使我们完全掌握python&#xff0c;并做到独立完成项目开发的能力。 上篇文章我们通过举例学习了流程控制语句中的循环语句。今天继续讨…

低代码开发:业务与技术的完美融合

正文&#xff1a; 随着数字化转型的加速&#xff0c;企业对应用软件的需求日益增长。然而&#xff0c;传统的开发方式往往费时费力&#xff0c;难以满足市场的快速变化。在此背景下&#xff0c;低代码开发平台应运而生&#xff0c;它们正逐步改变我们的工作方式&#xff0c;让…

从头开始学Spring—06初识声明式事务

目录 1.概念 1.1编程式事务 1.2声明式事务 2.JdbcTemplate 2.1准备工作 2.1.1加入依赖 2.1.2创建jdbc.properties 2.1.3配置Spring的配置文件 2.2测试 2.2.1在测试类装配JdbcTemplate 2.2.2测试增删改功能 2.2.3查询一条数据为实体类对象 2.2.4查询多条数据为一个…

LabVIEW灵活集成与调试的方法

在LabVIEW开发中&#xff0c;为了构建一个既便于调试又能灵活集成到主VI中的控制VI&#xff0c;开发者需要采用适当的编程方式和架构。常见的选择包括模块化设计、状态机架构以及事件驱动编程。这些方法有助于简化调试过程、提高系统的稳定性&#xff0c;并确保代码的重用性和可…

博客常见问题

hexo g 生成静态文件 hexo s 本地预览 hexo d 同步上传到git 1、输入hexo d &#xff0c;上传到git时&#xff0c;报错 看了下git的配置&#xff0c;没有问题&#xff0c;单机过去也能直接到我的git上 可能是传不过去&#xff0c;token的问题 最下面开发者设置&#xff0c;找到…

知网合作商AEPH出版,学生/教师均可投稿,优先录用教育社科领域,往期最快2周见刊

AEPH出版社旗下有5本学术期刊&#xff0c;专门出版自然科学、社会科学研究与教育领域论文的高影响力期刊&#xff0c;拥有正规ISSN号&#xff0c;出版类型涉及应用和理论方面的原创和未曾公开发表的研究论文&#xff0c;分配独立DOI号。AEPH作为中国知网&#xff08;CNKI&#…

当你忘记很久前的 DJANGO + UWSGI 项目是怎么启动的

在后端项目代码推到云服务器后&#xff0c;通常需要手动重启相关服务才会更新生效。 本人生产环境中用的是UWSGI服务器&#xff0c;更新步骤如下&#xff1a; 文章目录 UWSGI服务启动方式SYSTEMCTL 命令查看查看当前运行的 UWSGI 进程其他&#xff1a;查看 UWSGI 日志文件 重启…

Codeforces Round 970 (Div. 3)(ABCDEF)

Codeforces Round 970 (Div. 3) A:Sakurakos Exams 签到 题意:给定1,2的数量,判断是否能用加减符号使得这些1,2计算出0 void solve() {cin>>n>>m;if(n%2)cout<<"NO\n";else{if(m%20||n)cout<<"YES\n";else cout<<"…

H5咖啡品牌官网响应式HTML网站模板源码

源码名称&#xff1a;咖啡品牌官网响应式HTML网站模板源码 源码介绍&#xff1a;一款咖啡品牌官网响应式HTML网站模板源码&#xff0c;源码含有11个页面&#xff0c;可用于咖啡品牌官网。 需求环境&#xff1a;H5 下载地址&#xff1a; https://www.51888w.com/307.html

echarts 柱状图数据集结合堆叠图

效果图&#xff1a; 1.使用echarts的数据集&#xff0c;可以动态展示多组数据统计a,b,c,d…&#xff1b; 2.其中每个数据又使用堆叠图展示详细数据&#xff0c;比如a可以分成成功和失败的次数进行堆叠&#xff0c; 3.所有数据使用不同颜色进行区分&#xff0c;而每个数据的失败…

Makefile学习总结

Makefile学习总结 目录 Makefile学习总结1. Makefile介绍2. Makefile规则3. Makefile文件里的赋值方法4. Makefile常用函数4.1 字符串替换和分析函数4.2 文件名函数4.3 其他函数 5. Makefile使用示例6、多级目录通用Makefile Demo6.1 一般通用Makefile的设计思想6.2 Demo分析 参…

可筛选的课程表设计excel表格@在线写作共享表格课程表设计模板参考

文章目录 abstract表格任务1. 时间段与课次安排2. 课程种类多样3. 教师与教室安排4. 课程颜色编码5. 课表标注 参考方案:样式预览全表添加不影响筛选列的跨列显示内容方案1方案2(pass) 针对指定老师筛选并生成课表&#x1f47a;在线表格链接(wps)要点表格说明&#x1f47a;列交…

Pow(x, n)

优质博文&#xff1a;IT-BLOG-CN 题目 实现pow(x, n) &#xff0c;即计算x的整数n次幂函数&#xff08;即&#xff0c;xn &#xff09;。 示例 1&#xff1a; 输入&#xff1a;x 2.00000, n 10 输出&#xff1a;1024.00000 示例 2&#xff1a; 输入&#xff1a;x 2.100…

【spring】IDEA 新建一个spring boot 项目

参考新建项目-sprintboot 选择版本、依赖,我选了一堆 maven会重新下载一次么?

系统工程建模MBSE

################################# ############# 片段一 ############## ################################# 下图采用“V”模式显示了集成的基于模型的系统/嵌入式软件开发流程Harmony。左侧描述了自顶向下的设计流程,而右侧显示了自底而上的从单元测试到最终系统验收测试…