go-数据结构[14]-希尔排序

希尔排序

希尔排序算法是按其设计者希尔(Donald Shell)的名字命名,该算法由1959年公布,是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步(增量较大)间隔比较,使记录跳跃式接近它的排序位置;然后增量缩小;最后增量为 1 ,这样记录移动次数大大减少,提高了排序效率。希尔排序对增量序列的选择没有严格规定。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

1、插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率
2、但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位
算法思路:

先取一个正整数 d1(d1 < n),把全部记录分成 d1 个组,所有距离为 d1 的倍数的记录看成一组,然后在各组内进行插入排序
然后取 d2(d2 < d1)
重复上述分组和排序操作;直到取 di = 1(i >= 1) 位置,即所有记录成为一个组,最后对这个组进行插入排序。一般选 d1 约为 n/2,d2 为 d1 /2, d3 为 d2/2 ,…, di = 1。

实例分析

go语言实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package main

import "fmt"
//打印
func print(arr []int){

for _,data := range arr{
fmt.Printf("%d ",data)
}

fmt.Println()
}



func main(){

//arr:= []int{8, 5, 2, 6, 9, 3, 1, 4, 0, 7,6,3,10}
arr:=[]int{1,3,2,4,9,2,6,5,4,8}
print(arr)

shellsort(arr)

print(arr)
}

//希尔排序
func shellsort(arr []int){

gap:=4
length:= len(arr)

for gap >0{

for i:=gap;i<length;i+=1{
j:= i
temp:= arr[i]
for;j>0;j-=gap{
if j-gap>=0 && arr[j] < arr[j-gap]{
tmp:= arr[j]
arr[j] = arr[j-gap]
arr[j-gap] = tmp
}else{
break
}
}
}

gap = gap/2

}
}

javascript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function shellSort(array) {

function swap(array, i, k) {
var temp = array[i];
array[i] = array[k];
array[k] = temp;
}

var length = array.length,
gap = Math.floor(length / 2);

while (gap > 0) {
for (var i = gap; i < length; i++) {
for (var j = i; 0 < j; j -= gap) {
if (array[j - gap] > array[j]) {
swap(array, j - gap, j);
} else {
break;
}
}
}

gap = Math.floor(gap / 2);
}

return array;
}