一、直接插入排序
原理
直接插入排序是一种最基本的插入排序方法，能够将第i个记录插入到前面i-1个已排好序的记录中，具体插入过程如下所示。
将第i个记录的关键字Ki 顺序与其前面记录的关键字Ki-1 , Ki-2 , …, K1 进行比较，将所有关键字大于Ki 的记录依次向后移动一个位置，直到遇见关键字小于或者等于Ki 的记录Kj 。此时Kj 后面必为空位置，将第i个记录插入空位置即可。完整的直接插入排序是从i=2开始的，也就是说，将第一个记录作为已排好序的单元素子集合，然后将第二个记录插入到单元素子集合中。将i从2循环到n，即可实现完整的直接插入排序。
下图给出了一个完整的直接插入排序实例。图中大括号内为当前已排好序的记录子集合：
直接插入排序.png
假设待排序记录保存在r[1..n]中，我们需要设置一个监视哨r[0]，使得r[0]始终保存待插入的记录，这样的目的是能够提高效率。此处设置监视哨的目的有如下两个作用：
- 备份待插入的记录，以便前面关键字较大的记录后移。
- 防止越界，这一点与顺序查找法中监视哨的作用相同。
动画演示过程
直接插入排序.gif
Go语言描述
插入排序思想的核心就是局部有序，对于样本小且基本有序的时候效率不错，实战可用。
- 平均时间复杂度：O(n²)
- 最坏时间复杂度：O(n²)
- 最好时间复杂度：O(n)
- 空间复杂度：O(1)
- 稳定性：稳定
直接插入排序实现：
每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。
func InsertionSort(list []int) {
// 获取数组长度
l := len(list)
// 2.外层循环从1开始，依次遍历到最后
for i := 1; i < l; i++ {
// 3.记录当前轮次选出的元素的位置
tmp := list[i]
j := i
// 4.内层循环不确定循环次数，依次比较前面的局部有序元素
for j > 0 && list[j-1] > tmp {
fmt.Print(j, " ") // 标记移动元素的次数
list[j] = list[j-1]
j--
list[j] = tmp
}
// fmt.Println()
}
}
直接插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n);在最坏情况下，时间复杂度依然为O(n2)。但是在数组元素随机排列的情况下，插入排序还是要优于冒泡排序和直接选择排序这两种排序的。
直接插入排序算法并不是任意使用的，它比较适用于待排序记录数目较少且基本有序的情形。当待排记录数目较大时，直接使用插入排序会降低很多性能。针对上述情形，如果硬要使用插入排序算法，则可以对直接插入排序进行改进。具体改进方法是在直接插入排序法的基础上，减少“比较关键字”和“移动记录”这两种操作的次数。
二、希尔排序
原理
希尔排序又被称为缩小增量排序法，这是一种基于插入思想的排序方法。希尔排序利用了直接插入排序的最佳性质，首先将待排序的关键字序列分成若干个较小的子序列，然后对子序列进行直接插入排序操作。经过上述粗略调整，整个序列中的记录已经基本有序，最后再对全部记录进行一次直接插入排序。在时间耗费上，希尔排序与直接插入排序法相比，其性能有了很大改进。
在进行直接插入排序时，如果待排序记录序列已经有序时，直接插入排序的时间复杂度可以提高到O(n)。因为希尔排序对直接插入排序进行了改进，所以大大提高了排序的效率。
下图为希尔排序的过程：
希尔排序.png
希尔排序在具体实现时，首先选定两个记录间的距离d1 ，在整个待排序记录序列中将所有间隔为d1 的记录分成一组，然后在组内进行直接插入排序。接下来取两个记录间的距离d2 <d1 ，在整个待排序记录序列中，将所有间隔为d2 的记录分成一组，进行组内直接插入排序，一直到选定两个记录间的距离dt =1为止。此时只有一个子序列，即整个待排序记录序列。
动画演示过程
希尔排序.gif
Go语言描述
希尔排序是第一个突破O(n²)效率的算法,它是插入排序的增强版，可以理解为分组插入排序。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，
整个文件恰被分成一组，算法便终止。平均的时间复杂度O(nlogn)。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。
它对于数据量较小的数列重复排序是非常好的。最坏的情况下时间复杂度是 O(n^2)。
- 平均时间复杂度：O(n^1.3)
- 最坏时间复杂度：O(n²)
- 最好时间复杂度：O(n)
- 空间复杂度：O(1)
- 稳定性：不稳定
关键思路：
一、选择合适的增量分组：
1.在希尔排序的原稿中，建议初始间距是N/2，简单把每趟排序分成两半
2.该方法好处是不需要在开始排序前为找合适的增量而进行任何计算
二、Hibbard增量序列
1.增量算法为2k - 1 ，也就是1 3 5 7...
2.该方法最坏的复杂度为O(N3/2),猜想的平均复杂度为O(N5/4)，目前尚未被证明
三、Sedgewick增量序列
1.{1,5,19,41,109,...}，该序列中的项或者是94^i - 9*2^i +1 或4^i -32^i +1
2.这种增量的最坏复杂度为O(N^4/3)，平均复杂度为 O(N^7/6)，但均未被证明
func ShellSort(list []int) {
// 1.获取数组的长度
l := len(list)
// 2.定义初始化的增量gap
gap := l / 2
// 3.不断缩小gap增量
for gap >= 1 {
// 4.以gap作为间隔进行分组，对分组进行插入排序
for i := gap; i < l; i++ {
tmp := list[i]
j := i
for j > gap-1 && list[j-gap] > tmp {
list[j] = list[j-gap]
j -= gap
}
list[j] = tmp
}
// 5.折半缩小gap分组增量
gap = gap / 2
}
}
网友评论