Python 实现十大经典排序算法详解：原理、代码与复杂度分析

Python 实现十大经典排序算法详解

本文详细讲解冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数等十种经典排序算法的 Python 实现。涵盖算法原理、图解流程、核心代码及时间空间复杂度分析，并提供算法选型建议，帮助开发者深入理解数据结构与算法基础。

01 冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访序列的工作是重复地进行直到没有再需要交换，也就是说该序列已经排序完成。

算法过程

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

算法特点

• 稳定性：稳定（相等元素的相对位置不变）
• 时间复杂度：
  • 最好情况：O(n)（已排序）
  • 平均情况：O(n^2)
  • 最坏情况：O(n^2)
• 空间复杂度：O(1)

Python 代码

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        swapped = False
        for j in range(1, n - i):
            if lst[j - 1] > lst[j]:
                lst[j - 1], lst[j] = lst[j], lst[j - 1]
                swapped = True
        if not swapped:
            break
    return lst 

02 选择排序

选择排序（Selection Sort）的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。

算法特点

• 稳定性：不稳定
• 时间复杂度：O(n^2)，无论数据初始状态如何
• 空间复杂度：O(1)

Python 代码

def selection_sort(lst):
    for i in range(len(lst) - 1):  
        min_index = i
        for j in range(i + 1, len(lst)):
            if lst[j] < lst[min_index]:
                min_index = j  
        lst[i], lst[min_index] = lst[min_index], lst[i] 
    return lst

03 快速排序

快速排序（Quick Sort）由东尼·霍尔提出。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

算法过程

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

算法特点

• 稳定性：不稳定
• 时间复杂度：
  • 最好/平均：O(n log n)
  • 最坏：O(n^2)
• 空间复杂度：O(log n) ~ O(n)

Python 代码

def quick_sort(lst):  
    n = len(lst)
    if n <= 1:
        return lst
    baseline = lst[0] 
    left = [lst[i] for i in range(1, len(lst)) if lst[i] < baseline] 
    right = [lst[i] for i in range(1, len(lst)) if lst[i] >= baseline]
    return quick_sort(left) + [baseline] + quick_sort(right)

04 归并排序

归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

算法特点

• 稳定性：稳定
• 时间复杂度：O(n log n)，始终如一
• 空间复杂度：O(n)

Python 代码

def merge_sort(lst):
    def merge(left, right):
        i = 0
        j = 0   
        result = []    
        while i < len(left) and j < len(right):  
            if left[i] <= right[j]:    
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result = result + left[i:] + right[j:]
        return result
    n = len(lst)
    if n <= 1:     
        return lst 
    mid = n // 2 
    left = merge_sort(lst[:mid])
    right = merge_sort(lst[mid:])
    return merge(left, right)

05 堆排序

堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法特点

• 稳定性：不稳定
• 时间复杂度：O(n log n)
• 空间复杂度：O(1)

Python 代码

