跳转至

11 排序算法

排序是计算机科学中最基础且重要的算法之一，Python作为一门功能强大的编程语言，提供了多种内置和第三方库的排序方法。在实际开发中，根据不同的数据规模、应用场景和性能需求，选择合适的排序算法至关重要。

Python内置的排序功能主要有：

  1. sorted()函数 - 返回一个新的已排序列表，不改变原序列 
    1
2
3
4
    nums = [3, 1, 4, 2]
sorted_nums = sorted(nums)      # [1, 2, 3, 4]
print(nums)        # 原列表未变，仍是 [3, 1, 4, 2]
print(sorted_nums) # 新列表
  2. list.sort()方法 - 原地排序列表，不返回新列表 
    1
2
3
    letters = ['b', 'd', 'a', 'c']
letters.sort()     # 直接修改列表本身
print(letters)     # ['a', 'b', 'c', 'd']
    以上两种方法都可以通过添加 reverse=True 实现递减的排列，但是如果要深入了解排序的原理，我们就得自己手搓算法，实现排序需求了，以下整理了8种不同的排序方式，我们来详细分析一下。

冒泡排序

冒泡排序通过多次遍历列表，比较相邻元素并交换它们的位置，将较大的元素逐渐“浮”到列表末尾，这里我添加了一个reverse参数，用于实现降序排序，时间复杂度为O(n²)。 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def bubble_sort(arr,reverse=False):
    n = len(arr)
    for i in range(n): # 外层循环表示要冒泡的次数
        for j in range(0, n-i-1): # 内层循环实现冒泡
            if reverse:
                if arr[j] < arr[j+1]: 
                    arr[j], arr[j+1] = arr[j+1], arr[j]
            else:
                if arr[j] > arr[j+1]: 
                    arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

print(bubble_sort([2,3,1])) # [1, 2, 3]
print(bubble_sort([2,3,1],reverse=True)) # [3, 2, 1]

选择排序

选择排序每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。时间复杂度为O(n²)，reverse 在此处就决定交换的是最大值还是最小值的索引。 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def selection_sort(arr,reverse=False):
    n = len(arr)
    for i in range(n): # 循环的长度，比arr的长度少1
        if not reverse:
            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]
        else:
            max_idx = i # 假设当前元素是最大的
            for j in range(i+1, n):
                if arr[j] > arr[max_idx]:
                    max_idx = j # 找到最大的元素的索引，并更新
            arr[i], arr[max_idx] = arr[max_idx], arr[i]
    return arr

print(selection_sort([2,7,3])) # 输出: [2, 3, 7]
print(selection_sort([2,7,3],reverse=True)) # 输出: [7, 3, 2]

插入排序

插入排序将未排序部分的元素逐个插入到已排序部分的正确位置。时间复杂度为O(n²)，在近乎有序的列表上表现较好（因为如果已经近乎有序，那while大部分情况下就会提前终止循环）。 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def insertion_sort(arr,reverse=False):
    for i in range(1, len(arr)):
        key = arr[i] # 存放当前要插入的元素
        j = i-1
        if not reverse:
            while j >= 0 and key < arr[j]: # 从已排序部分从后向前扫描
                arr[j+1] = arr[j] # 发现比key大的元素，向后移动一位
                j -= 1
        else:
            while j >= 0 and key > arr[j]:
                arr[j+1] = arr[j] # 发现比key小的元素，向后移动一位
                j -= 1
        arr[j+1] = key # 停止扫描，将key插入到正确的位置
    return arr

print(insertion_sort([2,7,3])) # 输出: [2, 3, 7]
print(insertion_sort([2,7,3],reverse=True)) # 输出: [7, 3, 2]

快速排序

快速排序通过选择一个“基准”元素，将列表分为小于基准和大于基准的两部分，递归排序子列表。平均时间复杂度为O(n log n)。 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def quick_sort(arr,reverse=False):
    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] # 大于中间值的所有元素构成一个列表
    if reverse: # 递归调用，对左右两个子列表进行排序，并将结果合并
        return quick_sort(right,reverse=True) + middle + quick_sort(left,reverse=True)
    else:
        return quick_sort(left) + middle + quick_sort(right)

print(quick_sort([1,6,5,3,2,4])) # 输出：[1, 2, 3, 4, 5, 6]
print(quick_sort([1,6,5,3,2,4],reverse=True)) # 输出：[6, 5, 4, 3, 2, 1]

归并排序

