WoodenRobot's Blog
0%

常见排序算法 Python 实现及舞蹈展示

发表于 分类于 Disqus：
本文字数： 4.3k 阅读时长 ≈ 4 分钟

前言

整理了一下常见排序算法 Python 的实现和动图及舞蹈视频对算法运行过程的可视化展示。

冒泡排序

工作原理

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

    复杂度

最坏时间复杂度 最优时间复杂度 平均时间复杂度 额外空间复杂度 稳定性
O(N^2) O(N) O(N^2) O(1) 稳定

实现

1
2
3
4
5
6
7
8
def bubble_sort(alist):
    # 首先得到每个循环需要比较的次数，第一次从0位置开始需要比较 len(alist) - 1 次
    for passnum in range(len(alist)-1, 0, -1):
        # 相邻两个位置不断比较，如果左边的数大于右边就交换位置
        for i in range(passnum):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
    return alist

可视化

选择排序

工作原理

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。步骤如下：

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描;
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置;
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5。

复杂度

最坏时间复杂度 最优时间复杂度 平均时间复杂度 额外空间复杂度 稳定性
O(N^2) O(N^2) O(N^2) O(1) 稳定

实现

1
2
3
4
5
6
7
8
9
def select_sort(alist):
    for i in range(len(alist) - 1):
        min_index = i
        for j in range(i + 1, len(alist)):
            if alist[j] < alist[min_index]:
                min_index = j

        alist[i], alist[min_index] = alist[min_index], alist[i]
    return alist

可视化

插入排序

工作原理

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

复杂度

最坏时间复杂度 最优时间复杂度 平均时间复杂度 额外空间复杂度 稳定性
O(N^2) O(N) O(N^2) O(1) 稳定

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
def insertion_sort(alist):
    # 从索引为 1 的值开始从后向前扫描
    for i in range(1, len(alist)):
        current_value = alist[i]
        position = i
        # 如果前一个数大于当前值则将前一个数向右移动一位，直到找到前一个数小于当前值得位置，将该位置的值设为当前值
        while position > 0 and alist[position - 1] > current_value:
            alist[position] = alist[position - 1]
            position -= 1

        alist[position] = current_value
    return alist

可视化

希尔排序

工作原理

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。

复杂度

最坏时间复杂度 最优时间复杂度 平均时间复杂度 额外空间复杂度 稳定性
O(NlogN) O(N^2) - O(1) 不稳定

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def shell_sort(alist):
    sub_list_count = len(alist) // 2
    while sub_list_count > 0:
        for start_position in range(sub_list_count):
           alist = gap_insertion_sort(alist, start_position, sub_list_count)

        print('After increments of size', sub_list_count, 'The list is', alist)
        sub_list_count = sub_list_count // 2
    return alist


def gap_insertion_sort(alist, start, gap):
    for i in range(start + gap, len(alist), gap):
        current_value = alist[i]
        position = i

        while position >= gap and alist[position - gap] > current_value:
            alist[position] = alist[position - gap]
            position = position - gap

        alist[position] = current_value
    return alist

可视化

快速排序

工作原理

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。步骤如下：

  1. 从数列中挑出一个元素，称为“基准”（pivot）；
  2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作；
  3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

复杂度

最坏时间复杂度 最优时间复杂度 平均时间复杂度 额外空间复杂度 稳定性
O(N^2) O(NlogN) O(NlogN) O(logN) 不稳定

实现

快速排序首先选择一个值，该值称为 枢轴值。虽然有很多不同的方法来选择枢轴值，我们将使用列表中的第一项。

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
def quick_sort(alist):
    quick_sort_helper(alist, 0, len(alist) - 1)


def quick_sort_helper(alist, first, last):
    if first < last:
        splitpoint = partition(alist, first, last)
        alist = quick_sort_helper(alist, first, splitpoint - 1)
        alist = quick_sort_helper(alist, splitpoint + 1, last)
    return alist


def partition(alist, first, last):
    pivotvalue = alist[first]

    leftmark = first + 1
    rightmark = last

    done = False
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
            leftmark += 1

        while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
            rightmark -= 1

        if rightmark < leftmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp

    temp = alist[first]
    alist[first] = alist[rightmark]
    alist[rightmark] = temp

    return rightmark

可视化

下图是以最后一项为枢轴值：

视频中以第一项为枢轴值：

归并排序

工作原理

归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
步骤如下：

  1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
  3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
  4. 重复步骤3直到某一指针到达序列尾；
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

复杂度

最坏时间复杂度 最优时间复杂度 平均时间复杂度 额外空间复杂度 稳定性
O(NlogN) O(NlogN) O(NlogN) O(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
def merge_sort(alist):
    if len(alist) > 1:
        mid = len(alist) // 2
        left_half = alist[:mid]
        right_half = alist[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = 0
        j = 0
        k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                alist[k] = left_half[i]
                i += 1

            else:
                alist[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            alist[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            alist[k] = right_half[j]
            j += 1
            k += 1
    return alist

可视化

小彩蛋

不同的排序算法听起来是什么样的？

参考

  1. 中文维基百科
  2. AlgoRythmics - YouTube
  3. What different sorting algorithms sound like

欢迎关注我的其它发布渠道