冒泡排序、快速排序和堆排序是Python编程中非常经典的排序算法，三种算法有着不同的实现逻辑和性能表现，适用于不同的业务场景。理解它们的原理和差异，能够帮助开发者在排序需求出现时做出更合适的选择。
冒泡排序
冒泡排序是一种基础的交换排序算法，核心逻辑是重复遍历待排序序列，每次比较相邻的两个元素，如果顺序不符合要求就交换它们的位置，直到整个序列有序。每一轮遍历都会把当前未排序部分的最大元素“浮”到序列末尾，因此得名冒泡排序。
实现原理
算法执行过程分为多轮，每一轮从序列第一个元素开始，依次比较相邻两个元素，若前一个元素大于后一个元素则交换位置，一轮结束后最大的元素会到达当前未排序部分的最后一位。重复这个过程，直到所有元素都有序。
Python代码实现
def bubble_sort(arr):
# 获取数组长度
n = len(arr)
# 外层循环控制遍历轮数
for i in range(n):
# 设置标志位，判断本轮是否有交换，没有则说明已经有序可以提前结束
swapped = False
# 内层循环比较相邻元素，每轮后最后i个元素已经有序，不需要再比较
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
# 测试示例
test_arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(test_arr))
性能分析
- 时间复杂度：最好情况为O(n)（数组已经有序时），最坏和平均情况为O(n²)
- 空间复杂度：O(1)，属于原地排序算法
- 稳定性：稳定，相等元素不会交换相对位置
快速排序
快速排序是一种分治思想的排序算法，平均性能非常优秀，是实际应用中使用较多的排序算法之一。它的核心逻辑是选择一个基准元素，将序列分为两部分，一部分所有元素小于基准，另一部分所有元素大于基准，然后递归对两部分继续排序，直到整个序列有序。
实现原理
首先选择一个基准元素，通常可以选择序列第一个、最后一个或者中间的元素。然后通过双指针遍历序列，将小于基准的元素放到基准左边，大于基准的元素放到基准右边，完成分区后基准元素就处于最终的正确位置。之后递归对左右两个子序列执行同样的操作，直到子序列长度为1或0，排序完成。
Python代码实现
def quick_sort(arr):
# 递归终止条件：数组长度小于等于1时已经有序
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)
# 测试示例
test_arr = [64, 34, 25, 12, 22, 11, 90]
print(quick_sort(test_arr))
性能分析
- 时间复杂度：平均情况为O(n log n)，最坏情况为O(n²)（每次选择的基准都是最大或最小元素），可以通过随机选择基准优化最坏情况
- 空间复杂度：O(log n)，主要是递归调用栈的空间开销
- 稳定性：不稳定，分区过程中相等元素的相对位置可能改变
堆排序
堆排序是利用堆这种数据结构的排序算法，堆是一个近似完全二叉树的结构，同时满足堆的性质：子节点的键值或索引总是小于（或大于）它的父节点。堆排序可以保证在最坏情况下也有不错的时间复杂度。
实现原理
首先将待排序序列构建成一个大顶堆（父节点大于子节点），此时堆顶元素是整个序列的最大值。然后将堆顶元素与堆的最后一个元素交换，此时最大值就放到了序列末尾，之后将剩余的前n-1个元素重新调整为大顶堆，重复这个过程，直到整个序列有序。
Python代码实现
def heapify(arr, n, i):
# 初始化最大元素为当前父节点
largest = i
# 左子节点索引
left = 2 * i + 1
# 右子节点索引
right = 2 * i + 2
# 如果左子节点存在且大于父节点，更新最大元素索引
if left < n and arr[left] > arr[largest]:
largest = left
# 如果右子节点存在且大于当前最大元素，更新最大元素索引
if right < n and arr[right] > arr[largest]:
largest = right
# 如果最大元素不是父节点，交换位置并递归调整受影响的子树
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[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
# 测试示例
test_arr = [64, 34, 25, 12, 22, 11, 90]
print(heap_sort(test_arr))
性能分析
- 时间复杂度：最好、最坏、平均情况都是O(n log n)，性能稳定
- 空间复杂度：O(1)，属于原地排序算法
- 稳定性：不稳定，堆调整过程中相等元素的相对位置可能改变
三种排序算法对比
为了更直观地看到三种算法的差异，我们可以从多个维度进行对比：
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
在实际开发中，如果数据量很小且需要稳定排序，可以选择冒泡排序；如果追求平均性能且数据量较大，快速排序是更合适的选择；如果需要保证最坏情况下的性能，同时希望空间开销小，堆排序会更适用。另外Python内置的sorted()函数和list.sort()方法使用的是TimSort算法，是结合了归并排序和插入排序的混合排序算法，性能比这三种基础算法更优，日常开发中优先使用内置排序方法即可。
冒泡排序快速排序堆排序Python排序算法修改时间：2026-07-12 07:21:29