当前位置： 首页 > article >正文

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

article 2024/11/27 2:58:23

文章目录

    • 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）

工作原理

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

实现步骤

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

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）

工作原理

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

实现步骤

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

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）

工作原理

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

实现步骤

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

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. 如果数组长度小于等于1，直接返回。
  2. 将数组分成两半，分别对左右两部分进行归并排序。
  3. 合并两部分，生成有序的数组。

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）

工作原理

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

实现步骤

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

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）

工作原理

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

实现步骤

  1. 将数组构建成一个最大堆。
  2. 将堆顶元素与数组末尾元素交换，缩小堆的范围。
  3. 对堆顶进行堆调整，保持堆性质。
  4. 重复步骤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中文版
在这里插入图片描述

实现步骤

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

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）

工作原理

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

实现步骤

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

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）

工作原理

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

实现步骤

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

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

10. 更多实用文章

【IDER、PyCharm】免费AI编程工具完整教程：ChatGPT Free - Support Key call AI GPT-o1 Claude3.5

【VScode】VSCode中的智能编程利器，全面揭秘ChatMoss & ChatGPT中文版

【OpenAI】获取OpenAI API Key的多种方式全攻略：从入门到精通，再到详解教程！！

11. 结语

通过这篇详尽的排序算法教程，希望能帮助你在编程学习和实际项目中游刃有余地应用各种排序技术，提升整体编程技能与算法素养。


http://www.kler.cn/a/410798.html

相关文章：

  • IDEA2024如何创建Web项目以及配置Tomcat
  • 【C++】深入哈希表核心：从改造到封装，解锁 unordered_set 与 unordered_map 的终极奥义！
  • css效果
  • PGSQL物化视图（Materialized View）
  • 图像标签格式转换
  • linux从0到1——shell编程9
  • 第二十天 模型评估与调优
  • LeetCode 872.叶子相似的树
  • DevExpress WinForms中文教程：Data Grid - 使用服务器模式的大数据源和即时反馈？
  • 在线课程管理：SpringBoot技术的应用
  • wordpress获取文章总数、分类总数、tag总数等
  • 解决 Android 单元测试 No tests found for given includes:
  • 【运维】 使用 shell 脚本实现类似 jumpserver 效果实现远程登录linux 服务器
  • Android数据存储——文件存储、SharedPreferences、SQLite、Litepal
  • sklearn学习
  • Golang 调用 mongodb 的函数
  • C++定义函数指针变量作为形参
  • JS的DOM操作和事件监听综合练习 （具备三种功能的轮播图案例）
  • 【MySQL】MySQL从入门到放弃
  • 一款开源在线项目任务管理工具
  • 后端并发编程操作简述 Java高并发程序设计 六类并发容器 七种线程池 四种阻塞队列
  • DM8 Docker环境部署
  • 贪心算法-区间问题 C++
  • 2025职业院校技能大赛信息安全管理与评估(河北省) 任务书
  • 即时通讯服务器被ddos攻击了怎么办？
  • php操作redis