常见排序算法

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

冒泡排序的实现如下，简单观察就可以知道它的时间复杂度为 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)

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)

包含所有排序算法和测试的完整代码如下
highlight python
执行结果如下

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