面试题 / 算法

经典排序

希尔排序

  • 时间复杂度 O(nlogn),空间复杂度 O(1)
  • 希尔排序是 插入排序的升级版
  • 将插入排序拆分多个区间,然后区间里进行排序
func shell(nums []int) []int {
	length := len(nums)
	gap := 1
	for gap < length/3 {
		fmt.Println(gap,length/3)
		gap = gap*3 + 1
	}
	for gap > 0 {
		for i := gap; i < length; i++ {
			temp := nums[i]
			j := i - gap
			for j >= 0 && nums[j] > temp {
				nums[j+gap] = nums[j]
				j -= gap
			}
			nums[j+gap] = temp
		}
		gap = gap / 3
	}
	return nums
}