CosmosNing的个人博客

探索·好奇

0%

算法趣解之基础排序算法（下）

发表于 更新于 分类于
本文字数： 3.6k 阅读时长 ≈ 3 分钟
一起来分析一下打牌时排序牌的方法
cover

打牌是很多人喜欢的与亲朋好友一起娱乐的一种方式。在牌局开始，打牌的各位都要依此摸牌。与此同时，为了方便后续出牌，很多人对摸到的牌从大到小排序。这种排序手法，在算法中，被称作“插入排序”。

为了理解“插入排序”的主要流程，我们先来简单地回顾一下对牌排序的流程。

每摸一张牌，我们都会将这张牌和手上的牌依次进行对比，找到合适的位置插入，保证手上的牌是有序的。下次摸牌时，也是类似的流程。最终，手上会是一个有序的牌组。

将上述流程抽象概括一下，就是：每次将一个待排序的数据，在前面已排好序的子序列中从后向前扫描， 按其值大小找到适当的位置并插入其中，直到序列中的全部数据都插入完毕为止。

这个算法的流程在排序牌的例子中已经有了非常直观的解释，这里我们直接进入代码实现环节。

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
def insert_sort(lst):
    """
    插入排序
     将无序的数字列表变成从小到大的数字列表返回
    参数：
     lst：待排序的列表
    返回：
     按从小到大排列的列表
    """
    for i in range(len(lst)):
        k = i#保存插入的位置
        tmp = lst[i]#暂时保存当前待插入元素的值

        for j in range(i+1):
            if lst[i] < lst[j]:
                k = j#找到插入位置，保存到k中
                break

        for j in range(i, k, -1):
            lst[j] = lst[j-1]#将列表中相关数据移位，方便元素插入

        lst[k] = tmp#插入元素

        print("第{}次排序结果:".format(i+1),lst)#print(lst)

    return lst

# 测试例程
lst = [89, 43, 88, 87, 61]

print("最终结果",insert_sort(lst))
        
"""
输出结果:
第1次排序结果: [89, 43, 88, 87, 61]
第2次排序结果: [43, 89, 88, 87, 61]
第3次排序结果: [43, 88, 89, 87, 61]
第4次排序结果: [43, 87, 88, 89, 61]
第5次排序结果: [43, 61, 87, 88, 89]
最终结果 [43, 61, 87, 88, 89]
"""

假设待排序的数据量为 \(N\) ，依据上述插入排序算法，外层循环将执行 \(N\) 次，内层循环依据外层循环次数 \(i\) 将执行 \(i\) 次（将两个内层循环次数相加即可）。所以该算法至多执行 \[ \begin{aligned} &\ \ \ \ \ 1+2+3+ ··· +N-1\\ &= (N-1)(1 + N – 1)/2\\ &= N(N-1)/2 \end{aligned} \] 次。所以插入排序的时间复杂度为 \(O(N^{2})\) 。

插入排序算法在时间性能上来说，表现得并不理想。能不能对他进行优化呢？希尔（Donald Shell）提出了他对该算法的改进。这个算法描述如下：

取一个小于 \(n\) 的整数 \(d_{1}\) 作为第一个增量， 把序列中的全部数据分成 \(d_{1}\) 个组。 所有距离为 \(d_{1}\) 的倍数的数据放在同一个组中；

\(n\) 在各组内进行直接插入排序；

\(n\) 取第二个增量 \(d_{2} < d_{1}\) ， 重复上述的分组和排序， 直至所取的增量 \(d_{t}=1(d_{t}< …<d_{2}<d_{1})\) ， 即所有数据都放在同一组中进行直接插入排序为止。

所以这个算法本质是一种分组插入排序。除了插入排序的思想，更关键的是算法中增量序列d的确定。

有一种增量叫做Hibbard增量，其表达式如下：

\[ h_{i} = 2^{i} - 1 \]

它可以使希尔排序的时间复杂度降低到 \(O(N^{\frac{3}{2}})\) 。

