You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
 

1.1 KiB

希尔排序

  • 介绍

    • 定义
      • 希尔排序是一种分组插入排序算法。
    • 复杂度 比较多类别,复杂度不一
    • 过程:
      • 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。
      • 插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。
    • 关键字:
      • 插入排序
      • 缩小增量排序
  • 原理

    • 按下标的一定增量分组 ,分成多个子序列,然后对各个子序列进行直接插入排序算法排序;
    • 然后依次缩减增量再进行排序,直到增量为1时,进行最后一次直接插入排序,排序结束。
  • 代码

func main(){
    for d := len(a); d >= 1; d = d/2 {
		Shell(a, d)
	}
}


/**
Shell 实现希尔排序 O(n * n)
	a : 被排序数组
	返回:排序完毕数组
*/
func Shell(s []int, get int) {
	n := len(s)
	if n < 2 {
		return
	}
	for i := get; i < n; i++ {
		for j := i; j > 0 && s[j] < s[j - get]; j = j - get {
			// 选择第j张比较第j - get张小,则循环交换较大的值
			s[j], s[j - get] = s[j - get], s[j]
		}
	}
}