个人站长还有什么类型的网站可以做,沈丘网站建设,北京3d效果图制作公司,2022年域名申请时间排序算法是数据结构相关知识中非常重要的一节#xff0c;相信很多小伙伴对这部分知识一知半解。那么接下来#xff0c;小编就要带领大家一起来进行对排序算法的深入剖析学习#xff0c;希望本篇文章能够使你有所收获#xff01;
一.常见的排序算法 排序算法有很多种#… 排序算法是数据结构相关知识中非常重要的一节相信很多小伙伴对这部分知识一知半解。那么接下来小编就要带领大家一起来进行对排序算法的深入剖析学习希望本篇文章能够使你有所收获
一.常见的排序算法 排序算法有很多种为了使同学们有一个比较系统的了解小编找了一张图片用以加深同学们的理解 那么接下来我们就对上图所提到的排序算法进行一一细致的学习吧
二..插入排序 插入排序就是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为 止得到一个新的有序序列 。 我们平时玩扑克牌就是运用到了插入排序的思想。 代码展示 时间复杂度问题
插入排序最好的时间复杂度是O(N) 当数组元素顺序时
最坏时间复杂度是是O(N^2) 当数组元素逆序时 三.希尔排序 只有掌握好插入排序才会有可能掌握希尔排序。希尔排序是建立在插入排序的基础之上。
希尔排序分为两步1.预排序让数组接近有序 注意预排序是多次 2.插入排序
其中预排序是将数组分为gap组每一组中的数是原数组间隔了gap个数而划分的间隔为gap亦将数组划分为gap组。
希尔排序的特性总结
1. 希尔排序是对直接插入排序的优化。
2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就 会很快。这样整体而言可以达到优化的效果。我们实现后可以进行性能测试的对比。
代码展示 为了方便同学们理解代码老师做了详细的批注 时间复杂度问题分析
希尔排序的复杂度问题分析非常复杂我们不做过多研究我们只告诉大家希尔排序的平均时间复杂度 O(N^1.3)
四.堆排序 堆排序相信大家都不陌生早在堆的实现中我们就已经涉及到了堆的相关知识那么我们就一起来温习一下吧 堆排序包括两步 1.向下调整建堆 2.堆排序
代码展示
堆排序示意图 注意升序建大堆 降序建小堆 本代码建的是大堆 堆排序具有实践意义堆排序使用堆来选数效率就高了很多。
堆排序时间复杂度 O(N*logN 五.选择排序
每一次从待排序的数据元素中选出最小或/和 最大的一个元素存放在序列的起始位置直到全部待排序的 数据元素排完 。
代码展示 时间复杂度 ON^2
本代码是优化后的选择排序的代码我们直接同时寻找最小和最大的两个元素分别放在序列的最左边和最右边。
六.冒泡排序 冒泡排序相信大家都不陌生那么话不多说我们直接上代码来展示一下 这里我们展示的代码是优化版本的冒牌排序设立了flag 放置有序情况下效率降低
冒泡排序的时间复杂度:
最坏情况下时间复杂度O(N^2)
最好情况下时间复杂度O(N) 数组顺序
七.快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为 任取待排序元素序列中 的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
一递归算法
1.霍尔版本 代码展示 2.挖坑法 代码展示 3.前后指针法 代码展示 快速排序的时间复杂度 O(NlogN 每一层的次数N*层数logN
注意
以上代码均是优化后的快速排序算法。快速排序算法的优化
1.三数取中选择keyi值避免有序情况下效率退化O(N*N
2.小区间递归优化当要排序个数小于10时我们可以采用插入排序。其目的是不再进行递归分割减小递归深度防止溢出。
二非递归算法
光是掌握快速排序的递归算法是远远不够的我们还需要掌握它的非递归算法
我们借助栈实现了快速排序的非递归算法。
八.归并排序 归并排序简而言之我们将其总结为“分而治之”。分即将待排数组分成一个个有序的序列治即排序将这些有序的序列合并得到完全有序的数组。
一递归算法
相信借助下图你可以对归并排序有一个更深入的理解 代码展示 归并排序的时间复杂度分析 O(N*logN 每一层的次数N*层数logN
归并排序的空间复杂度 O(N) 开辟了一个tmp数组 二非递归算法
我们可以借助栈来实现归并排序的非递归算法
注意这里要谨防数组边界越界问题。
九.计数排序
计数排序是非比较排序的一种它的实现原理非常的巧妙。
1.建立count数组统计元素出现的次数
2.根据元素出现的次数回馈到原数组排序 代码展示 本着减少空间浪费的原则本代码采用了相对映射的方法。即设立一个range变量。在计数的时候count的下标写为a[i]-min,在排序的时候a[j]的值赋值为imi。count的下标存储的就是数值。
计数排序适用于数据较为集中且数据为整数的情况。
计数排序的时间复杂度 OMAX(rangeN
计数排序的空间复杂度 Q(N) 开辟了一个数组用以计数
十.排序算法的稳定性分析
稳定性
假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排 序算法是稳定的否则称为不稳定的。
那么下面这个表格可以帮你快速梳理一下排序算法的相关性质 今天关于排序算法的讲解就到这里相信坚持学习到这里的小伙伴一定收获满满如果有相关问题欢迎大家私信留言小编一定竭尽所能为大家指点迷津我们下次再会
