希尔排序是插入排序的一种,也称之为缩小增量排序
。希尔排序算法是直接插入排序算法的一种改进,减少了其复制的次数,速度要快很多。希尔排序是非稳定排序算法,实现过程:
对每个组进行插入排序
假设步长为step,对[1, 8, 2, 9, 3, 7, 4, 6, 5]进行排序,步长一般是按照折半
进行选取
def shell_sort(alist):
# 希尔排序:核心是插入排序
n = len(alist)
# 折半:取整数解,防止小数:n=9,step=4
step = n // 2
i = 1
# 步长变化到0之前即1,插入算法执行的次数
while step > 0:
# 插入算法:与普通插入算法的区别就是步长step
for j in range(step, n):
# j = gap, gap+1, ..., n-1
i = j
while i > 0:
if alist[i] < alist[i-step]:
# 比较的两个数下标相差为步长step
alist[i], alist[i-step] = alist[i-step], alist[i]
i -= step
else:
break
# 一个for循环结束则缩短步长step
step //= 2
return alist
package main
import "fmt"
// shell排序
func shellSort(numberArray []int) []int{ // 定义函数、参数和返回值
n := len(numberArray)
step := n / 2 // 设定步长step
for step > 0{ // 进行排序的条件:步长大于0
for j := step; j < n; j++{ // 控制外层循环:从中间的step位置开始,往后进行比较
// j = [step, step+1, ..., n-1]
i := j
for i > 0{
if numberArray[i] > numberArray[i-step]{ // 进行比较和交换的两个数之的索引相差为step
numberArray[i], numberArray[i-step] = numberArray[i-step], numberArray[i]
i -= step // 每交换一次,下标左移step;直接插入排序中是左移一个位置
}else {
break
}
}
}
step = step / 2 // 执行一次,步长要缩短一半
}
return numberArray
}
func main(){
shellArray := []int{1,8,9,7,3,5,2,6,4}
fmt.Println("Before:", shellArray)
shellSort(shellArray)
fmt.Println("After:", shellArray)
}