详细讲解了冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数等十种经典排序算法的 Python 实现。涵盖算法原理、图解流程、核心代码及时间空间复杂度分析，并提供算法选型建议，帮助开发者深入理解数据结构与算法基础。文章包含各算法复杂度对比表及选用指南，适合计算机专业学生及后端开发人员阅读。
本文详细讲解冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数等十种经典排序算法的 Python 实现。涵盖算法原理、图解流程、核心代码及时间空间复杂度分析，并提供算法选型建议，帮助开发者深入理解数据结构与算法基础。
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访序列的工作是重复地进行直到没有再需要交换，也就是说该序列已经排序完成。
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
选择排序（Selection Sort）的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
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
快速排序（Quick Sort）由东尼·霍尔提出。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
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)
归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
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)
堆排序（Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
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
插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
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
希尔排序（Shell Sort）是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。
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
计数排序（Counting Sort）的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。要求输入的数据必须是整数，且范围不能太大。
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
桶排序（Bucket Sort）是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要选择合适的桶的数量和分布范围。
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
基数排序（Radix Sort）属于分配式排序，又称桶子法（Bucket Sort）或 Bin Sort。它是透过键值的部份信息，将要排序的元素分配至某些桶中，以达到排序的作用。基数排序法有两种：最高位优先（MSD）法和最低位优先（LSD）法。
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) | 稳定 |
在实际开发中，选择排序算法需考虑以下因素：
数据规模：
数据特征：
稳定性要求：
内存限制：
以上是用 Python 实现的十种经典排序算法。代码实现并非重点，理解算法思想、适用场景及性能差异更为关键。掌握这些基础算法有助于优化程序性能，解决复杂工程问题。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online