数据结构之内部排序--排序的基本概念_Kun_beim的博客-程序员秘密

技术标签: 排序  数据结构  知识基础  

排序

有n个记录的序列 R1,R2,...,Rn R 1 , R 2 , . . . , R n ,其相应的关键字的序列是 K1,K2,...,Kn K 1 , K 2 , . . . , K n ,相应的下标序列1,2,…,n。通过排序,找出当前的下标序列1,2,…,n的一种排列 p1,p2,...pn p 1 , p 2 , . . . , p n ,使得相应的关键字满足如下的非递减(或者非递增)关系: Kp1<=Kp2<=...<=Kpn K p 1 <= K p 2 <= . . . <= K p n ,这样就得到一个按关键字乐有序的记录序列。

内部排序与外部排序

根据排序时数据所占用的存储器的不同,可以将排序分为两大类。一类是整个排序过程完全在内存中进行,称为内部排序;另一类是由于待排序记录数据量太大,内存无法容纳全部数据,排序需要借助外部存储设备才能完成,称为外部排序

主关键字与次关键字

上面所说的关键字 Ki K i 可以是记录 Ri R i 的主关键字,也可以是此关键字,甚至可以时记录中若干数据項的组合。若 Ki K i 是主关键字,则任何一个无序的序列经排序后得到的有序序列是唯一3的;若 Ki K i 是次关键字或是记录中若干数据項的组合,得到的排序结果可能是不唯一的。

排序的稳定性

若在排序前的的队列中 Ri R i 领先于 Rj R j 其中 i<j i < j ,经过排序后得到的序列中 Ri R i 仍然领先于 Rj R j ,则称排序方法是稳定的。反之领先关系在排序时发生变化,则称排序方法是不稳定的
无论是稳定的还是不稳定的算法,都可以很好的排序,只不过在某些时候我们需要让他的顺序保持不变。

常用排序的基本类型

1.插入类排序

-直接插入排序
-折半插入排序
-希尔排序
排序算法 稳定性 时间复杂度 最好情况 最坏情况 空间复杂度
直接插入 稳定 O(n2) O ( n 2 ) O(n) O ( n ) O(n2) O ( n 2 ) O(1) O ( 1 )
折半插入 稳定 O(n2) O ( n 2 ) O(nlogn) O ( n l o g n ) O(n2) O ( n 2 ) O(1) O ( 1 )
希尔排序 不稳定 O(n1.5) O ( n 1.5 ) O(1) O ( 1 )

2.交换类排序

-冒泡排序
-快速排序
排序算法 稳定性 时间复杂度 最好情况 最坏情况 空间复杂度
冒泡排序 稳定 O(n2) O ( n 2 ) O(n) O ( n ) O(n2) O ( n 2 ) O(1) O ( 1 )
快速排序 不稳定 O(nlog2n) O ( n l o g 2 n ) O(nlog2n) O ( n l o g 2 n ) O(n2) O ( n 2 ) O(log2n) O ( l o g 2 n )

3.选择类排序

-简单选择排序
-树形选择排序
-堆排序
排序算法 稳定性 时间复杂度 最好情况 最坏情况 空间复杂度
简单选择排序 不稳定 O(n2) O ( n 2 ) O(n2) O ( n 2 ) O(n2) O ( n 2 ) O(1) O ( 1 )
树形选择排序 稳定 O(nlog2n) O ( n l o g 2 n ) O(nlog2n) O ( n l o g 2 n ) O(nlog2n) O ( n l o g 2 n ) O(n) O ( n )
堆排序 不稳定 O(nlog2n) O ( n l o g 2 n ) O(nlog2n) O ( n l o g 2 n ) O(nlog2n) O ( n l o g 2 n ) O(1) O ( 1 )

4.归并排序

-归并排序
排序算法 稳定性 时间复杂度 最好情况 最坏情况 空间复杂度
归并排序 稳定 O(nlog2n) O ( n l o g 2 n ) O(nlog2n) O ( n l o g 2 n ) O(n) O ( n )

5.分配类排序

-多关键字排序
-链式基数排序

总结

数据结构在计算机世界里承担很重要的角色。就例如十万个数排序快速排序的时间在0.5s左右(Python编写),而有的排序则需要十几分钟,可想而知,在现在大数据时代,没有一个好的数据结构,没有一个好的算法,对生产来说,十分不利。其次数据结构也大大的提升了自己的逻辑判断水平。对提升自己的编码水平,有很大的帮助,对自己以后研究算法,也会打下坚实的基础。或许这些算法以后用不到,但是我知道,其他复杂的算法都是在基础的算法之上建立的,也应当对这些基础算法进行了解。
此篇文章参考
【1】耿国华,张德同,周全名等.数据结构用c语言描述【M】.第二版.北京:高等教育出版社.2016.

有什么问题请联系我

QQ:3116316431 (请附上信息)
E-mail:[email protected]

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_33571896/article/details/79510294

智能推荐

Qt6.2.3使用vscode编写Qt项目_vscode 中编写qt_RiCoCoSoul的博客-程序员秘密

