龙华网站制作公司,大连在哪个省市,wordpress 一直加载插件,东莞网站建设百度地图千万不要因为一件事不会做而失去信心#xff0c;你又不是只有这一件事不会#xff0c;你还有很多呢
一、插入排序
1.直接插入排序 InsertSort
1.1 基本思想
1.2 实现原理
1.3 代码实现
1.4 直接插入排序的特性总结
2.希尔排序 ShellSort
2.1 基本思想
2.2 实现原理 … 千万不要因为一件事不会做而失去信心你又不是只有这一件事不会你还有很多呢
一、插入排序
1.直接插入排序 InsertSort
1.1 基本思想
1.2 实现原理
1.3 代码实现
1.4 直接插入排序的特性总结
2.希尔排序 ShellSort
2.1 基本思想
2.2 实现原理
2.3 代码实现
2.4希尔排序的特性总结
二、完结撒❀
–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀-正文开始-❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–❀–
一、插入排序
1.直接插入排序
1.1 基本思想
直接插入排序是一种简单的插入排序法其基本思想是
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列。
实际中我们玩扑克牌时开始出牌前我们总先把牌都按照大小排列一边这就用了插入排序的思想
1.2 实现原理
下面以数组实现升序为例
总体是按照·数组下标由小到大进行排序
对一个数组arr进行排序从第一个位置下标为0开始与下标为1进行比较
如果arr[0]arr[1]将arr[0]后移至arr[1]的位置再将arr[1]插入arr[0]的位置就完成了排序再继续向后读取排序即可。 如果arr[0]arr[1]即为升序继续向后读取排序即可。
当插入到第ii0个元素时前面的arr[0],arr[1]…arr[i-1]都已经排好序此时将arr[i]对应数值与arr[i-1],arr[i-2]…对应的数值依次进行排序比较大于arr[i]的数值依次向后移动一个数据位置大小(假设arr[i-1]大于arr[i],就将arr[i-1]后移止arr[i]的位置)arr[i]继续向前进行比较直到遇到比arr[i]小的数时将arr[i]插入到其前面位置即可
按照数组下标顺序以此执行上面操作直到将数组中最后一个数据排完为止即可实现升序。
动态图解:
1.3 代码实现
//时间复杂度
//最坏情况O(N^2),逆序
//最好情况ON
void InsertSort(int* a, int n)
{assert(a);for (int i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp){a[end 1] a[end];--end;}else{break;}}a[end 1] tmp;}
}1.4 直接插入排序的特性总结
1. 元素集合越接近有序直接插入排序算法的时间效率越高
2. 时间复杂度O(N^2)
4. 空间复杂度O(1)它是一种稳定的排序算法
5. 稳定性稳定
2.希尔排序 ShellSort
2.1 基本思想
希尔排序法又称缩小增量法。希尔排序法的基本思想是
先选定一个gap整数把待排序文件中所有记录分成gap个组所有距离为gap的整数记录分在同一组内并对每一组内的记录进行排序。然后减小gap重复上述分组和排序的工作。当到达gap1时所有记录在统一组内排好序。 2.2 实现原理
希尔排序相当于是对直接插入排序进行了优化 直接插入排序就相当于把gap直接当作1进行插入排序而希尔排序不同
希尔排序分为预排序和最终排序两部进行且开始gap等于数组数据个数ngap减小到1之前所进行的排序都为预排序只有最后gap1时的排序为最终排序
希尔排序之所以快是预排序在起作用预排序的目标是让整体数组接近有序而总体预排序消耗的时间又很少其对最终排序的使用时间有很大增益效果
注意这里以gap / 2为例进行动态图解 动态图解
2.3 代码实现
注意这里代码是以gap gap/31为例时间复杂度为O(N^1.3)。具体说明在特性里面
//希尔排序 时间复杂度ON^1.3
//欲排序 目标接近有序
void ShellSort(int* a, int n)
{assert(a);int gap n;while (gap 1){gap gap/3 1;for (int j 0; j gap; j){for (int i j; i n - gap; i gap){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}a[end gap] tmp;}}}}
}2.4希尔排序的特性总结
1. 希尔排序是对直接插入排序的优化。
2. 当gap 1时都是预排序目的是让数组更接近于有序。当gap 1时数组已经接近有序的了这样就会很快。这样整体而言可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在一些树中给出的希尔排序的时间复杂度都不固定 《数据结构-用面相对象方法与C描述》— 殷人昆 因为咱们的gap是按照Knuth提出的方式取值的而且Knuth进行了大量的试验统计我们暂时就按照ON^1.3来算。
4.稳定性不稳定。
二、完结撒❀
如果以上内容对你有帮助不妨点赞支持一下以后还会分享更多编程知识我们一起进步。 最后我想讲的是据说点赞的都能找到漂亮女朋友❤