归并排序将列表递归分成两半，分别排序后再合并。时间复杂度为O(n log 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
33
34
35
def merge_sort(arr,reverse=False):
    if len(arr) > 1:
        mid = len(arr)//2 # 向下取整
        left = arr[:mid]
        right = arr[mid:]

        merge_sort(left, reverse)  # 递归排序左半部分
        merge_sort(right, reverse)  # 递归排序右半部分

        i = j = k = 0
        while i < len(left) and j < len(right): # 合并两个子数组
            # 根据 reverse 参数决定排序顺序
            condition = left[i] < right[j] if not reverse else left[i] > right[j]
            if condition:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1

    return arr

print(merge_sort([38, 27, 43, 3, 9, 82, 10])) # 输出: [3, 9, 10, 27, 38, 43, 82]
print(merge_sort([38, 27, 43, 3, 9, 82, 10], reverse=True)) # 反之

堆排序

堆排序利用堆数据结构，将列表构建为最大堆，依次取出堆顶元素完成排序。时间复杂度为O(n log 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
def heapify(arr, n, i, reverse=False):
    largest_or_smallest = i
    left = 2 * i + 1 # 左子节点索引
    right = 2 * i + 2 # 右子节点索引

    if left < n and ((arr[left] > arr[largest_or_smallest]) if not reverse else (arr[left] < arr[largest_or_smallest])):
        largest_or_smallest = left # 如果左子节点更大/更小，更新largest_or_smallest
    if right < n and ((arr[right] > arr[largest_or_smallest]) if not reverse else (arr[right] < arr[largest_or_smallest])):
        largest_or_smallest = right # 如果右子节点更大/更小，更新largest_or_smallest
    if largest_or_smallest != i:
        arr[i], arr[largest_or_smallest] = arr[largest_or_smallest], arr[i]  
        heapify(arr, n, largest_or_smallest, reverse) # 递归调用heapify

def heap_sort(arr, reverse=False):
    n = len(arr)
    for i in range(n//2 - 1, -1, -1): # 从最后一个非叶子节点开始构建堆
        heapify(arr, n, i, reverse)
    for i in range(n-1, 0, -1): # 一个个从堆中取出元素
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0, reverse)
    return arr

print(heap_sort([3, 6, 8, 10, 1, 2, 1])) # 输出: [1, 1, 2, 3, 6, 8, 10]
print(heap_sort([3, 6, 8, 10, 1, 2, 1], reverse=True)) # 反之

计数排序

计数排序适用于整数且范围较小的列表，通过统计元素出现次数完成排序。时间复杂度为O(n + k)，k为数据范围。 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def counting_sort(arr,reverse=False):
    max_val = max(arr)
    count = [0] * (max_val + 1)
    for num in arr:
        if not reverse:
            count[num] += 1 # 相当于在对应的位置打了一个标记
        else:
            count[max_val-num] += 1 # 同理，只不过记录的位置相反
    sorted_arr = []
    for i in range(max_val + 1):
        # 有可能会存在相同的数，因此用extend进行扩展
        if not reverse:
            sorted_arr.extend([i] * count[i]) # 将对应位置的数值添加到结果数组中
        else:
            sorted_arr.extend([max_val-i] * count[i]) # 计算和最大值之间的差值添加到结果数组中
    return sorted_arr

print(counting_sort([4, 2, 2, 8, 3, 3, 1])) # 输出: [1, 2, 2, 3, 3, 4, 8]
print(counting_sort([4, 2, 2, 8, 3, 3, 1],reverse=True)) # 反之

基数排序

基数排序按数字的每一位进行排序，从低位到高位依次处理。时间复杂度为O(nk)，k为数字的最大位数。 

 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
def counting_sort_radix(arr, exp, reverse=False):
    n = len(arr)
    output = [0] * n  # 输出数组
    count = [0] * 10  # 计数数组

    # 统计每个数字出现的次数
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    # 根据 reverse 参数决定累加方向
    if not reverse:
        # 升序累加
        for i in range(1, 10):
            count[i] += count[i - 1]
    else:
        # 降序累加
        for i in range(8, -1, -1):
            count[i] += count[i + 1]

    # 构建输出数组
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        pos = count[index % 10] - 1
        output[pos] = arr[i]
        count[index % 10] -= 1
        i -= 1

    # 将排序结果复制回原数组
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr, reverse=False):
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    # 按位排序
    while max_val // exp > 0:
        counting_sort_radix(arr, exp, reverse)
        exp *= 10
    return arr

# 示例：升序和降序排序
arr1 = [170, 45, 75, 90, 802, 24, 2, 66]
print('升序:', radix_sort(arr1.copy()))
print('降序:', radix_sort(arr1.copy(), reverse=True))

比较与选择

最后给出一张详细的对比表，可以参考，在大多数情况下都可以选用前面几种常见的排序方式，但是涉及到大规模的数据的时候，更加精细化的排序就能大展拳脚了！

排序算法 平均时间复杂度 适用场景
冒泡排序 O(n²) 小规模数据或接近有序数据
选择排序 O(n²) 小规模数据，交换成本较高时
插入排序 O(n²) 小规模或基本有序数据
快速排序 O(n log n) 大规模数据，通用高效场景
归并排序 O(n log n) 大规模数据，需稳定排序时
堆排序 O(n log n) 大规模数据，内存受限时
计数排序 O(n + k) 非负整数且数据范围较小
基数排序 O(n × k) 非负整数，位数均匀分布