冒泡排序

冒泡排序的原理很简单，就是每次都把当前无序序列中最大（或者最小）的元素移动到序列的开头（或者结尾），之后再对除该元素之外的剩余序列做同样的操作。当所有的元素都冒泡完毕之后，整个序列就会变得有序。冒泡排序的过程正如它的名字一般，每次都把序列中最大的元素移动到末尾（假设我们选择了这种规则），这种操作就好像水中的泡泡不断地从水中浮到水面一般。

冒泡排序的实现如下，简单观察就可以知道它的时间复杂度为O(n2)

1
2
3
4
5
6
def bubble_sort(arr):
    length = len(arr)
    for i in range(length - 1):
        for j in range(length - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

选择排序

原理上类似于冒泡排序，区别在于冒泡排序比较的是相邻元素的大小，选择排序则会与一个固定的数值进行大小比较，省去了一些没有必要的比较过程。同样是获取一个无序序列的最小值并放到开头，冒泡排序是逐个比较并交换值，而选择排序会以第一个元素作为基准值进行比较，获取到最小值后只需要把最小值和开头元素进行交换即可。

选择排序实现如下，复杂度为O(n2)

1
2
3
4
5
6
7
8
def select_sort(arr):
    length = len(arr)
    for i in range(length):
        min_num_index = i
        for j in range(i, length):
            if arr[j] < arr[min_num_index]:
                min_num_index = j
        arr[min_num_index], arr[i] = arr[i], arr[min_num_index]

插入排序

插入排序是将序列分为两部分，一部分有序，一部分无序。每次从无序序列选择一个元素插入到有序序列中的正确位置，保证有序序列仍然有序，就好像打牌的时候不断地抓牌把牌插入到正确的位置一般。在这里我们把序列的前半段当做有序序列，后半段当做无序序列。

插入排序实现如下，复杂度为O(n2)

1
2
3
4
5
6
7
8
9
def insert_sort(arr):
    length = len(arr)
    for i in range(1, length):
        value = arr[i]
        j = i - 1
        while j >= 0 and value < arr[j]:  # 元素向前挪动
            arr[j + 1] = arr[j]  # 全部向后移一位
            j -= 1
        arr[j + 1] = value

归并排序

归并排序是将两个有序序列合并为一个序列，而合并前的有序序列又可以由两个有序序列合并得到，如此反复最终实现排序。

归并排序实现如下，复杂度为O(NlogN)

flat
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
def merge_sort(arr):
    def _merge_sort(_arr, left, right):
        if left >= right:
            return
        # 计算中间位置
        mid = (left + right) // 2
        # 获得左半边的有序序列
        _merge_sort(_arr, left, mid)
        # 获得右半边的有序序列
        _merge_sort(_arr, mid + 1, right)

        tmp = []
        i = left
        j = mid + 1
        while i <= mid or j <= right:  # 遍历
            if i > mid:  # i已经到了尽头，只存j
                tmp.append(_arr[j])
                j += 1
                continue
            if j > right:  # j已经到了尽头，只存i
                tmp.append(_arr[i])
                i += 1
                continue

            # 取较小的那个值
            if _arr[i] < _arr[j]:
                tmp.append(_arr[i])
                i += 1
            else:
                tmp.append(_arr[j])
                j += 1

        _arr[left: right + 1] = tmp  # 将这一段序列设为有序

    _merge_sort(arr, 0, len(arr) - 1)

快速排序

快速排序和归并排序类似，都是使用分治法。区别在于归并排序是先创建两个有序的子序列，而快速排序是随机选取一个主元（pivot），然后将大于该元素的值放在其右边，小于该元素的值放在其左边。如此反复，最终序列就变得有序了。

快速排序实现如下，复杂度为O(NlogN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def quick_sort(arr):
    def _quick_sort(_arr, left, right):
        if left >= right:
            return

        pivot = random.randint(left, right)  # 随机一个pivot
        _arr[pivot], _arr[right] = _arr[right], _arr[pivot]  # 把这个值放到最右边
        j = left
        for i in range(left, right):
            if _arr[i] < _arr[right]:  # 如果当前这个值小于pivot对应的值
                _arr[i], _arr[j] = _arr[j], _arr[i]  # 将这个值放到左边去
                j += 1
        _arr[j], _arr[right] = _arr[right], _arr[j]  # 最后把这个值放在小值和大值的中间

        # 对左右两边的值进行分治
        _quick_sort(_arr, left, j - 1)
        _quick_sort(_arr, j + 1, right)

    _quick_sort(arr, 0, len(arr) - 1)

包含所有排序算法和测试的完整代码如下

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
import copy
import random
import time


def log(time_log=True, result_log=False):
    def decorator(func):
        def wrapper(*args, **kw):
            start = time.time()
            result = func(*args, **kw)
            end = time.time()
            if time_log:
                print('{:>12}: {:>7.2f}ms'.format(func.__name__, (end - start) * 1000))
            if result_log:
                print(result, end='\n\n')
            return result

        return wrapper

    return decorator


@log(result_log=True)
def get_array(start=0, end=1000, length=500):
    if start >= end or length <= 0:
        return []
    random_list = []
    for i in range(length):
        random_list.append(random.randint(start, end))
    return random_list


@log()
def bubble_sort(arr):
    length = len(arr)
    for i in range(length - 1):
        for j in range(length - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]


@log()
def select_sort(arr):
    length = len(arr)
    for i in range(length):
        min_num_index = i
        for j in range(i, length):
            if arr[j] < arr[min_num_index]:
                min_num_index = j
        arr[min_num_index], arr[i] = arr[i], arr[min_num_index]


@log()
def insert_sort(arr):
    length = len(arr)
    for i in range(1, length):
        value = arr[i]
        j = i - 1
        while j >= 0 and value < arr[j]:  # 元素向前挪动
            arr[j + 1] = arr[j]  # 全部向后移一位
            j -= 1
        arr[j + 1] = value


@log()
def merge_sort(arr):
    def _merge_sort(_arr, left, right):
        if left >= right:
            return
        # 计算中间位置
        mid = (left + right) // 2
        # 获得左半边的有序序列
        _merge_sort(_arr, left, mid)
        # 获得右半边的有序序列
        _merge_sort(_arr, mid + 1, right)

        tmp = []
        i = left
        j = mid + 1
        while i <= mid or j <= right:  # 遍历
            if i > mid:  # i已经到了尽头，只存j
                tmp.append(_arr[j])
                j += 1
                continue
            if j > right:  # j已经到了尽头，只存i
                tmp.append(_arr[i])
                i += 1
                continue

            # 取较小的那个值
            if _arr[i] < _arr[j]:
                tmp.append(_arr[i])
                i += 1
            else:
                tmp.append(_arr[j])
                j += 1

        _arr[left: right + 1] = tmp  # 将这一段序列设为有序

    _merge_sort(arr, 0, len(arr) - 1)


@log()
def quick_sort(arr):
    def _quick_sort(_arr, left, right):
        if left >= right:
            return

        pivot = random.randint(left, right)  # 随机一个pivot
        _arr[pivot], _arr[right] = _arr[right], _arr[pivot]  # 把这个值放到最右边
        j = left
        for i in range(left, right):
            if _arr[i] < _arr[right]:  # 如果当前这个值小于pivot对应的值
                _arr[i], _arr[j] = _arr[j], _arr[i]  # 将这个值放到左边去
                j += 1
        _arr[j], _arr[right] = _arr[right], _arr[j]  # 最后把这个值放在小值和大值的中间

        # 对左右两边的值进行分治
        _quick_sort(_arr, left, j - 1)
        _quick_sort(_arr, j + 1, right)

    _quick_sort(arr, 0, len(arr) - 1)


if __name__ == '__main__':
    random_array = get_array()

    array1 = copy.deepcopy(random_array)
    bubble_sort(array1)

    array2 = copy.deepcopy(random_array)
    select_sort(array2)

    array3 = copy.deepcopy(random_array)
    insert_sort(array3)

    array4 = copy.deepcopy(random_array)
    merge_sort(array4)

    array5 = copy.deepcopy(random_array)
    quick_sort(array5)

执行结果如下

   get_array:    1.08ms[606, 969, 12, 732, 279, 820, 962, 752, 989, 594, 789, 83, 818, 555, 872, 266, 863, 800, 953, 879, 371, 685, 171, 325, 868, 141, 209, 581, 660, 252, 426, 731, 672, 360, 913, 427, 44, 272, 399, 291, 492, 957, 921, 315, 65, 10, 745, 343, 832, 144, 550, 403, 634, 579, 863, 164, 730, 562, 487, 23, 755, 957, 906, 378, 656, 18, 337, 446, 315, 36, 530, 826, 788, 384, 687, 760, 769, 161, 424, 57, 572, 506, 954, 192, 765, 111, 184, 732, 220, 602, 815, 930, 915, 284, 347, 441, 530, 378, 938, 246, 434, 848, 334, 259, 535, 747, 125, 137, 77, 881, 403, 390, 758, 298, 268, 440, 428, 793, 871, 364, 688, 180, 184, 957, 398, 300, 336, 981, 212, 650, 986, 742, 182, 553, 149, 898, 805, 796, 489, 727, 253, 333, 512, 464, 310, 688, 241, 533, 49, 31, 338, 500, 359, 403, 328, 277, 259, 844, 4, 802, 715, 209, 889, 596, 177, 521, 707, 435, 970, 960, 800, 990, 749, 833, 837, 845, 993, 585, 961, 783, 649, 677, 134, 517, 784, 491, 974, 668, 442, 200, 692, 549, 506, 951, 175, 292, 585, 98, 637, 561, 178, 500, 673, 812, 22, 893, 701, 216, 575, 642, 183, 814, 544, 926, 280, 683, 3, 588, 743, 815, 707, 88, 666, 886, 775, 861, 421, 542, 204, 469, 462, 698, 698, 893, 748, 576, 154, 372, 253, 120, 377, 549, 415, 492, 613, 377, 160, 325, 960, 245, 581, 697, 782, 663, 431, 71, 83, 484, 283, 454, 913, 219, 192, 77, 202, 184, 733, 775, 582, 945, 7, 445, 143, 909, 507, 600, 189, 158, 19, 800, 304, 61, 874, 945, 763, 452, 996, 667, 70, 705, 953, 877, 864, 57, 467, 320, 361, 543, 645, 749, 312, 821, 139, 176, 667, 908, 506, 943, 738, 167, 267, 803, 502, 40, 598, 699, 40, 259, 74, 28, 761, 482, 200, 402, 784, 878, 189, 405, 384, 260, 248, 354, 265, 26, 89, 685, 964, 618, 546, 424, 604, 339, 621, 343, 68, 401, 534, 69, 476, 826, 747, 497, 594, 553, 863, 238, 856, 787, 723, 18, 680, 797, 945, 822, 455, 0, 822, 245, 715, 184, 399, 597, 78, 780, 913, 85, 825, 873, 969, 550, 776, 729, 704, 582, 227, 723, 923, 120, 104, 207, 885, 977, 66, 393, 672, 236, 812, 85, 659, 36, 900, 46, 763, 481, 806, 545, 974, 312, 757, 66, 538, 689, 806, 632, 284, 717, 358, 490, 375, 873, 203, 601, 276, 121, 544, 16, 450, 310, 255, 274, 232, 520, 822, 908, 806, 254, 357, 365, 41, 967, 258, 894, 174, 764, 656, 906, 212, 362, 154, 371, 836, 365, 237, 651, 767, 126, 85, 361, 434, 399, 58, 362, 846, 343, 293, 492, 172, 451, 962, 293, 100, 777, 28, 788, 179, 10, 292, 53, 479, 126, 0, 433, 850, 525, 723, 276, 611, 66, 401, 536, 570, 798, 231, 993, 222, 171, 737, 961, 222, 430] bubble_sort:  181.51ms select_sort:   51.87ms insert_sort:   29.96ms  merge_sort:    3.12ms  quick_sort:    2.97ms

参考

十大常见排序算法
常见的基本排序算法
Data Structure Visualizations
Comparison Sorting Algorithms
VisuAlgo