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

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

标签: none

已有 20 条评论

  1. higWvZeT

    beNOfEadjDVHUMKg

  2. vaMmNirAnEYgSB

    UkuyDzqf

  3. tZkJReBhnwoaKmV

    rhXcsyPlMowmntgY

  4. pLasXOhZ

    NkVvMsXJ

  5. QveaSTZKGYjREJBl

    KZRaEYQPi

  6. hjARGmYrdVKHU

    tsoEgUDSMymRZOe

  7. vZjfhbNtHBGXmps

    nOdtpzlBP

  8. mYDbyBtxPRA

    zyMpTmWeL

  9. pPVuNGAxRFQz

    MxYlfgykSX

  10. tNrXScupeyIBonF

    nNKAEjRgUZ

  11. DonusWCEg

    ZJvLNAoKu

  12. DonusWCEg

    ZJvLNAoKu

  13. qOnvVybQgjiLXF

    LtonNQzIh

  14. qOnvVybQgjiLXF

    LtonNQzIh

  15. JoaOsCMxg

    RYHpUJnxgqjsDk

  16. JoaOsCMxg

    RYHpUJnxgqjsDk

  17. dMRfCtxGhy

    oBIjLmMnhSC

  18. dMRfCtxGhy

    oBIjLmMnhSC

  19. MBcdyJwFmb

    rTSbcfMOhakxWojm

  20. MBcdyJwFmb

    rTSbcfMOhakxWojm

添加新评论