常见排序算法详解
排序是将无序数据转换为有序序列的过程，Python 中可以通过内置的 sort() 方法完成。排序广泛应用于排行榜、表格整理、二分查找前置处理以及其他算法的基础环节。
常见的排序算法可分为三类：
- 初级排序：冒泡排序、选择排序、插入排序
- 高效排序：快速排序、堆排序、归并排序
- 其他排序：希尔排序、计数排序、桶排序
排序过程中通常涉及两个区域：已排序区和未排序区。初始状态下整个列表为未排序区，逐步从中提取元素进行排列，并将其放入已排序区。
性能分析工具
为了衡量不同排序算法的执行效率，我们定义一个装饰器用于统计运行时间：
# timewrap.py
import time
def cal_time(func):
def wrapper(*args, **kwargs):
start = time.time()
result = func(*args, **kwargs)
end = time.time()
print(f"{func.__name__} 执行耗时: {end - start:.6f} 秒")
return result
return wrapper
初级排序算法
冒泡排序
冒泡排序通过重复遍历待排序列表，比较相邻项并在必要时交换它们的位置，从而让较大的值像气泡一样"浮"到末尾。
特点：
- 时间复杂度：
O(n²) - 空间复杂度：
O(1) - 稳定排序
@cal_time
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(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
选择排序
每次从未排序部分选取最小值并将其置于当前位置。
特点：
- 时间复杂度：
O(n²) - 空间复杂度：
O(1) - 不稳定排序
@cal_time
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
插入排序
模拟打扑克时摸牌的过程，每次从无序区取出一张牌插入到有序区合适的位置。
特点：
- 时间复杂度：
O(n²) - 空间复杂度：
O(1) - 稳定排序
@cal_time
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
高级排序算法
快速排序
采用分治策略，选定基准元素将数组划分为两部分，分别递归排序。
特点：
- 平均时间复杂度：
O(n log n) - 最坏情况：
O(n²) - 空间复杂度：
O(log n) - 不稳定排序
import sys
sys.setrecursionlimit(100000)
def partition(arr, low, high):
pivot = arr[low]
while low < high:
while low < high and arr[high] >= pivot:
high -= 1
arr[low] = arr[high]
while low < high and arr[low] <= pivot:
low += 1
arr[high] = arr[low]
arr[low] = pivot
return low
def _quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
_quick_sort(arr, low, pi - 1)
_quick_sort(arr, pi + 1, high)
@cal_time
def quick_sort(arr):
_quick_sort(arr, 0, len(arr) - 1)
堆排序
构建最大堆（或最小堆），反复取出堆顶元素以获得有序序列。
特点：
- 时间复杂度：
O(n log n) - 空间复杂度：
O(1) - 不稳定排序
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)
@cal_time
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)
归并排序
将数组不断拆分至单个元素，再逐层合并两个有序子数组。
特点：
- 时间复杂度：
O(n log n) - 空间复杂度：
O(n) - 稳定排序
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
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)
@cal_time
def merge_sort(arr):
sorted_arr = _merge_sort(arr)
arr[:] = sorted_arr
其他排序方法
希尔排序
作为插入排序的改进版，通过设定间隔逐步减少的方式提升效率。
特点：
- 时间复杂度：取决于步长序列
- 空间复杂度：
O(1) - 不稳定排序
def shell_sort(arr):
gap = len(arr) // 2
while gap > 0:
for i in range(gap, len(arr)):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
计数排序
适用于整数范围较小的情况，通过统计每个数值出现次数来排序。
特点：
- 时间复杂度：
O(n + k)（k 为数值范围） - 空间复杂度：
O(k) - 稳定排序
@cal_time
def counting_sort(arr, max_val=100):
count = [0] * (max_val + 1)
for num in arr:
count[num] += 1
index = 0
for value, freq in enumerate(count):
for _ in range(freq):
arr[index] = value
index += 1
以上介绍了多种常用排序算法及其特性。实际应用中应根据具体需求如数据规模、是否允许额外空间、稳定性要求等因素综合考虑选用合适的算法。
