代码收藏家技术教程 2024-11-29

【Python】九大经典排序算法：从入门到精通的详解（冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序、计数排序、基数排序、桶排序）

文章目录

1. 冒泡排序（Bubble Sort）

2. 选择排序（Selection Sort）

3. 插入排序（Insertion Sort）

4. 归并排序（Merge Sort）

5. 快速排序（Quick Sort）

6. 堆排序（Heap Sort）

7. 计数排序（Counting Sort）

8. 基数排序（Radix Sort）

9. 桶排序（Bucket Sort）

10. 更多实用文章

11. 结语

排序算法对比表格

排序算法	时间复杂度	空间复杂度	稳定性	适用场景
冒泡排序	O(n²)	O(1)	稳定	小规模数据或几乎有序的数据
选择排序	O(n²)	O(1)	不稳定	数据量小且对稳定性无要求
插入排序	O(n²)	O(1)	稳定	小规模数据或几乎有序的数据
归并排序	O(n log n)	O(n)	稳定	大规模数据需要稳定性的场景
快速排序	O(n log n)	O(log n)	不稳定	大规模数据，平均情况高效
堆排序	O(n log n)	O(1)	不稳定	大规模数据，不需要稳定性
计数排序	O(n + k)	O(k)	稳定	整数且范围有限的数据
基数排序	O(d*(n + k))	O(n + k)	稳定	大规模整数或可以分位处理的数据
桶排序	O(n + k)	O(n)	稳定	均匀分布的大规模数据

1. 冒泡排序（Bubble Sort）

工作原理

冒泡排序是一种简单的交换排序算法，通过重复遍历要排序的列表，比较相邻元素并交换顺序错误的元素，直到整个列表有序。每一次遍历都会将未排序部分的最大元素“冒泡”到列表末尾。

实现步骤

从列表的起始位置开始，比较相邻的两个元素。
如果前一个元素比后一个元素大，则交换它们的位置。
对整个列表重复上述过程，每完成一轮遍历，未排序部分的元素数量减少一位。
当一轮遍历未发生任何交换时，意味着列表已经有序，可以提前终止算法。

Python 实现

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, 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
    return arr

优点：

实现简单，理解容易。

对于少量数据或已经基本有序的数据，效率较高。

缺点：

时间复杂度高，为 O(n²)。

不适合大规模数据排序。

2. 选择排序（Selection Sort）

工作原理

选择排序是一种简单直观的排序算法。它通过多次从未排序部分选择最小（或最大）的元素，放到已排序部分的末尾，逐步完成排序过程。

实现步骤

从未排序部分中找到最小的元素。
将该最小元素与未排序部分的第一个元素交换位置。
缩小未排序部分的范围，重复上述过程，直到所有元素都有序。

Python 实现

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        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]
    return arr

优点：

实现简单，无需额外的内存空间。

适用于数据量较小的情况。

缺点：

时间复杂度为 O(n²)，效率较低。

不稳定排序，可能破坏相同元素的相对顺序。

3. 插入排序（Insertion Sort）

工作原理

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

实现步骤

从第二个元素开始，假设第一个元素为已排序部分。
取未排序部分的第一个元素，将其插入到已排序部分的适当位置。
重复上述过程，直到整个列表有序。

Python 实现

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

优点：

实现简单，效率较高，对于少量数据或基本有序的数据效果不错。

稳定排序，保持相同元素的相对位置。

缺点：

最坏情况下时间复杂度为 O(n²)。

对于大规模数据排序效率低下。

4. 归并排序（Merge Sort）

工作原理

归并排序采用分治法，将数组分成两半，分别进行排序后再合并。其核心在于有效地将两个有序数组合并成一个有序数组。

体验最新GPT系列模型、支持自定义助手、文件上传等功能：ChatMoss & ChatGPT-AI中文版

实现步骤

如果数组长度小于等于1，直接返回。
将数组分成两半，分别对左右两部分进行归并排序。
合并两部分，生成有序的数组。

Python 实现

def merge_sort(arr):
    if len(arr) <=1:
        return arr
    mid = len(arr)//2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    merged = []
    i=j=0
    while i<len(left) and j<len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i+=1
        else:
            merged.append(right[j])
            j+=1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

优点：

时间复杂度稳定为 O(n log n)。

稳定排序，保持相同元素的相对位置。

适用于大规模数据。

缺点：

需要额外的内存空间，空间复杂度为 O(n)。

5. 快速排序（Quick Sort）

工作原理

快速排序同样采用分治策略，通过选择一个“基准”元素，将数组分成两部分，一部分小于基准元素，另一部分大于基准元素，然后递归排序两部分。

实现步骤

