排序 解题模板

适用场景

数组排序、归并思想、快速选择

通用模板

快排

 
def quicksort(arr, l, r):
 
    if l >= r: return
 
    pivot = partition(arr, l, r)
 
    quicksort(arr, l, pivot-1)
 
    quicksort(arr, pivot+1, r)
 
def partition(arr, l, r):
 
    pivot = arr[r]
 
    i = l
 
    for j in range(l, r):
 
        if arr[j] <= pivot:
 
            arr[i], arr[j] = arr[j], arr[i]
 
            i += 1
 
    arr[i], arr[r] = arr[r], arr[i]
 
    return i
 

归并

 
def mergesort(arr):
 
    if len(arr) <= 1: return arr
 
    mid = len(arr)//2
 
    left = mergesort(arr[:mid])
 
    right = mergesort(arr[mid:])
 
    return merge(left, right)
 
def merge(l, r):
 
    res = []
 
    i = j = 0
 
    while i < len(l) and j < len(r):
 
        if l[i] <= r[j]: res.append(l[i]); i+=1
 
        else: res.append(r[j]); j+=1
 
    return res + l[i:] + r[j:]
 

快速选择（第 K 大）

 
# partition 后:
 
if pivot == k: return nums[pivot]
 
if pivot < k: l = pivot + 1
 
else: r = pivot - 1
 

复杂度总结

算法	时间	空间	稳定
快排	O(n log n) 平均	O(log n)	不稳
归并	O(n log n)	O(n)	稳定
堆排	O(n log n)	O(1)	不稳
插入	O(n²)	O(1)	稳定

关键要点

• 快排 partition 边界处理

• 归并适合链表排序（148 题）

• 快速选择 = 快排的 partition 只走一边

→ 查看该分类题目：LeetCode学习路线图 > 七、排序

---

关联题型

关联题型	常见结合方式	典型题目
数组与哈希	数组排序 + 双指针	15三数之和
二分查找	排序数组 + 二分	34搜索范围
堆	堆排序	215第K大元素