1. 快速排序（Quick Sort）
原理：
- 选择一个基准值（pivot）
- 将数组分成两部分：小于 pivot 的放左边，大于 pivot 的放右边。然后递归处理
工作过程示例：
示例数组：[5, 3, 8, 4, 2]
- 选择 pivot = 8
左：[5, 3, 4, 2]，中：[8]，右：[] - 递归左部分 pivot = 4
左：[3, 2]，中：[4]，右：[5] - 递归 [3, 2] pivot = 2
左：[]，中：[2]，右：[3] - 合并结果：
[] + [2] + [3]→[2, 3] - 逐步合并：
[2, 3] + [4] + [5]→[2, 3, 4, 5]
[2, 3, 4, 5] + [8]→[2, 3, 4, 5, 8]
代码：
def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2] # 选中间值left = [x for x in arr if x < pivot] # 左边mid = [x for x in arr if x == pivot] # 中间right = [x for x in arr if x > pivot] # 右边return quick_sort(left) + mid + quick_sort(right)print(quick_sort([5, 3, 8, 4, 2]))
2. 堆排序（Heap Sort）
原理：
- 构建最大堆（堆顶是最大元素）
- 将堆顶与末尾交换，缩小堆的范围
- 重新堆化，直到数组有序
工作过程示例：
示例数组：[5, 3, 8, 4, 2]
- 建最大堆 →
[8, 4, 5, 3, 2]（堆顶是最大值 8） - 交换堆顶与末尾 →
[2, 4, 5, 3, 8]，缩小堆范围 - 堆化 →
[5, 4, 2, 3, 8] - 交换堆顶与末尾 →
[3, 4, 2, 5, 8] - 堆化 →
[4, 3, 2, 5, 8] - 交换堆顶与末尾 →
[2, 3, 4, 5, 8] - 完成排序：
[2, 3, 4, 5, 8]
代码：
def heapify(arr, n, i):largest = il, r = 2*i + 1, 2*i + 2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif 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 arrprint(heap_sort([5, 3, 8, 4, 2]))
3. 归并排序（Merge Sort）
原理：
- 递归将数组拆分成左右两半
- 分别排序后，合并两个有序数组
- 典型的分治算法，稳定
工作过程示例
示例数组：[5, 3, 8, 4, 2]
- 拆分：
[5, 3, 8]和[4, 2]
[5, 3]和[8]→[5][3][8]
[4][2] - 合并（按顺序）：
[5] + [3]→[3, 5]
[4] + [2]→[2, 4] - 合并
[3, 5]和[8]→[3, 5, 8] - 合并
[3, 5, 8]和[2, 4]→[2, 3, 4, 5, 8]
代码：
def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)def merge(left, right):res = []i = j = 0while i < len(left) and j < len(right):if left[i] <= right[j]:res.append(left[i])i += 1else:res.append(right[j])j += 1res.extend(left[i:])res.extend(right[j:])return resprint(merge_sort([5, 3, 8, 4, 2]))
4. 希尔排序（Shell Sort）
原理：
- 插入排序的改进版
- 先分成间隔为
gap的多个子序列，对每个子序列做插入排序 - 逐步缩小
gap，直到gap=1时完成排序
工作过程示例：
示例数组：[5, 3, 8, 4, 2]
- gap = 2（分组做插入排序）
组1:[5, 8, 2]→[2, 8, 5]
组2:[3, 4]→[3, 4]
排序结果：[2, 3, 8, 4, 5] - gap = 1（普通插入排序）
[2, 3, 4, 5, 8]→ 完成
代码：
def shell_sort(arr):n = len(arr)gap = n // 2while gap > 0:for i in range(gap, n):temp = arr[i]j = iwhile j >= gap and arr[j - gap] > temp:arr[j] = arr[j - gap]j -= gaparr[j] = tempgap //= 2return arrprint(shell_sort([5, 3, 8, 4, 2]))
5. 计数排序（Counting Sort）
原理：
- 适用于整数且范围不大的情况
- 统计每个值出现的次数
- 按次数依次回填到数组中
工作过程示例：
示例数组：[5, 3, 8, 4, 2]
- 找范围：min=2，max=8
- 计数数组（索引表示值-2）：
值：2 3 4 5 6 7 8
次数：[1,1,1,1,0,0,1] - 回填：
输出[2, 3, 4, 5, 8]
代码：
def counting_sort(arr):if not arr:return arrmin_val, max_val = min(arr), max(arr)count = [0] * (max_val - min_val + 1)for num in arr:count[num - min_val] += 1res = []for i, c in enumerate(count):res.extend([i + min_val] * c)return resprint(counting_sort([5, 3, 8, 4, 2]))
