社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
插入排序在某些情况下,效率是很高的。
比如我们的记录本身就是基本有序的,只需要少量的插入操作。
再比如,记录少的时候,插入排序效率的优势也是很明显的。
可是现实中,哪有那么理想的情况啊[>_<]
没有环境,那我们就要自己创造啊!!!
基本有序:
所谓的基本有序就是小的关键字在前面,大的基本在后面,不大不小的基本在中间。
关键词: 步长
、分组
我们首先根据一定的步长
,将原有的记录进行分组
。
在分组内,使用插入排序把分组变成有序。
然后调整增量
,继续对分组做插入排序
处理。
直至最后步长变为1
,此时整个记录已经基本有序了,再进行少量的插入操作,就可以把整个记录变成有序。
举个例子:
func shellSortStep(arr []int, start int, gap int) []int {
// 数组长度
length := len(arr)
// 插入排序的变种
for i := start + gap; i < length; i += gap {
// 备份待插入的数据
backup := arr[i]
// 初始化待插入位置
j := i - gap
// 待插入数据,小于前面的数据
for j >= 0 && backup < arr[j] {
// 从前往后移动
arr[j+gap] = arr[j]
j -= gap
}
arr[j+gap] = backup
}
return arr
}
func ShellSort(arr []int) []int {
// 数组长度
length := len(arr)
// 数组为空或者只有一个元素
if length <= 1 {
return arr
}
// 步长
gap := length / 2
for gap > 0 {
// 处理每个元素的步长
for i := 0; i < gap; i++ {
shellSortStep(arr, i, gap)
}
gap /= 2
}
return arr
}
有人说,按照Knuth序列,应该是这样的:
// 如果h最终为1
h = 1
// 则h的计算公式为,同时h不应该大于1/3,否则就比整个数组长度还要大了
h = 3*h - 1
func shellSortStep(arr []int, start int, gap int) []int {
// 数组长度
length := len(arr)
// 插入排序的变种
for i := start + gap; i < length; i += gap {
// 备份待插入的数据
backup := arr[i]
// 初始化待插入位置
j := i - gap
// 待插入数据,小于前面的数据
for j >= 0 && backup < arr[j] {
// 从前往后移动
arr[j+gap] = arr[j]
j -= gap
}
arr[j+gap] = backup
}
return arr
}
func ShellSort(arr []int) []int {
// 数组长度
length := len(arr)
// 数组为空或者只有一个元素
if length <= 1 {
return arr
}
// 步长
gap := 1
for gap <= length/3 {
gap = gap*3 + 1
}
for gap > 0 {
// 处理每个元素的步长
for i := 0; i < gap; i++ {
shellSortStep(arr, i, gap)
}
gap = (gap - 1) / 3
}
return arr
}
希尔排序的时间复杂度是:O(n^(1.3—2))
为什么是个区间呢?
因为时间复杂度和增量的选择有关,选择不同的增量会有不同的效果。
但不论怎么说,希尔排序的性能要好于直接排序的O(n^2)。
由于希尔排序在排序的过程中,记录时跳跃式的移动,所以希尔排序是一种不稳定排序算法。
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!