1. 经典排序
1.1. 希尔排序
- 时间复杂度 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
}