【排序算法】python之冒泡，选择，插入，快速，归并_快速排序python

参考资料：

• 《Python实现5大排序算法》
• 《六大排序算法：插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序》 --代码似乎是C语言

————————
本文介绍5种常见的排序算法和基于Python实现：
冒泡排序（Bubble Sort）：通过不断交换相邻元素，将较大的元素逐渐“冒泡”到数组的尾部，较小的元素逐渐沉到数组的头部。
选择排序（Selection Sort）：每次从未排序的部分中选择最小（或最大）的元素，然后放到已排序部分的末尾（或开头）。
插入排序（Insertion Sort）：将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的适当位置，使其保持有序。
快速排序（Quick Sort）：通过递归地选择一个基准元素，并将数组划分为小于基准和大于基准的两部分，然后对两部分继续进行快速排序。
归并排序（Merge Sort）：将数组拆分成两个子数组，对每个子数组进行排序，然后再将两个有序子数组合并成一个有序数组。
不同的排序算法在时间复杂度、空间复杂度以及稳定性等方面有所不同，选择适合具体情况的排序算法可以提高排序效率。

一、冒泡排序

冒泡排序是一种简单的排序算法，它的思想是重复地走访过要排序的元素列，依次比较相邻的两个元素，如果它们的顺序错误就交换它们，直到没有任何再需要交换的元素，排序完成。

案例
我们以升序为实例。【34，,64，,11，,12，,22，,25，,90】长度为7.
第一次循环，要判断交换n-1次=6.两两交换，要将最大值90沉到末尾。结果为：【34，,11，,12，,22，,25，,64，,90】

第二次循环，要判断n-2次=5.两两交换，要将次最大值64沉到尾部(90之前)。结果为：
【11，,12，,22，,25，,34，,64，,90】
第三次循环，要判断n-3次=4. 值得注意的是，在这次循环中，没有一次交换行为。
第四次循环，要判断n-4次=3.值得注意的是，在这次循环中，没有一次交换行为。
第五次循环，要判断n-5次=2.值得注意的是，在这次循环中，没有一次交换行为。
第六次循环，要判断n-6次=1.值得注意的是，在这次循环中，没有一次交换行为。

因此，设置一个“标志位”，用于优化。若某次循环中没有交换元素，说明数组已经有序，可以提前结束排序。即在第三次循环中，判断没有交换，则可以提前结束优化了。

1.1 代码

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        # 标志位，用于优化：若某次循环中没有交换元素，说明数组已经有序，可以提前结束排序
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

1
2
3
4
5
6
7
8
9
10
11
12

测试

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr)  # 输出：[11, 12, 22, 25, 34, 64, 90]

1
2
3
4
5

在冒泡排序中，外层循环控制需要比较的次数，内层循环实际进行相邻元素的比较和交换。通过标志位swapped的引入，可以优化冒泡排序，当某次循环没有发生交换时，说明数组已经有序，可以提前结束排序。这样在数组近乎有序的情况下，冒泡排序的性能会有所提升。

改进
“swapped”是优化的循环次数，提前截止循环。当序列的长度足够大的时候，在循环的某次的内部是否可以提前截止交换呢？
【22，,12，,11，25, 34，,64 ，90】

假设，如果我们用last_swap_index记录当前轮次最后交换的位置。在下一轮的循环的时候，提前结束判断交换。则在每个循环轮次中节省很多判断和步骤。因此，优化后的代码为：

1.2 优化后的代码

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        # 记录当前轮循环最后一次交换的位置，初始值为未排序部分的末尾
        last_swap_index = n - 1

        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
                last_swap_index = j  # 更新最后一次交换的位置

        if not swapped:
            break
            

        # 更新下一轮未排序部分的边界
        n = last_swap_index + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.3 复杂度

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N)
空间复杂度：O(1)

二、选择排序

选择排序（Selection Sort）是一种简单直观的排序算法，其思想是在未排序部分找到最小（或最大）元素，然后与未排序部分的第一个元素交换位置。重复这个过程直到所有元素都有序。

2.1 代码

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        # 假设当前未排序部分的第一个元素是最小的
        min_idx = i

        # 在未排序部分中找到最小元素的索引
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j

        # 将找到的最小元素与未排序部分的第一个元素交换位置
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
1
2
3
4
5
6
7
8
9
10
11
12
13

测试

arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print(arr)  # 输出：[11, 12, 22, 25, 34, 64, 90]
1
2
3

在选择排序中，外层循环控制需要排序的次数，内层循环在未排序部分中找到最小元素的索引。然后将找到的最小元素与未排序部分的第一个元素交换位置。这样每一轮循环会将未排序部分的最小元素放到已排序部分的末尾，从而实现排序。选择排序的时间复杂度是O(n^2)，它是一个不稳定的排序算法。
改进
换个角度看，外层循环指示了已排序部分的末尾，要求所有的元素都必须经历排序，因此，外层循环是不可能像冒泡排序一样提前截止的。在每次循环的内部选择最小元素的时候，我们也必须在所有未排序的元素中选择，也不可以提前截止。因此，我们只能将优化的注意力放在“交换”上。
例如:【11，,12，,22，,25，,34，,90，,64】
第一次循环，位置arr[0], 选择最小的arr[0]–>交换
第二次循环，位置arr[1], 选择最小的arr[1]–>交换
第二次循环，位置arr[2], 选择最小的arr[2]–>交换
。。。
可以看到，出现了很多不必要的交换。因此，添加一个判断因素，从而停止交换。—提醒的是，计算机做判断的消耗的运行时间远远小于数组的位置交换所消耗的时间。

2.2 优化的代码

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_idx = i

        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j

        # 如果最小元素的索引不是当前的第一个元素，才进行交换
        if min_idx != i:
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
1
2
3
4
5
6
7
8
9
10
11
12