选择数组中的一个元素作为基准（通常选择第一个元素）。
重新排列数组，将小于基准的元素放到左边，大于基准的元素放到右边。
递归对左右两部分进行快速排序。

Python 实现

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)

优点：

平均时间复杂度为 O(n log n)，表现优异。

不需要额外的内存空间（原地排序实现时）。

通常比其他 O(n log n) 算法更快，尤其在实践中表现良好。

缺点：

最坏情况下时间复杂度为 O(n²)，如已排序数据。

不稳定排序，可能破坏相同元素的相对位置。

6. 堆排序（Heap Sort）

工作原理

堆排序利用堆这种数据结构，首先将数组构建成一个最大堆（或最小堆），然后依次将堆顶元素（最大或最小）移到数组末尾，调整堆，重复此过程直到整个数组有序。

实现步骤

将数组构建成一个最大堆。
将堆顶元素与数组末尾元素交换，缩小堆的范围。
对堆顶进行堆调整，保持堆性质。
重复步骤2和3，直到堆的范围为1。

Python 实现

def heapify(arr, n, i):
    largest = i
    l = 2*i +1
    r = 2*i +2
    if l < n and arr[l] > arr[largest]:
        largest = l
    if r < n and arr[r] > arr[largest]:
        largest = r
    if largest !=i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n//2 -1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

优点：

时间复杂度为 O(n log n)。

不需要额外的内存空间（原地排序）。

对于大规模数据表现稳定。

缺点：

通常比快速排序慢，常数因子较大。

不稳定排序，可能破坏相同元素的相对位置。

7. 计数排序（Counting Sort）

工作原理

计数排序是一种稳定的线性时间排序算法，适用于元素范围较小的整数排序。它通过统计每个元素出现的次数，计算元素的位置，最后构建有序数组。

体验最新GPT系列模型、支持自定义助手、文件上传等功能：ChatMoss & ChatGPT-AI中文版

实现步骤

找到待排序数组的最大值和最小值。
创建一个计数数组，统计每个元素的出现次数。
计算计数数组的前缀和，确定每个元素在有序数组中的位置。
构建有序数组，确保稳定性。

Python 实现

def counting_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    min_val = min(arr)
    range_of_elements = max_val - min_val +1
    count = [0]*range_of_elements
    for num in arr:
        count[num - min_val] +=1
    for i in range(1, len(count)):
        count[i] += count[i-1]
    output = [0]*len(arr)
    for num in reversed(arr):
        output[count[num - min_val] -1] = num
        count[num - min_val] -=1
    return output

优点：

时间复杂度为 O(n + k)，其中 k 是元素的范围。

稳定排序，保持相同元素的相对顺序。

缺点：

只能用于整数排序，且元素范围较小。

需要额外的内存空间，尤其当元素范围较大时。

8. 基数排序（Radix Sort）

工作原理

基数排序是一种非比较型排序算法，通过将元素按位（如个位、十位等）进行多次排序，实现整体有序。常结合计数排序作为子过程。

实现步骤

确定元素的最大位数。
从最低位开始，对所有元素进行稳定排序（如使用计数排序）。
重复上述过程，直到所有位数排序完成。

Python 实现

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0]*n
    count = [0]*10
    for num in arr:
        index = num//exp
        count[index %10] +=1
    for i in range(1,10):
        count[i] += count[i-1]
    for num in reversed(arr):
        index = num//exp
        output[count[index %10] -1] = num
        count[index %10] -=1
    return output

def radix_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    exp =1
    while max_val//exp >0:
        arr = counting_sort_for_radix(arr, exp)
        exp *=10
    return arr

优点：

时间复杂度为 O(d*(n + k))，d 是位数，k 是基数。

稳定排序，保持相同元素的相对顺序。

适用于大规模数据和大位数整数排序。

缺点：

只能用于整数排序，或可以拆分为位进行排序的对象。

需要额外的内存空间，尤其是基数较大时。

9. 桶排序（Bucket Sort）

工作原理

桶排序将元素分到多个桶中，每个桶内部再采用其他排序算法排序，最后将所有桶中的元素按顺序合并。适用于元素均匀分布的情况。

实现步骤

确定桶的数量和范围。
将每个元素分配到对应的桶中。
对每个桶内部进行排序（如使用插入排序）。
按顺序合并所有桶中的元素，得到有序数组。

Python 实现

def bucket_sort(arr):
    if not arr:
        return arr
    bucket_count = 10
    min_val = min(arr)
    max_val = max(arr)
    range_val = (max_val - min_val)/bucket_count
    buckets = [[] for _ in range(bucket_count)]
    for num in arr:
        index = int((num - min_val)/range_val)
        if index == bucket_count:
            index -=1
        buckets[index].append(num)
    for bucket in buckets:
        insertion_sort(bucket)
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)
    return sorted_arr