希尔排序

算法 评论

希尔排序是一种基于插入排序的算法.

插入排序的递增序列是1, 每次向前插入的时候都是和相邻的数组元素比较. 而希尔排序的递增是不固定的, 一般我们是选择一个算法, 算出递增. 希尔排序的思想是在间隔任意值h之间的数字是有序的, 这样的数组称为h有序数组. h有序数组是由h个互相独立的有序数组组成的一个大数组.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#-*- coding=utf-8 -*-

data = [8, 7, 6, 5, 4, 3, 2, 1]
print data

h = 1
while h < len(data)/3:
    h = 3*h + 1

def sort():
    global h
    while h > 0:
        for i in range(0, len(data)):
            for j in range(i, 0, -h):
                pre = j - h
                if data[j] < data[pre]:
                    tmp = data[pre]
                    data[pre] = data[j]
                    data[j] = tmp

                print str(h) + ":   " + str(data[j - h]) + " compore " + str(data[j]) + " -> " + str(data)
        h = h / 3
sort()

运算结果为

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
[8, 7, 6, 5, 4, 3, 2, 1]
4:   3 compore 7 -> [8, 7, 6, 5, 4, 3, 2, 1]
4:   2 compore 6 -> [8, 7, 6, 5, 4, 3, 2, 1]
4:   1 compore 5 -> [8, 7, 6, 5, 4, 3, 2, 1]
4:   4 compore 8 -> [4, 7, 6, 5, 8, 3, 2, 1]
4:   3 compore 7 -> [4, 3, 6, 5, 8, 7, 2, 1]
4:   3 compore 7 -> [4, 7, 6, 5, 8, 3, 2, 1]
4:   2 compore 6 -> [4, 7, 2, 5, 8, 3, 6, 1]
4:   2 compore 6 -> [4, 7, 6, 5, 8, 3, 2, 1]
4:   1 compore 5 -> [4, 7, 6, 1, 8, 3, 2, 5]
4:   1 compore 5 -> [4, 7, 6, 5, 8, 3, 2, 1]
1:   4 compore 7 -> [4, 7, 6, 5, 8, 3, 2, 1]
1:   6 compore 7 -> [4, 6, 7, 5, 8, 3, 2, 1]
1:   4 compore 6 -> [4, 6, 7, 5, 8, 3, 2, 1]
1:   5 compore 7 -> [4, 6, 5, 7, 8, 3, 2, 1]
1:   5 compore 6 -> [4, 5, 6, 7, 8, 3, 2, 1]
1:   4 compore 5 -> [4, 5, 6, 7, 8, 3, 2, 1]
1:   7 compore 8 -> [4, 5, 6, 7, 8, 3, 2, 1]
1:   6 compore 7 -> [4, 5, 6, 7, 8, 3, 2, 1]
1:   5 compore 6 -> [4, 5, 6, 7, 8, 3, 2, 1]
1:   4 compore 5 -> [4, 5, 6, 7, 8, 3, 2, 1]
1:   3 compore 8 -> [4, 5, 6, 7, 3, 8, 2, 1]
1:   3 compore 7 -> [4, 5, 6, 3, 7, 8, 2, 1]
1:   3 compore 6 -> [4, 5, 3, 6, 7, 8, 2, 1]
1:   3 compore 5 -> [4, 3, 5, 6, 7, 8, 2, 1]
1:   3 compore 4 -> [3, 4, 5, 6, 7, 8, 2, 1]
1:   2 compore 8 -> [3, 4, 5, 6, 7, 2, 8, 1]
1:   2 compore 7 -> [3, 4, 5, 6, 2, 7, 8, 1]
1:   2 compore 6 -> [3, 4, 5, 2, 6, 7, 8, 1]
1:   2 compore 5 -> [3, 4, 2, 5, 6, 7, 8, 1]
1:   2 compore 4 -> [3, 2, 4, 5, 6, 7, 8, 1]
1:   2 compore 3 -> [2, 3, 4, 5, 6, 7, 8, 1]
1:   1 compore 8 -> [2, 3, 4, 5, 6, 7, 1, 8]
1:   1 compore 7 -> [2, 3, 4, 5, 6, 1, 7, 8]
1:   1 compore 6 -> [2, 3, 4, 5, 1, 6, 7, 8]
1:   1 compore 5 -> [2, 3, 4, 1, 5, 6, 7, 8]
1:   1 compore 4 -> [2, 3, 1, 4, 5, 6, 7, 8]
1:   1 compore 3 -> [2, 1, 3, 4, 5, 6, 7, 8]
1:   1 compore 2 -> [1, 2, 3, 4, 5, 6, 7, 8]

王明Coder

一个纯粹的技术开发者。