我们以这种增量序列生成方式来实现一下希尔排序。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
# 参考：https://baike.baidu.com/item/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/3229428?fr=aladdin#7_8
import math

def shell_insert(lst,dk):
    """
    shell_insert:
     按照增量dk，对lst中的元素进行分组插入排序
    参数：
     lst：存储待排序的数据列表
     dk:增量
    返回：
     分组排序后的数据列表
    """
    for i in range(dk,len(lst)):
        tmp = lst[i]
        m = i - dk
        for j in range(i-dk, -dk-1,-dk):
            if not(j >= i%dk and lst[j] > tmp):
                m = j
                break
            lst[j+dk] = lst[j]
        if m != i - dk:
            lst[m+dk] = tmp
    return lst

def dkHibbard(t, k):
    """
    dkHibbard:
     按照Hibbard增量生成方式生成增量
    参数：
     t：排序的总趟数
     k：当前排序的趟数
    返回：
     当前趟数的Hibbard增量
    """
    return (int)(math.pow(2,t-k+1)-1)


def shell_sort(lst, t):
    """
    希尔排序：
     对无序的数据列表排序，使之从小到大排列
    参数：
     lst：待排序的数据列表
     t：排序当前数据列表的总趟数
    返回：
     从小到大排序的数据列表
    """
    for i in range(1, t+1):
        
        print("第{}次排序前序列:".format(i),lst)
        lst = shell_insert(lst, dkHibbard(t, i))
        print("第{}次排序使用的增量{}".format(i,dkHibbard(t, i)))
        print("第{}次排序结果:".format(i),lst)
        print()
        
        
        """
        dk = (int)(math.pow(2,t-i+1)-1)
        print("第{}次排序前序列:".format(i),lst)
        print("第{}次排序使用的增量{}".format(i,dk))
        for j in range(dk,len(lst)):
            tmp = lst[j]
            m = j - dk
            for k in range(j-dk, -dk-1,-dk):
                if not(k >= j%dk and lst[k] > tmp):
                    m = k
                    break
                lst[k+dk] = lst[k]
            if m != j - dk:
                lst[m+dk] = tmp
        print("第{}次排序结果:".format(i),lst)
        print()
        """

    return lst

# 排序趟数等于log2(待排序的数据量大小 + 1)取整
print(shell_sort([84, 83, 88, 87, 61, 50, 70, 60, 80, 99],(int)(math.log2(10+1))))

"""
输出结果：
第1次排序前序列: [84, 83, 88, 87, 61, 50, 70, 60, 80, 99]
第1次排序使用的增量7
第1次排序结果: [60, 80, 88, 87, 61, 50, 70, 84, 83, 99]

第2次排序前序列: [60, 80, 88, 87, 61, 50, 70, 84, 83, 99]
第2次排序使用的增量3
第2次排序结果: [60, 61, 50, 70, 80, 83, 87, 84, 88, 99]

第3次排序前序列: [60, 61, 50, 70, 80, 83, 87, 84, 88, 99]
第3次排序使用的增量1
第3次排序结果: [50, 60, 61, 70, 80, 83, 84, 87, 88, 99]

[50, 60, 61, 70, 80, 83, 84, 87, 88, 99]
"""

大家可以对照上述程序的执行过程来体会希尔排序的排序流程。在实现希尔排序的过程中，默认采用了函数嵌套的写法。同时，我也写了不用函数嵌套的写法。（将5054注释，将5672行取消注释，即是不用函数嵌套的写法）。

在文章的最后，照例进行总结：

  1. 插入排序的主要流程：每次将一个待排序的数据，在前面已排好序的子序列中从后向前扫描，按其值大小找到适当的位置并插入其中，直到序列中的全部数据都插入完毕为止。
  2. 插入排序的时间复杂度为 \(O(N^{2})\) 。
  3. 一种插入排序的改进算法，希尔排序，本质是一种分组排序方法。
  4. 利用Hibbard增量生成希尔排序中需要的增量序列，可以使得其时间复杂度变为 \(O(N^{\frac{3}{2}})\) 。