国外网站设计的网站,北京 做网站,关键词优化排名软件哪家好,从化做网站建设目录
前言
简介
基本思想 1.直接插入排序 2.希尔排序
代码实现 1.直接插入排序 2.希尔排序
总结
1.时空复杂度
2.稳定性
尾声 前言 排序(Sorting) 是计算机程序设计中的一种重要操作#xff0c;它的功能是将一个数据元素#xff08;或记录#xff09;的任意序列它的功能是将一个数据元素或记录的任意序列重新排列成一个关键字有序的序列。所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 排序算法就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。 简介 所谓排序算法即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则体现出一定的规律因此经处理后的数据便于筛选和计算大大提高了计算效率。对于一个排序算法的优劣我们需要从它的时间复杂度、空间复杂度和稳定性三个方面来考虑。什么叫稳定性呢即当两个相同的元素同时出现于某个序列之中则经过一定的排序算法之后两者在排序前后的相对位置不发生变化。换言之即便是两个完全相同的元素它们在排序过程中也是各有区别的。 本篇文章讲述的是排序算法中的插入排序其中包含了两种排序算法分别是直接插入排序和希尔排序下面将会一一为大家详细介绍。用升序进行讲解 插入排序算法是基于某序列已经有序排列的情况下通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端开始执行即要插入序列中的元素最先和有序序列中最大的元素比较若其大于该最大元素则可直接插入最大元素的后面即可否则再向前一位比较查找直至找到应该插入的位置为止。
基本思想 插入排序的基本思想是每次将1个待排序的记录按其关键字大小插入到前面已经排好序的序列中寻找最适当的位置直至全部记录插入完毕。 1.直接插入排序 下面我们首先来看一看直接插入算法的动图演示 看了上图之后我们可以得知直接插入排序是在一个给定的数组中我们从第二个元素开始与之前的元素一一进行比较 · 若是该位置的元素小于前一个元素那么就将该位置元素与更前一位的元素再次进行比较直到前面没有元素那么此时该元素就放在数组的首位。 · 若是该位置的元素大于或者等于前一个元素那么就把该位置的元素放到前一个元素的后面具体的方式在下面的代码实现中进行讲解。 这就是直接插入排序的具体思路有了它我们便可以写出我们的直接插入排序算法。 2.希尔排序 当数组中的元素越接近有序时直接插入排序算法的时间效率越高但是当数组中的元素越不接近有序特别是倒序时此时要使元素正序排列使用直接插入算法的时间效率就非常低了那我们能不能对直接插入算法进行一些优化呢? 答案是可以的。既然我们说当元素越有序时的时间效率越高那我们可以把元素先分为若干份先将这些部分使用直接插入算法变得有序后再去整体进行直接插入排序算法从而达到目的这就是希尔排序。 希尔排序法又称缩小增量法。希尔排序算法的基本思想是先选定一个整数记为num用num计算出一个距离gap n / num 1n为元素总数把待排序元素分成各组所有的距离相等的记录分在同一组内并对每⼀组内的元素进行排序然后gap gap / num 1得到下⼀个距离再将数组分成各组进行直接插入排序当gap 1时就相当于直接插入排序。举个例子此时我们的num取2先看下面图片 上图中n 10我们选取一个整数2计算得到第一个距离gap 10 / 2 1 5此时第一个元素9和与他距离为5的第六个元素4为一组6 5 11由于数组中只有十个元素因此第一组中只有两个元素9和4后面以此类推。将这些组分别进行直接插入排序后我们更新gap gap / 2 1 2此时相距为2的元素为一组再次对每一组进行直接插入排序直到gap 1此时再进行直接插入排序这样我们就完成了希尔排序算法。当 gap 1 时都是预排序目的是让数组更接近于有序。当 gap 1 时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。其中整数num的取值有各种各样不过一般来说我们的num 3。
代码实现 1.直接插入排序 先看代码
void Insert_sort(vectorint a)
{//从第二个元素开始进行排序一直到最后一个元素for (int i 1; i a.size(); i){//用end记录需要排序的元素的前一个元素的下标tmp用来保存当前需要排序的元素int end i - 1, tmp a[i];//用while循环对a[i]进行排序while (end 0){//end位置的元素大于tmp(也就是a[i])时把end位置的元素复制到end 1的位置上并且end--继续进行比较if (a[end] tmp){a[end 1] a[end];end--;}//因为我们插入一个新的元素时它前面的元素都已经是有序的因此当end位置的元素不大于tmp时循环结束else break;}//当循环结束时由于end进行一次减一操作所以该元素所处的正确位置为end 1a[end 1] tmp;}
} 解析通过注释相信大家基本上已经能够了解代码的意思接下来我会通过画图的方式再给大家进行更加详细的介绍 通过上面的图相信大家对直接插入排序已经十分了解了。 2.希尔排序 在前面已经为大家详细的介绍希尔排序的过程下面的代码大家可以参考一下
void Shell_sort(vectorint a)
{//先将元素个数赋值给gap这样在循环中可以很好的控制gapint gap a.size();while (gap 1){gap gap / 3 1;//我们可以不必一组一组的进行排序而是i走到哪一组就对哪一组的元素进行排序这样可以节省一层for循环for (int i gap; i a.size(); i){//因为此时的每一组的元素相距为gap因此我们从gap位置开始枚举即每一组的第二个元素//此时要找到前一个元素的下标end需要用i - gapint end i - gap, tmp a[i];while (end 0){if (a[end] tmp){//与上面同理我们每组中元素相距gap因此end gap才是end位置后的那一个元素位置a[end gap] a[end];end-gap;}else break;}//与上面同理a[end gap] tmp;}}
} 注 上述两种排序的算法博主用的是从第二个元素去找前一个元素大家也可以反过来例如在直接插入排序算法中for循环改为 for(int i 0; i a.size() - 1; i) 此时 end itmp a[i 1]。根据个人习惯选择即可。 总结
1.时空复杂度 简单分析我们可以得到直接插入排序算法的时间复杂度和空间复杂度 直接插入排序 时间复杂度O(N ^ 2) 空间复杂度O(1) 对于希尔排序来说对于整数num的取值不同其时间复杂度也不同导致很难去计算时间复杂度因此很多书中给出的希尔排序的时间复杂度都不固定。《数据结构(C语言版)》--- 严蔚敏书中给出的时间复杂度为 希尔排序 时间复杂度O(nlogn ~ n ^ 2) 空间复杂度O(1) 希尔排序算法是在直接插入排序算法的基础上进行改进而来的综合来说它的效率肯定是要高于直接插入排序算法的。
2.稳定性 在排序算法中我们不光要关注算法的时空复杂度还在看看算法的稳定性什么是稳定性呢 稳定性是假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。 执行过程中若遇到和插入元素相等的位置则将要插人的元素放在该相等元素的后面因此插入该元素后并未改变原序列的前后顺序。我们认为插入排序是一种稳定的排序方法。但是对于希尔排序来说因为对数据进行了分组因此在排序过程中会出现相同的元素不在同一组中导致其相对位置发生了改变因此我们说希尔排序是不稳定的。 直接插入排序 稳定 希尔排序 不稳定 尾声 若有纰漏或不足之处欢迎大家在评论区留言或者私信同时也欢迎各位一起探讨学习。感谢您的观看
