算法:希尔排序
算法 About 2,775 words算法演进
首次按数组的长度除以2
为分组步长,若步长大于1
,则再次分组,以首次得到的步长再除以2
为步长,以此类推分组,直至步长为1
。
以[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
为例。
第一步
分组步长:10/2=5
,以5
为步长递增分组得到:[8,3] [9,5] [1,4] [7,6] [2,0]
,分组后从第5
位元素开始按步长为5
递减进行排序交换得到[3 5 1 6 0 8 9 4 7 2]
。
第二步
分组步长:5/2=2
,以2
为步长递增分组得到:[3,1,0,9,7] [5,6,8,4,2]
,分组后从第2
位元素开始按步长为2
递减进行排序交换得到[0 2 1 4 3 5 7 6 9 8]
。
第三步
分组步长:2/2=1
,以1
为步长递增分组得到:[0 2 1 4 3 5 7 6 9 8]
,分组后从第1
位元素开始按步长为1
递减进行排序交换得到[0 1 2 3 4 5 6 7 8 9]
。
// 交换法
func ShellSortExchangeEvolution() {
arr := []int{8, 9, 1, 7, 2, 3, 5, 4, 6, 0}
log.Println(arr)
//step := 5 // len(arr)/2
for i := 5; i < len(arr); i++ {
log.Println("step=5, iiiiiiiiii=", i, arr)
for j := i - 5; j >= 0; j -= 5 {
if arr[j] > arr[j+5] {
temp := arr[j]
arr[j] = arr[j+5]
arr[j+5] = temp
}
log.Println("step=5, j=", j, arr)
}
}
log.Println(arr)
for i := 2; i < len(arr); i++ {
/*if arr[i-2] > arr[i] {
temp := arr[i-2]
arr[i-2] = arr[i]
arr[i] = temp
}*/
log.Println("step=2, iiiiiiiiii=", i, arr)
for j := i - 2; j >= 0; j -= 2 {
if arr[j] > arr[j+2] {
temp := arr[j]
arr[j] = arr[j+2]
arr[j+2] = temp
}
log.Println("step=2, j=", j, arr)
}
}
log.Println(arr)
for i := 1; i < len(arr); i++ {
log.Println("step=1, iiiiiiiiii=", i, arr)
for j := i - 1; j >= 0; j -= 1 {
if arr[j] > arr[j+1] {
temp := arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
}
log.Println("step=1, j=", j, arr)
}
}
log.Println(arr)
}
希尔排序交换法代码
func Exchange() {
arr := []int{8, 9, 1, 7, 2, 3, 5, 4, 6, 0}
for step := len(arr) / 2; step > 0; step /= 2 {
for i := step; i < len(arr); i++ {
for j := i - step; j >= 0; j -= step {
if arr[j] > arr[j+step] {
temp := arr[j]
arr[j] = arr[j+step]
arr[j+step] = temp
}
}
}
log.Println(arr)
}
}
希尔排序移位法代码
func main() {
arr := []int{8, 9, 1, 7, 2, 3, 5, 4, 6, 0}
for step := len(arr) / 2; step > 0; step /= 2 {
for i := step; i < len(arr); i++ {
j := i
insertVal := arr[i]
if arr[j] < arr[j-step] {
for j-step >= 0 && insertVal < arr[j-step] {
arr[j] = arr[j-step]
j -= step
}
arr[j] = insertVal
}
}
log.Println(arr)
}
}
Views: 1,358 · Posted: 2021-02-08
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...