希尔排序

func sortArray(nums []int) []int {
// 希尔排序，比较交换，不稳定算法，时间O(nlog2n)最坏O(n^2), 空间O(1)
// 改进插入算法
// 每一轮按照间隔插入排序，间隔依次减小，最后一次一定是1
/
主要思想：
设增量序列个数为k，则进行k轮排序。每一轮中，
按照某个增量将数据分割成较小的若干组，
每一组内部进行插入排序；各组排序完毕后，
减小增量，进行下一轮的内部排序。
/
gap := len(nums)/2
for gap > 0 {
for i:=gap;i j := i
for j-gap >= 0 && nums[j-gap] > nums[j] {
nums[j-gap], nums[j] = nums[j], nums[j-gap]
j -= gap
}
}
gap /= 2
}
return nums
}