前言关于怎么下载安装Qt6.0和vscode这里就不讲了,网上的教程多如牛毛。再次说明此教程只适合有Qt基础和Cmake基础的人!!!测试环境Qt版本:6.2.3vscode:1.63.2编译器:MinGW64-GCC-11.2设置找到Qt安装目录找到路径目录*:\Qt\6.2.3\mingw_64(此路径包含了库文件)和*:\Qt\Tools\mingw900_64\bin(Qt自带的MinGw编译器)设置环境变量这里有两种方法一是直接使用Qt内置的工具提供的MinGW,或者.

启动Vue项目执行npm run serve报错npm ERR! [email protected] serve: `vue-cli-service serve --open`_会哭的孩子有奶喝的博客-程序员秘密

问题想启动一个Vue项目,在终端输入npm run serve后报错:解决方法参考 https://blog.csdn.net/CC1991_/article/details/108152325 ,发现很容易解决,只需要先把项目里面的node_modules文件夹直接删掉,再执行命令npm install,安装完毕之后,再次在终端里面输入命令行:npm run serve 回车,就不再报错。总结:启动Vue项目执行npm run serve报错首先删掉node_modules文件夹然后执行

mac清理系统存储之xcode_|刘钊|的博客-程序员秘密

1、iOS DeviceSupport --~/Library/Developer/Xcode/iOS DeviceSupport竟占最多!我把12以下的都删除了。不过这个可重新生成!在连接旧设备调试时,会重新自动生成。2、Archives --~/Library/Developer/Xcode/Archives这个不可恢复;Adhoc或者App Store版本会被删除。建议备份...

百度搜索 推出“蝶变行动”:新站支持力度大_Eddiewing的博客-程序员秘密_百度发布"蝶变行动"云财经

百度搜索推出的系列活动”蝶变行动”,这次活动对新站支持的力度特别大。百度举了一个案例:界面新闻,流量增长37%,UV增长68%,接口人也因此晋升为网站合伙人,界面新闻参与蝶变活动获奖后,知名度大幅提升,流量也相应上涨10%。优质新站在百度站长平台验证后,填写备案号即可列入”新站保护计划”候选列表,如被选中,将被百度搜索一周内收录首页及内页。优质站点、资源提供方还将获得百度搜索网站排序、阿拉丁合...

KDD2020|基于邻域的异构图交互推荐模型_EdmundYan的博客-程序员秘密_基于邻域的推荐

An Efficient Neighborhood-based Interaction Model for Recommendation on Heterogeneous Graph

CentOS7.2安装mysql数据库问题记录_小屁孩~~的博客-程序员秘密

yum install mysql 安装mysql数据库mysql安装后出现下面问题CentOS7.2安装mariadb-server,解决Failed to start mysqld.service: Unit not foundsystemctl start mysql.service要启动MySQL数据库是却是这样的提示Failed to start mysqld...

随便推点

上海交通大学计算机科学导论,数模之旅——上海交通大学“高教社杯”获奖团队的追寻之路..._好爱赵辰龙的博客-程序员秘密

2018年“高教社杯”全国大学生数学建模竞赛(CUMCM,简称国赛)于11月10日揭晓奖项,上海交通大学电子信息与电气工程学院计算机系高晓沨老师指导的学生刘一鸣(电院计算机系)、王超玥(致远学院物理方向)、赖鹏程(致远学院物理方向)获本科组唯一的最高奖项“高教社杯”(概率0.0026%)。这是上海交大、也是上海赛区在国赛开赛27年、设置最高奖项20年以来首次获此殊荣,实现了上海交大在该项赛事的历史...

css禁止界面选中文字 无效,css实现禁止页面文字被选中功能_Xy Chen的博客-程序员秘密

通过css实现页面文字不能被选中(推荐教程:CSS教程).cannotselect {-webkit-touch-callout: none;-webkit-user-select: none;-moz-user-select: none;-ms-user-select: none;user-select: none;}css介绍user-select说明控制选取能否被选择.该特性是非标准的,请尽...

如何在Ruby中使用数组方法_cukw6666的博客-程序员秘密

介绍 (Introduction)Arrays let you represent lists of data in your programs. Once you have data in an array, you can sort it, remove duplicates, reverse its order, extract sections of the array, or sea...

js实现倒数计时器功能_微也的web的博客-程序员秘密

正在学习js的路程中,今天知道了如何实现简单倒数计时的功能,比如说,可以用于设计考试定时功能,不是从0开始计时,而是从最后的规定时长开始,如02:00:00一直到00:00:00……现在开始学习,未设置天数的功能首先,我们要明白几个方法,1. setInterval( )方法可以按照指定的周期(以毫秒计)来调用函数或计算表达式,如setInterval(function(){}, 10

运动控制_Angeras的博客-程序员秘密_ez 信号

**运动控制:**初始化控制卡(d2210_board_init)函数 ==》 脉冲模式设置(d2210_set_pulse_otmode)函数 中断控制函数(若有) &lt;&lt;——&gt;&gt;用户定义中断程序运 动过 运动函数调用(d2210_t_vmove)函数程 运动状态检测(d2210_check_done)函数处 理...

推荐文章

热门文章

相关标签