通过增加一个条件判断，只有当最小元素的索引不等于当前的第一个元素的索引时，才进行交换操作。这样就可以减少不必要的交换，进而优化选择排序的性能。这个优化对于已经近乎有序的数组尤为有效，因为这些情况下交换次数较少。尽管选择排序的时间复杂度仍然是O(n^2)，但这样的优化可以提高它的效率。

2.3 复杂度

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N^2)
空间复杂度：O(1)

三、插入排序

插入排序（Insertion Sort）是一种简单的排序算法，其基本思想是将数组分为已排序和未排序两个部分，逐个将未排序元素插入到已排序部分的适当位置，使其保持有序。

在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
  但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。

案例

3.1 代码

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]  # 当前要插入的元素
        j = i - 1  # 已排序部分的最后一个元素的索引

        # 逐个将已排序部分中比key大的元素后移，为key找到合适的插入位置
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1

        # 插入key到合适的位置
        arr[j + 1] = key
1
2
3
4
5
6
7
8
9
10
11
12
13

在插入排序中，外层循环控制需要插入的次数，从第2个元素开始（索引为1），依次向已排序部分插入未排序部分的元素。内层循环用于将已排序部分中比当前元素key大的元素后移，为key找到合适的插入位置。最后，将key插入到合适的位置，完成一次插入操作。

改进
在外层循环控制的插入次数，所有的元素都要被插入，因此无法提前截止。内层循环控制的是插入位置，一一倒序比较插入的位置是否合适。为了更快的找到插入位置，可以使用二分法判断插入位置。

3.2 优化的代码

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        left, right = 0, i - 1

        # 使用二分查找找到key应该插入的位置
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] > key:
                right = mid - 1
            else:
                left = mid + 1

        # 将已排序部分中大于key的元素都后移一位
        for j in range(i, left, -1):
            arr[j] = arr[j - 1]

        arr[left] = key

# 使用示例
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print(arr)  # 输出：[11, 12, 22, 25, 34, 64, 90]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.3 复杂度

时间复杂度

最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(N)，此时待排序列为升序，或者说接近升序。

空间复杂度：O(1)

四、快速排序

快速排序（Quick Sort）是一种高效的排序算法，它使用分治法来对数组进行排序。快速排序的基本思想是选择一个基准元素（pivot），然后将数组中小于等于基准的元素放在左边，大于基准的元素放在右边，然后分别对左右两部分递归地进行快速排序，直到整个数组有序为止。

案例
以【34，,25，,11，,22，,12，,64，,90】为例。

4.1 代码

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]  # 选择中间的元素作为基准
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)
1
2
3
4
5
6
7
8
9
10

改进
在优化快速排序的代码中，主要关注减少递归调用的次数和减少额外空间的使用。以下是针对这两方面的优化方法：

• 优化递归调用次数：对于小规模的子数组，可以切换到其他排序算法，例如插入排序。这是因为在小规模数据下，插入排序的常数项较小，比快速排序的递归开销更小。
• 减少额外空间的使用：原始的快速排序需要额外的数组空间用于存放左右子数组，但我们可以通过就地分区的方式来减少空间使用。

或者说是用挖坑法 减少额外空间的使用。注意，在减少空间使用的的快速排序算法有很多，下面这个动态图比较形象，所以放在这里的。这与我们 下面使用的partition的代码不一致。

4.2 优化的代码

对于小规模的子数组，切换到插入排序

def insertion_sort(arr, low, high):
    for i in range(low + 1, high + 1):
        key = arr[i]
        j = i - 1
        while j >= low and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key


def partition(arr, low, high):
    pivot = arr[high] ##注意这里的坑位与前面的动态图相反，选择的是最后一个位置而不是首位置
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        # 对于小规模的子数组，切换到插入排序
        if high - low + 1 <= 10:
            insertion_sort(arr, low, high)
        else:
            pivot_index = partition(arr, low, high)
            quick_sort(arr, low, pivot_index - 1)
            quick_sort(arr, pivot_index + 1, high)
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

测试

arr = [64, 34, 25, 12, 22, 11, 90]
quick_sort(arr, 0, len(arr) - 1)
print(arr)  # 输出：[11, 12, 22, 25, 34, 64, 90]
1
2
3

在优化后的代码中，我们引入了insertion_sort函数用于对小规模子数组进行插入排序。当子数组大小不超过10个元素时，切换到插入排序。同时，在quick_sort函数中采用就地分区的方法，减少了额外的空间使用。
这些优化方法可以提高快速排序在小规模数据和近乎有序数组的性能。但需要注意的是，优化的效果也依赖于具体的数据情况

4.3 案例讲解–partition的应用

以【72，,64，,34，,25，,12，,22，,90，,17，,45，,58】为例。当子数组规模小于3的时候，切换到“插入排序”。以其中一轮为例。

递归调用的树状图

五、 归并算法

归并排序（Merge Sort）是一种高效稳定的排序算法，它使用分治法将数组分为两个子数组，递归地对子数组进行排序，然后将排好序的子数组合并成一个有序数组。

5.1 代码

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 将数组一分为二
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    # 递归对左右两部分进行归并排序
    left = merge_sort(left)
    right = merge_sort(right)

    # 合并已排序的左右两部分
    return merge(left, right)

def merge(left, right):
    merged = []
    left_idx, right_idx = 0, 0

    while left_idx < len(left) and right_idx < len(right):
        if left[left_idx] < right[right_idx]:
            merged.append(left[left_idx])
            left_idx += 1
        else:
            merged.append(right[right_idx])
            right_idx += 1

    # 将剩余的元素加入合并后的数组
    merged.extend(left[left_idx:])
    merged.extend(right[right_idx:])

    return merged


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