445_排序算法面试题¶

一句话说明¶

排序算法是面试必考基础，快排平均 O(n log n)、归并稳定 O(n log n)、堆排原地 O(n log n)，手写快排和归并是基本功，同时要能分析各算法的适用场景。

核心知识点¶

白话理解¶

排序就像整理书架。快排：随机找一本书作基准，比它小的放左边大的放右边，再分别整理两边（分治）。归并：把书架分成两半分别排好，再把两个有序的合成一个（分而合之）。

常见算法对比¶

算法	平均时间	最坏时间	空间	稳定性
冒泡	O(n²)	O(n²)	O(1)	稳定
选择	O(n²)	O(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(n)	稳定
堆排	O(n log n)	O(n log n)	O(1)	不稳定

经典题目与解法¶

题目1：手写快速排序¶

题意：实现快速排序，平均时间复杂度 O(n log n)。

def quick_sort(nums, left, right):
    """
    快速排序：选基准值，分区，递归
    """
    if left >= right:                      # 区间只有1个或0个元素，不用排
        return

    pivot_idx = partition(nums, left, right)  # 分区：基准归位
    quick_sort(nums, left, pivot_idx - 1)    # 递归处理左半部分
    quick_sort(nums, pivot_idx + 1, right)   # 递归处理右半部分

def partition(nums, left, right):
    """
    双指针分区（Lomuto 分区法）
    选最右边的元素作为基准值
    """
    pivot = nums[right]                    # 选最右边作基准
    i = left - 1                           # i 是小于基准区域的右边界

    for j in range(left, right):           # j 遍历 [left, right-1]
        if nums[j] <= pivot:               # 当前元素小于等于基准
            i += 1                         # 小于区扩张
            nums[i], nums[j] = nums[j], nums[i]  # 换到小于区

    nums[i + 1], nums[right] = nums[right], nums[i + 1]  # 基准归位
    return i + 1                           # 返回基准的最终位置

# 三路快排（处理大量重复元素更高效）
def quick_sort_3way(nums, left, right):
    """
    三路分区：< pivot | == pivot | > pivot
    处理重复元素从 O(n²) 优化到 O(n)
    """
    if left >= right:
        return

    pivot = nums[left]
    lt = left                              # lt: 小于区的右边界
    gt = right                             # gt: 大于区的左边界
    i = left + 1                           # i: 当前处理的元素

    while i <= gt:
        if nums[i] < pivot:
            nums[lt], nums[i] = nums[i], nums[lt]
            lt += 1
            i += 1
        elif nums[i] > pivot:
            nums[gt], nums[i] = nums[i], nums[gt]
            gt -= 1                        # i不动，新换来的元素还没处理
        else:                              # 等于pivot
            i += 1

    quick_sort_3way(nums, left, lt - 1)   # 递归 < pivot 部分
    quick_sort_3way(nums, gt + 1, right)  # 递归 > pivot 部分

# 测试
nums = [3, 6, 8, 10, 1, 2, 1]
quick_sort(nums, 0, len(nums) - 1)
print(nums)  # [1, 1, 2, 3, 6, 8, 10]

时间复杂度：平均 O(n log n)，最坏 O(n²)（已排序数组）
空间复杂度：O(log n) 递归栈

题目2：手写归并排序¶

题意：实现归并排序，保证时间复杂度 O(n log n)。

def merge_sort(nums):
    """
    归并排序：分治 + 合并
    """
    if len(nums) <= 1:                     # 只有0或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):
    """合并两个有序数组"""
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:            # 取小的放入结果
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])                # 接上左边剩余
    result.extend(right[j:])               # 接上右边剩余

    return result

# 原地归并（不额外创建数组，面试进阶）
def merge_sort_inplace(nums, left, right):
    if left >= right:
        return

    mid = (left + right) // 2
    merge_sort_inplace(nums, left, mid)
    merge_sort_inplace(nums, mid + 1, right)
    merge_inplace(nums, left, mid, right)

def merge_inplace(nums, left, mid, right):
    temp = nums[left:right + 1]            # 临时数组
    i, j = 0, mid - left + 1              # 两个子数组的指针

    for k in range(left, right + 1):
        if i > mid - left:                 # 左半用完
            nums[k] = temp[j]; j += 1
        elif j > right - left:             # 右半用完
            nums[k] = temp[i]; i += 1
        elif temp[i] <= temp[j]:
            nums[k] = temp[i]; i += 1
        else:
            nums[k] = temp[j]; j += 1

# 测试
nums = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(nums))  # [3, 9, 10, 27, 38, 43, 82]

时间复杂度：O(n log n) 任何情况
空间复杂度：O(n) 需要额外数组

题目3：数组中第 K 个最大元素（LeetCode 215，快速选择）¶

import random

def find_kth_largest(nums, k):
    """
    快速选择：快排的变体，每次只递归一侧
    平均 O(n)，比完整排序快
    """
    target = len(nums) - k                 # 第k大 = 从小到大第(n-k)个

    def quick_select(left, right):
        if left == right:
            return nums[left]

        pivot_idx = random.randint(left, right)  # 随机基准，避免最坏情况
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]

        pivot = nums[right]
        i = left - 1

        for j in range(left, right):
            if nums[j] <= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]

        pivot_pos = i + 1
        nums[pivot_pos], nums[right] = nums[right], nums[pivot_pos]

        if pivot_pos == target:            # 基准刚好是第k大
            return nums[pivot_pos]
        elif pivot_pos < target:
            return quick_select(pivot_pos + 1, right)  # 去右边找
        else:
            return quick_select(left, pivot_pos - 1)   # 去左边找

    return quick_select(0, len(nums) - 1)

print(find_kth_largest([3,2,1,5,6,4], 2))  # 5

面试技巧¶

快排最坏情况：已排序或逆序数组，基准每次选到最大/最小值，退化到 O(n²)，用随机化避免
归并是稳定的：相同元素相对顺序不变，归并排序适合外部排序（数据在磁盘）
K 大元素想到快速选择：比完整排序快，平均 O(n)
Python 实际用 Timsort：sorted() 和 .sort() 是 Timsort（归并+插入），最坏 O(n log n)
说出稳定性的应用：多关键字排序时，先按次关键字稳定排序，再按主关键字稳定排序

速查表¶

# Python 内置排序（面试直接用，除非题目要求手写）
nums.sort()                    # 原地排序
sorted(nums)                   # 返回新列表
sorted(nums, key=lambda x: -x) # 降序
sorted(pairs, key=lambda x: (x[0], -x[1]))  # 多关键字

# 快排模板（背熟）
def partition(nums, l, r):
    pivot = nums[r]
    i = l - 1
    for j in range(l, r):
        if nums[j] <= pivot:
            i += 1
            nums[i], nums[j] = nums[j], nums[i]
    nums[i+1], nums[r] = nums[r], nums[i+1]
    return i + 1