def heap_sort(lst):
    def adjust_heap(lst, i, size):
        left_index = 2 * i + 1
        right_index = 2 * i + 2
        largest_index = i 
        if left_index < size and lst[left_index] > lst[largest_index]: 
            largest_index = left_index 
        if right_index < size and lst[right_index] > lst[largest_index]: 
            largest_index = right_index 
        if largest_index != i: 
            lst[largest_index], lst[i] = lst[i], lst[largest_index] 
            adjust_heap(lst, largest_index, size)

    def built_heap(lst, size):
        for i in range(len(lst)//2)[::-1]: 
            adjust_heap(lst, i, size) 

    size = len(lst)
    built_heap(lst, size) 
    for i in range(len(lst))[::-1]:         
        lst[0], lst[i] = lst[i], lst[0]
        adjust_heap(lst, 0, i) 
    return lst

06 插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法特点

• 稳定性：稳定
• 时间复杂度：
  • 最好：O(n)
  • 平均/最坏：O(n^2)
• 空间复杂度：O(1)

Python 代码

def insertion_sort(lst):
    for i in range(len(lst) - 1):
        cur_num, pre_index = lst[i+1], i
        while pre_index >= 0 and cur_num < lst[pre_index]:
            lst[pre_index + 1] = lst[pre_index]
            pre_index -= 1
        lst[pre_index + 1] = cur_num 
    return lst

07 希尔排序

希尔排序（Shell Sort）是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

算法特点

• 稳定性：不稳定
• 时间复杂度：取决于增量序列，通常优于 O(n^2)
• 空间复杂度：O(1)

Python 代码

def shell_sort(lst):
    n = len(lst)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            for j in range(i, gap - 1, -gap):
                if lst[j] < lst[j - gap]:
                    lst[j], lst[j - gap] = lst[j - gap], lst[j]
                else:
                    break
        gap //= 2
    return lst

08 计数排序

计数排序（Counting Sort）的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。要求输入的数据必须是整数，且范围不能太大。

算法特点

• 稳定性：稳定
• 时间复杂度：O(n + k)，k 为数据范围
• 空间复杂度：O(k)

Python 代码

def counting_sort(lst):
    nums_min = min(lst)
    bucket = [0] * (max(lst) + 1 - nums_min)
    for num in lst:
        bucket[num - nums_min] += 1
    i = 0
    for j in range(len(bucket)):
        while bucket[j] > 0:
            lst[i] = j + nums_min
            bucket[j] -= 1
            i += 1
    return lst

09 桶排序

桶排序（Bucket Sort）是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要选择合适的桶的数量和分布范围。

算法特点

• 稳定性：稳定
• 时间复杂度：平均 O(n+k)，最坏 O(n^2)
• 空间复杂度：O(n+k)

Python 代码

def bucket_sort(lst, defaultBucketSize=4):
    maxVal, minVal = max(lst), min(lst)
    bucketSize = defaultBucketSize
    bucketCount = (maxVal - minVal) // bucketSize + 1  
    buckets = [[] for i in range(bucketCount)]
    for num in lst:
        buckets[(num - minVal) // bucketSize].append(num)
    lst.clear()  
    for bucket in buckets:
        # 此处复用冒泡排序逻辑，实际可用其他排序
        bubble_sort(bucket)  
        lst.extend(bucket)
    return lst

10 基数排序

基数排序（Radix Sort）属于分配式排序，又称桶子法（Bucket Sort）或 Bin Sort。它是透过键值的部份信息，将要排序的元素分配至某些桶中，以达到排序的作用。基数排序法有两种：最高位优先（MSD）法和最低位优先（LSD）法。

算法特点

• 稳定性：稳定
• 时间复杂度：O(d*(n+r))，d 为位数，r 为基数
• 空间复杂度：O(n+r)

Python 代码

def radix_sort(lst):
    mod = 10
    div = 1
    mostBit = len(str(max(lst))) 
    buckets = [[] for row in range(mod)] 
    while mostBit:
        for num in lst:  
            buckets[num // div % mod].append(num)
        i = 0  
        for bucket in buckets:  
            while bucket:
                lst[i] = bucket.pop(0)
                i += 1
        div *= 10
        mostBit -= 1
    return lst

各算法复杂度对比表

算法	最好时间	平均时间	最坏时间	空间复杂度	稳定性
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
希尔排序	O(n log n)	O(n log n)	O(n^2)	O(1)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n log n)	O(n^2)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
计数排序	O(n+k)	O(n+k)	O(n+k)	O(k)	稳定
桶排序	O(n+k)	O(n+k)	O(n^2)	O(n+k)	稳定
基数排序	O(d*(n+r))	O(d*(n+r))	O(d*(n+r))	O(n+r)	稳定

算法选用建议

在实际开发中，选择排序算法需考虑以下因素：

1. 数据规模：

   • 小规模数据（N < 50）：插入排序、冒泡排序即可，实现简单。
   • 中等规模数据：快速排序、归并排序、堆排序。
   • 大规模数据：归并排序、快速排序。

2. 数据特征：

   • 基本有序：插入排序、冒泡排序效率较高。
   • 数据范围已知且较小：计数排序、基数排序效率极高。
   • 数据分布均匀：桶排序效果较好。

3. 稳定性要求：

   • 若需保持相等元素相对顺序（如多关键字排序），必须选择稳定排序（归并、插入、计数、桶、基数）。

4. 内存限制：

   • 内存紧张时，避免使用归并排序（O(n) 空间），优先选择原地排序（堆、快排、插入）。

总结

以上是用 Python 实现的十种经典排序算法。代码实现并非重点，理解算法思想、适用场景及性能差异更为关键。掌握这些基础算法有助于优化程序性能，解决复杂工程问题。