数据结构排序算法物理实现 数据结构和算法-3-排序算法
人气:487 ℃/2024-02-19 17:39:43
上一篇介绍了最基本的数据存储结构 -- 数组,既然提到数组就难免要说一下排序了,由于排序是一个比较重要的部分,在一些面试中问到算法基础也经常会问到,而且本篇会介绍8种常见的排序算法,篇幅较大,所以将排序单独分离出来作为一篇文章。
交换数组元素在介绍排序算法前,先写一个交换数组中任意两个元素的方法,供下面各排序算法进行调用
还有一个便于我们查看结果的打印方法,虽然没有什么技术含量,不过还是顺便写出来吧:
下面正式开始介绍排序算法:
8种常见排序算法:1. 简单选择排序每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完,它需要经过n-1趟比较。代码实现如下:
2. 冒泡排序依次比较两个相邻的元素,将值大的元素交换至右端。代码实现如下:
3. 直接插入排序将待排序的数据元素按其关键字值的大小插入到前面的有序序列中。代码如下:
3.2. 折半插入排序又叫二分插入排序, 即寻找插入位置时,用二分法寻找
4. 归并排序- 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。
- 将两个有序表合并成一个有序表,称为二路归并。
- 优点:效率较高,时间复杂度为O(NlogN), 而冒泡,插入,选择的时间复杂度都是O(NN)
- 缺点:需要在存储器中有一个大小等于被排序数组的中介数组,就是用空间换时间
- 核心:归并两个有序数组
代码实现如下:
5. 希尔排序:- 又叫最小增量排序,基于插入排序,时间复杂度O(N*(logN)2),效率不算太高,适于中等大小数组,但是非常容易实现,代码既简单又短。
- 原理:通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项大跨度地移动,当这些数据项排过一趟序之后,希尔排序算法减小数据项的间隔再进行排序,依次进行下去,进行这些排序时的数据项之间的间隔被称为增量,习惯上用字母h来表示这个增量。
- Shell排序是不稳定的,它的空间开销是O(1),时间开销估计在O(N3/2)~O(N7/6)之间
- Shell原稿中建议初始间距为N/2,但这被证明不是最好的数列,会使时间复杂度降低到O(N*N)
- 后又衍生出N/2.2的优化,其中的关键点在于间隔数列元素的互质性,这使得每一趟排序更有可能保持前一趟排序已排好的效果
代码实现如下:
6. 快速排序:- 划分:快速排序的根本机制, 把数据分为两组,使所有关键字大于特定值的数据项在一组,小于的在另一组, 如全班学生的考试成绩以及格线60划分。
- 时间复杂度: O(N*logN)
- 原理:把一个数组分为两个子数组(划分), 然后递归的调用自身,为每个子数组进行快速排序。
- 效率: 影响效率的关键点在于枢纽的选择(即上面划分中的关键字,例子中的60分),应尽量保证两个子数组的大小接近
- 通常来说关键字可以选择任意一项数据,一般选择头尾arr[0]或arr[arr.length-1],但是这样做算法的性能是不稳定的,因为待排序的数组可能是有序的,会使时间复杂度降到O(N*N)
- 理想中的枢纽应为待排序数组的中值数据项, 但是选取中间值比较麻烦,所以一个折中的办法就是'三项数据取中'划分,即数组头,尾,中,三个数据项的中值作为枢纽, 这样既简单又可以避免选择到最大或最小值作为枢纽的情况。
1. 常规实现:以起始(或结尾)索引为分界点
2. 三项数据取中实现快速排序
7. 基数排序- 基数:一个数字系统的基,10是十进制系统的基数,2是二进制系统的基数
- 把数值拆分2位数字位,对每一位进行排序
- 缺点:以空间换时间
代码如下:
8. 堆排序代码如下:
其中VectorHeap是一个自己写到堆的实现类,关于堆到后面介绍到堆时再详细介绍,下面先给出其具体实现类的代码
其中的Node节点类实现如下:
我是今阳,如果想要进阶和了解更多的干货,欢迎关注公众号”今阳说“接收我的最新文章- 12-17贵州各县人口排名表:贵州省各县,县级市区
- 02-08国内最牛的超跑展厅排名 国内五大顶级超跑俱乐部
- 03-15大学生学非遗怎么样?大学毕业学木匠你怎么看
- 03-30iphonex官方壁纸超清,IphoneX壁纸高清无水印,学会了不打扰
- 03-03甘肃省内大部晴雨:甘肃多地降雨再起部分地方降温明显
- 04-19高手的技术与高手的心态,小胜在于技巧中胜在于实力
- 12-01八里沟冬季景区好玩吗?冰封,的八里沟这才是冬天应有的美丽
- 02-25手帐所有的素材名字 手帐素材文字背景图有你爱豆吗
- 11-27h5游戏什么情况下会关服?最近H5游戏的iOS联运渠道事有
- 12-03冰冻的海鲜怎么处理才好吃?朝阳市场海鲜忙鲜美就靠这招
- 02-02农村大鱼的做法:老一辈的大鱼是这样煮的
- 03-20东部新区2025年世运会有哪些项目?北辰大道或将成全运会最新门面路
- 05-15虎牙旺仔和荒神的矛盾是什么?虎牙主播旺仔开启solo挑战
- 02-17最强nba字母哥错位优势晋升,表哥,字母哥能否成新版
- 05-09多哈机场有什么值得买的?4大洲10国机场扫货攻略不买就吃亏
- 04-21沉香价格一般是多少 沉香一般什么价位
热门
推荐
- 1巨难的脑筋急转弯题目143
- 2爸妈写给孩子的一封信480
- 3最经典的幽默个性签名322
- 4铁路论文的参考文献著录格式要求431
- 5吃完鸡蛋后不能做的事情205
- 6思念一个人的短句子411
- 7十大仿古砖品牌排名榜单401
- 8冬瓜海带汤功效与作用,冬瓜海带汤的坏处270