大家好，欢迎来到IT知识分享网。
插入排序
插入排序有可分为两种：直接插入排序 和 希尔排序
基本思想：
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其
关键码（key）
值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为
止，得到一个新的有序序列
。
把待排序的记录按其
关键码（key）
值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为
止，得到一个新的有序序列
。
直接插入排序
基本思想
当插入第
i(i>=1)
个元素时，前面的所有元素如
array[0],array[1],…,array[i-1]
已经排好序，此时用
array[i]
的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将
array[i]
插入，原来位置上的元素顺序后移。
i(i>=1)
个元素时，前面的所有元素如
array[0],array[1],…,array[i-1]
已经排好序，此时用
array[i]
的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将
array[i]
插入，原来位置上的元素顺序后移。
图片解析
依次类推……………………
代码参考
void InertSort(int* a, int n) { assert(a); for (int i = 0; i < n - 1; i++) { int tmp = a[i + 1]; int begin = i; while (begin >= 0) { if (a[begin + 1] < a[begin]) { a[begin + 1] = a[begin]; begin--; } else { break; } a[begin + 1] = tmp; } } }直接插入排序的特性总结：
1.
元素集合越接近有序，直接插入排序算法的时间效率越高
元素集合越接近有序，直接插入排序算法的时间效率越高
2.
时间复杂度：
O(N^2)
时间复杂度：
O(N^2)
以最坏情况看 每次会进行N次交换，且会进行N次
则时间复杂度为 N^2
3.
空间复杂度：
O(1)
，它是一种稳定的排序算法
空间复杂度：
O(1)
，它是一种稳定的排序算法
4.
稳定性：不稳定
稳定性：不稳定
希尔排序( 缩小增量排序 )
基本思想
希尔排序法又称缩小增量法。希尔排序法的基本思想是：
先选定一个整数（gap），把待排序文件中所有记录分成个
组（gap组），所有距离为的记录分在同一组内，
并对每一组内的记录进行排序
。然后，取，重复上述分组和排序的工
作。当到达
=1
时
（即直接插入排序时）
，所有记录在统一组内排好序
。
先选定一个整数（gap），把待排序文件中所有记录分成个
组（gap组），所有距离为的记录分在同一组内，
并对每一组内的记录进行排序
。然后，取，重复上述分组和排序的工
作。当到达
=1
时
（即直接插入排序时）
，所有记录在统一组内排好序
。
总结一下就是：分为预排序 和 排序 当gap>1 时 是预排序 == 1 时 相当于排序（直接插入排序）
如图分析
若 gap = N / 3 + 1
代码参考
void ShellSort(int* a, int n) { int gap = n; //不能 == 1 若== 1 1 / 3 + 1 = 1 进入死循环 while (gap > 1) { gap = gap / 3 + 1; for (int i = 0; i < n - gap; i += gap) { int tmp = a[i + gap]; int end = i; while (end >= 0) { if (a[end + gap] < a[end]) { a[end + gap] = a[end]; end -= gap; } else { break; } a[end + gap] = tmp; } } } }希尔排序的特性总结：
1.
希尔排序是对直接插入排序的优化。其中也利用了直接插入排序.
希尔排序是对直接插入排序的优化。其中也利用了直接插入排序.
2.
当
gap > 1
时都是预排序，目的是让数组更接近于有序。当
gap == 1
时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
当
gap > 1
时都是预排序，目的是让数组更接近于有序。当
gap == 1
时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3.希尔排序的时间复杂度不好计算，因为
gap
的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
gap
的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定
大致为 O（logN^1.25 —– 1.6N^1.25)
简单粗略计算希尔排序的时间复杂度
以 gap = N / 3
总体大致
可以看作 gap 组 每组 3 个数据
可以看作 gap 组 每组 3 个数据
则 第一趟预排序
最差的情况 会走 （1+2）* N/ 3 == N
第二趟预排序
最差情况 会走 （1 + 2 + …+ 8）* N / 9 == 4N
………………
最后一趟 也是直接插入排序，但是经过预排序，数据已经接近有序；则，最后一趟 会走 N
图大致是这样的，因此可以大致认为 希尔排序的 时间复杂度为
O（logN^1.25）
O（logN^1.25）
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/136157.html
