排序的几种算法

发表于

###关于排序算法的问题梳理：

​ 衡量一个算法的好坏有两个指标：渐近时间复杂度和渐近空间复杂度

  • 第一类：简单排序算法 - 简单选择排序、简单插入排序、冒泡排序 - O(n ** 2)
  • 第二类：高级排序算法 - 快速排序、归并排序 - O(n * log2 n)

本文主要介绍冒泡排序和归并排序

####冒泡排序

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
"""
68, 34, 12, 95, 73, 80, 57
34, 12, 68, 73, 80, 57, 95
12, 34, 68, 73, 57, 80
12, 34, 68, 57, 73
12, 34, 57, 68
12, 34, 57
12, 34
"""

def bubble_sort(unsorted_items, *, comp=lambda x, y: x > y):
    """冒泡排序"""
    items = unsorted_items[:]
    items_len = len(items)
    for i in range(items_len - 1):
        swapped = False
        for j in range(items_len - 1 - i):
            if comp(items[j], items[j + 1]):
                items[j], items[j + 1] = items[j + 1], items[j]
                swapped = True
        if swapped:
            swapped = False
            for j in range(items_len - 2 - i, 0, -1):
                if comp(items[j - 1], items[j]):
                    items[j], items[j - 1] = items[j - 1], items[j]
                    swapped = True
        if not swapped:
            break
    return items


# class Student():
#
#     def __init__(self, name, age):
#         self.name = name
#         self.age = age
#
#     def __repr__(self):
#         return f'{self.name}: {self.age}'
#
#     def __gt__(self, other):
#         return self.age > other.age
# 使用namedtuple可以更简洁的生成类
Student = namedtuple('Student', ('name', 'age'))


def main():
    """主函数"""
    items = [
        Student('Luo Hao', 38), Student('Wang Dachui', 19),
        Student('Lee Xiaolong', 25), Student('Zhang Sanfeng', 120)
    ]
    print(bubble_sort(unsorted_items=items,
                      comp=lambda x, y: x.age > y.age))
    items2 = ['pitaya', 'pear', 'apple', 'watermelon', 'waxberry']
    print(bubble_sort(items2, comp=lambda x, y: len(x) > len(y)))


if __name__ == '__main__':
    main()

归并排序

​ 通过分解再重组来排序

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
"""
68, 34, 12, 95, 73, 80, 57
[69, 34, 12], [95, 73, 80, 57]
[69], [34, 12], [95, 73], [80, 57]
[69], [34], [12], [95], [73], [80], [57]
----------------------------------------
[34, 69], [12, 95], [73, 80], [57]
[12, 34, 69, 95], [57, 73, 80]
[12, 34, 57, 69, 73, 80, 95]
"""
# 分治法 - 将规模较大的问题划分为规模较小的子问题 用子问题解合并出原问题的解
# divide-and-conquer
def merge_sort(unsorted_items, *, comp=lambda x, y: x < y):
    if len(unsorted_items) <= 1:
        return unsorted_items[:]
    mid = len(unsorted_items) // 2
    left = merge_sort(unsorted_items[:mid], comp=comp)
    right = merge_sort(unsorted_items[mid:], comp=comp)
    return merge(left, right, comp=comp)


def merge(list1, list2, *, comp=lambda x, y: x < y):
    """将两个有序列表合并 合并之后仍然有序"""
    list3 = []
    index1, index2 = 0, 0
    while index1 < len(list1) and index2 < len(list2):
        if comp(list1[index1], list2[index2]):
            list3.append(list1[index1])
            index1 += 1
        else:
            list3.append(list2[index2])
            index2 += 1
    list3 += list1[index1:]
    list3 += list2[index2:]
    return list3
    
    def main():
    """主函数"""
    items3 = [68, 34, 12, 95, 73, 80, 57]
    print(merge_sort(items3))


if __name__ == '__main__':
    main()

分治法：分而治之，将大问题拆解

所以能用循环的地方都不用递归

例子：小孩走楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 爬楼梯 一次可以爬1个、2个、3个台阶
# 爬完10个台阶一共有多少种走法
def walk(num, result={}):
    if num == 0:
        return 1
    elif num < 0:
        return 0
    try:
        return result[num]
    except KeyError:
        result[num] = walk(num - 1) + walk(num - 2) + walk(num - 3)
        return result[num]
        
def main():
    for num in range(1, 11):
        print(f'{num}: {walk(num)}')
        
        
if __name__ == '__main__':
    main()

例子2:斐波拉契数列的两种解法

1
2
3
4
def factorial(num):
    if num in (0, 1):
        return 1
    return num * factorial(num - 1)

斐波拉契优化：

动态规划优化

​ 将求解的中间值储存起来，牺牲空间换取时间

使用动态规划算法，求解的问题有局部最优解或者最优字结构，（把每一次的结果保存下来）

1
2
3
4
5
6
7
8
9
10
# 1 1 2 3 5 8 13 21 34 55 ...
# 动态规划 - 求解的问题有局部最优解或者最优子结构
def fib2(num, result={}):
    if num in (1, 2):
        return 1
    try:
        return result[num]
    except KeyError:
        result[num] = fib2(num - 1) + fib2(num - 2)
        return result[num]