· 插入排序

插入排序的思路是创建一个初始指向arr[0]的指针p，将数组arr分为：左边的已排序区（arr[:p]） 和 右边的未排序区（arr[p:]）。arr[p]是下一个要排好序的元素。

对arr进行n-1轮排序，每轮排序需要将arr[p]插入到排序区的合适位置（因此需要查找已排序区内arr[p]的合适位置，插入过程会导致已排序区内的部分元素整体后移）。

 

插入排序过程如下：

 

代码实现：

func InsertSort(arr []int) []int{
	p := 0
	for p < len(arr){
		target := arr[p]		// 要插入到已排序区的目标值
		i := p-1	// target要和[0, p-1]的数比较，从而找到要插入的位置，比较的同时要将arr[i]挪到arr[i+1]的位置
		for ; i >=0; i--{
			if target < arr[i]{
				arr[i+1] = arr[i]
			}else{		// 如果 arr[i] 比 arr[p]小或相等，则arr[p]插入到arr[i+1]的位置
				break
			}
		}
		arr[i+1] = target
		p++
	}
	return arr
}

 

在已排序区寻找arr[p]的合适插入位置是否可以使用二分查找降低复杂度？

肯定是不行的，因为将arr[p]插入到合适位置后，挪动已排序区内arr[p]后的元素也需要O(n)复杂度。

 

但相比于冒牌排序，插入排序不仅减少了很多次交换，也减少了很多次比较，但是增加了移动元素的成本（一次移动元素的成本小于一次交换的成本，因此插入排序还是由于冒泡排序的）。

如果在数组大部分元素是有序的情况下，插入排序的比较次数和交换次数都可以大大减少（对一个完全排好序的数组进行插入排序其复杂度为O(n)），这是优于选择排序和冒泡排序的地方。

 

此外插入排序是一种稳定的排序，这里的稳定是指多个相同元素排序后顺序不会乱。

 

 

· 希尔排序

希尔排序是基于插入排序的优化，优化的根据有2点：

1、插入排序在数组长度越小的情况工作量越小；

2、插入排序在数组大多数元素已经有序的情况下工作量越小（对于完全排好序的数组，插入排序只需比较 n-1次，而且无需交换，无需移动元素）。

 

希尔排序大体思路是将一个数组预处理，使其满足上述两点。

具体思路是对数组arr进行多轮不同间距的分组，初始间距为len(arr)/2，下一轮的间距是上一轮间距的一半（如果无法整除则向下取整）。

对同一间距下的每个分组进行插入排序，当间距减小为1时整个数组arr就只有一组，即arr本身，对arr本身进行最后一次插入排序即可完成整体排序。（间距越大，每一组的元素数量就越小，反之则每一组的数量越大，实际上组数 = 间距，即使间距/2无法整除这个结论也成立）。

 

过程如下：

0、原数组arr

 

1、第一轮间距取 len(arr)/2 = 4，共4组，每组2个元素（组数 = 间距 = 4）

元素5和元素9一组，元素8和元素2一组，元素6和元素1一组，元素3和元素7一组，一共4组。对每组进行插入排序后的结果如下：

 

2、第二轮间距取 len(arr)/2^2 = len(arr)/4 = 2，共2组，每组4个元素

元素5，1，9，6一组，元素2，3，8，7一组。对每组进行插入排序后的结果如下：

 

3、第三轮间距取 len(arr)/8 =  2，共1组，每组8个元素，进行最后一次插入排序

 

分组可以减少每次插入排序的元素数量，满足第一个优化条件；下一轮分组的插入排序都是在上一轮已经有部分排序的序列中再排序，满足第二个优化条件。

上面示例中所使用的分组跨度（4，2，1），被称为希尔排序的增量，又称为希尔增量。实际上对增量的选择不同，希尔排序的性能也不同。

 

代码实现：

// 希尔排序
func ShellSort(arr []int) []int{
	gap := len(arr)/2		// gap表示组间距
	for gap >= 1{
		// 在指定组间距下，arr[0:gap]是每一组的第一个元素，一共有 gap 组
		for i:=0; i<gap; i++{	// 对 gap 组序列分别进行插入排序
			InsertSortHelper(arr, i, gap)
		}
		gap /= 2
	}
	return arr
}

func InsertSortHelper(arr []int, start, gap int){	// 分组插入排序，start是本组的开始下标，gap是组间距
	p := start
	for p < len(arr){
		target := arr[p]
		i := p - gap	// i表示没有与target比较过的已排序区元素
		for ; i>=start; i-=gap{
			if target < arr[i]{
				arr[i+gap] = arr[i]
			}else{
				break
			}
		}
		arr[i+gap] = target
		p += gap
	}
}

 

希尔排序的复杂度介于 O(n^2)到O(nlogn)之间，最优可达到O(nlogn)的复杂度。

 

但是希尔排序的性能会在某种特殊情况下达到O(n^2)，而且会比直接插入排序性能还差，那就是在分组已经排好序的情况，例如：

上面这个数组，如果我们照搬之前的分组思路，无论是以4为增量，还是以2为增量，每组内部的元素都没有任何交换。一直到我们把增量缩减为1，数组才会按照直接插入排序的方式进行调整。对于这样的数组，应该直接使用插入排序，希尔排序不但没有减少直接插入排序的工作量，反而白白增加了分组操作的成本。

 

可以使用“互质（互为质数）”的增量避免这种情况，也就是增量之间没有除1之外的公约数。如 1/3/7/15，即本轮间距为 n，下一轮间距是 (n+1)/2-1，而非n/2。利用此种增量方式的希尔排序，最坏时间复杂度是O（n^(3/2)）。

 

此外，希尔排序还是一个可能导致相同元素乱序的排序，如下：

原数组：

 

经过希尔排序之后得到：

 

由此可见希尔排序是一个不稳定排序。