排序

（正文内容从这里开始…）

快速排序

import random

def partition(nums, start, end):
    """填坑法分区：返回枢轴落点索引"""
    pivot = nums[start]          # 也可随机：p = random.randint(start, end); nums[start], nums[p] = nums[p], nums[start]
    left, right = start, end
    while left < right:
        # 右侧先找 < pivot 的
        while left < right and nums[right] >= pivot:
            right -= 1
        nums[left] = nums[right]     # 右边的小填到左坑

        # 左侧再找 > pivot 的
        while left < right and nums[left] <= pivot:
            left += 1
        nums[right] = nums[left]     # 左边的大填到右坑

    nums[left] = pivot               # 枢轴就位
    return left

def quicksort(nums, l=0, r=None):
    """原地快速排序（递归）"""
    if r is None:
        r = len(nums) - 1
    if l >= r:
        return
    mid = partition(nums, l, r)
    quicksort(nums, l, mid - 1)
    quicksort(nums, mid + 1, r)

def quicksort(nums, start, end):
    """原地快速排序（递归）"""
    if start >= end:
        return

    pivot = nums[start]
    left, right = start, end

    # 分区：右找小填左坑，左找大填右坑
    while left < right:
        while left < right and nums[right] >= pivot:
            right -= 1
        if left < right:
            nums[left] = nums[right]
        while left < right and nums[left] <= pivot:
            left += 1
        if left < right:
            nums[right] = nums[left]

    nums[left] = pivot  # 枢轴就位
    quicksort(nums, start, left - 1)
    quicksort(nums, left + 1, end)

这个方法会在leetcode217.存在重复元素超时
改进快排

import random
from typing import List

def quicksort(a: List[int], l: int, r: int) -> None:
    """改进版原地快速排序（三路划分 + 随机枢轴 + 尾递归优化）"""
    while l < r:
        # 1) 随机选择枢轴，交换到开头
        p = random.randint(l, r)
        a[l], a[p] = a[p], a[l]
        pivot = a[l]

        # 2) 三路划分：[l..lt-1] < pivot, [lt..gt] == pivot, [gt+1..r] > pivot
        lt, i, gt = l, l + 1, r
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1

        # 3) 递归较小的一侧，循环处理较大的一侧（尾递归优化）
        left_len = lt - 1 - l
        right_len = r - (gt + 1)
        if left_len < right_len:
            if l < lt - 1:
                quicksort(a, l, lt - 1)
            l = gt + 1
        else:
            if gt + 1 < r:
                quicksort(a, gt + 1, r)
            r = lt - 1

```  
# 冒泡排序

def bubble_sort(nums):
“””原地冒泡排序；稳定。平均/最坏 O(n^2)，最好（近乎有序）可提前终止。”””
n = len(nums)
for i in range(n - 1):
swapped = False
# 相邻比较与交换，内层区间逐步缩短
for j in range(0, n - 1 - i):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
swapped = True
if not swapped: # 本轮无交换 -> 已有序
break
return nums

def selection_sort(nums):
“””原地选择排序；不稳定。时间复杂度始终 O(n^2)。”””
n = len(nums)
for i in range(n - 1):
min_idx = i
# 在 [i+1, n) 中找最小元素的位置
for j in range(i + 1, n):
if nums[j] < nums[min_idx]:
min_idx = j
# 只在需要时交换，减少无谓交换次数
if min_idx != i:
nums[i], nums[min_idx] = nums[min_idx], nums[i]
return nums

# 归并排序

def merge_sort(nums):
if len(nums) <= 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)

def merge(left, right):
l, r = 0, 0
res = []
while l < len(left) and r < len(right):
if left[l] <= right[r]:
res.append(left[l])
l += 1
else:
res.append(right[r])
r += 1
res.extend(left[l:])
res.extend(right[r:])
return res