排序之希尔排序(减少步长排序)｜Go主题月

希尔排序是以其设计者希尔（Donald Shell）名字命名，也称“缩小步长排序”，它对插入排序做了改进：

1. 将列表分成数个子列表；
2. 并对每一个子列表使用插入排序算法进行排序。

如何切分列表？

1. 并不是连续切分；
2. 而是使用步长i选取所有间隔为i的元素组成子列表。

以切片数组[10, 1, 5, 3]为例:

1. 这个列表有4个元素;
2. 如果步长间隔为2，就有2个子列表，即索引0和索引2构成的子列表1、索引1和索引3构成的子列表2;

3. 对每个子列表应用插入排序。子列表1就是[10, 5]进行插入排序即[5, 10];子列表2[1, 3]进行插入排序即[1,3]；
4. 经过子列表的插入排序后，尽管列表[5,1,10,3]仍然不算完全有序，但通过给子列表排序，我们已经让元素离它们的最终位置更近了；
5. 对步长为1的切片数组应用插入排序。

时间复杂度：大概介于O(n)和O(n²)之间

使用Golang实现的希尔排序(减少步长排序)算法代码如下：

package main

import "fmt"

func shellSort(numList []int) {
	// 希尔排序：递减步长排序
	subListCount := len(numList) / 2
	for subListCount > 0 {
		for i := 0; i < len(numList); i++ {
			// 对 相同步长不同起点 得到的子列表进行插入排序
			gapInsertSort(numList, i, subListCount)
		}
		// 步长递减
		subListCount = subListCount / 2
	}
}

func gapInsertSort(numList []int, startPosition int, gap int) {
	// 对 待排序子列表 进行插入排序
	for idx := startPosition + gap; idx < len(numList); idx += gap {
		position := idx
		currentValue := numList[idx]
		for position >= gap && numList[position-gap] > currentValue {
			numList[position] = numList[position-gap]
			position = position - gap
		}
		numList[position] = currentValue
	}
}

func main() {
	numList := []int{10, 1, 5, 3}
	shellSort(numList)
	fmt.Println(numList)
}
复制代码