希尔排序

2021-04-15 | 129 浏览

希尔排序

希尔排序也称为缩小增量排序,它的基本原理如下:首先将待排序的数组元素分成多个子序列,使得每个子序列的元素个数相对较少,然后对各个子序列分别进行直接插入排序,待整个排序序列"基本有序"后,最后再对所有元素进行一次直接插入排序.

具体步骤如下:

选者一个步长序列t1,t2 ... ,tk,满足ti>tj,tk=1

按步长序列个数k,对待排序序列进行k趟排序

每趟排序,根据对应的步长ti,将待排序列分割成ti个子序列,分别对各个子序列进行直接插入排序

注意:当步长因子为1时,所有元素作为一个序列来处理,其长度为n,以数组{26,53,67,48,57,13,48,32,60,50},步长序列为{5,3,1}为例,具体步骤如下:

初始化关键字:

第1趟:26 , 53 , 67 , 48 , 57 , 13 , 48 , 32 , 60 , 50

第2趟:13 , 48 , 32 , 48 , 50 , 26 , 53 , 67 , 60 , 57

第3趟:13 , 26 , 32 , 48 , 48 , 50 , 53 , 57 , 60 , 67
package main

import "fmt"

func shellSort(array []int) {
	llen := len(array)
	for h := llen / 2; h > 0; h = h / 2 {
		for i := h; i < llen; i++ {
			temp := array[i]
			var j int
			for j = i - h; j >= 0; j -= h {
				if temp < array[j] {
					array[j+h] = array[j]
				} else {
					break
				}
			}
			array[j+h] = temp
		}
		fmt.Println("排序过程: ", array)
	}
}
func main() {
	data := []int{26, 53, 67, 48, 57, 13, 48, 32, 60, 50}
	shellSort(data)
	fmt.Printf("排序结果如下:\n")
	fmt.Println(data)
}
程序输出为
[administrator@administrator-dev 20210414]$ go run   01.go 
排序过程:  [13 48 32 48 50 26 53 67 60 57]
排序过程:  [13 26 32 48 50 48 53 57 60 67]
排序过程:  [13 26 32 48 48 50 53 57 60 67]
排序结果如下:
[13 26 32 48 48 50 53 57 60 67]
希尔排序的关键并不是随便地分组后各自排序,而是将相隔某个"增量"的记录组成一个子序列,实现跳跃式地移动,使得排序的效率提高

算法