希尔排序
package main
import (
"fmt"
"helper/number"
"helper/time"
)
func main() {
data := number.GenerateInt(100000, 100)
start := time.CurrentMillis()
shellSort(data)
fmt.Printf("cost %v ms\n", time.CurrentMillis()-start)
}
func shellSort(data []int) {
//一共有多少列: 4 -> 2 -> 1
for col := len(data) / 2; col >= 1; col = col / 2 {
//对每一列处理 0 -> col（即每一次循环，就是处理该列的排序）
for i := 0; i < col; i++ {
//从每一列的第二个数开始进行插入排序（因为只有 >= 2 个元素时，才有可比性）
n := 1
//i + col * n 表示该列的下一个元素的位置 , 它要 < len(data)
for i+col*n < len(data) {
//保存当前元素的位置（因为它要不断地与位置比它小的进行交换（即插入排序）
k := i + col*n
for k >= 0 && (k-col) >= 0 {
//不断地与前一个元素进行比较（直到 前一个元素 >= 即可停止）这里是开始排序
if data[k] < data[k-col] {
data[k], data[k-col] = data[k-col], data[k]
k = k - col
} else {
break
}
}
//该列的下一个元素
n++
}
}
}
}
性能
[22:34:42] emacsist:test3 $ go build main.go && time ./main
cost 11 ms
./main 0.02s user 0.01s system 83% cpu 0.029 total
[22:39:18] emacsist:test3 $ go build main.go && time ./main
cost 12 ms
./main 0.02s user 0.01s system 95% cpu 0.024 total
[22:39:56] emacsist:test3 $
