排序算法-希尔排序详解_希尔排序的时间复杂度

        希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是一种不稳定排序。

        时间复杂度

        希尔排序的时间复杂度为O(n^(1.2-2))。

        算法思想

        希尔排序属于插入排序，希尔排序需要计算增量，按照增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的标定元素越来越多，当增量减至1时，整个数组被分成一组，算法便终止。当下比较流行的增量序列:gap=length/2或gap=length/3+1。希尔排序的步骤由如下图示讲解：

        假如当前有12个元素，按照增量计算公式：gap=length/2来计算增量，gap=6，第二轮增量为3，最后一轮增量为1；

        以增量为6，排序完之后得到增量有序的数组，接下来再将增量调整为3，进行排序

        以增量为3，排序完之后得到增量有序的数组，最后将增量调整为1，进行排序，排序之后就可以得到完全有序的数组。

        代码实现

package main
 
import "fmt"
 
func shellSort(arr []int) {
	if len(arr) < 2 {
		return
	}
	gap := len(arr) / 2
	for ; gap > 0; gap /= 2 {
		for i := gap; i < len(arr); i += gap {
			key := arr[i]
			j := i - gap
			for ; j >= 0 && arr[j] > key; j -= gap {
				arr[j+gap] = arr[j]
			}
			arr[j+gap] = key
		}
	}
}
 
func main() {
	arr := []int{15, 5, 2, 7, 12, 6, 1, 4, 3, 9, 8, 10}
	shellSort(arr)
	fmt.Println(arr)
}