🔄 排序 — 从比较到非比较的进化

📖 排序的核心概念

排序是算法的基础中的基础。面试中，你不需要手写快排，但需要理解各种排序的特点：哪些稳定、哪些原地、哪些 O(n log n)、哪些可以 O(n)。更重要的是，排序常作为其他算法的预处理步骤——排序 + 双指针、排序 + 二分、排序 + 贪心。

1. 排序在面试中的考点

2. Python 排序速查

# list.sort() — 原地排序
nums = [3, 1, 4, 1, 5]
nums.sort()               # [1, 1, 3, 4, 5]
nums.sort(reverse=True)   # [5, 4, 3, 1, 1]

# sorted() — 返回新列表
new_list = sorted(nums)

# 自定义 key
words = ["banana", "pie", "Washington"]
words.sort(key=len)       # 按长度: ["pie", "banana", "Washington"]
words.sort(key=lambda x: x.lower())  # 忽略大小写

# 多关键字排序
students = [("Alice", 90), ("Bob", 85), ("Charlie", 90)]
students.sort(key=lambda x: (-x[1], x[0]))  # 分数降序,名字升序

🎯 题目一：数组中的第K个最大元素 (LC 215)

题目描述：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

思路分析

代码实现

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 方法二: 小顶堆
        import heapq
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]

复杂度分析

时间复杂度：O(n log k)

空间复杂度：O(k)

变体练习

• LC 347 前 K 个高频元素（频率统计 + 堆）
• LC 378 有序矩阵中第 K 小的元素

🎯 题目二：前 K 个高频元素 (LC 347)

题目描述：给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。

思路分析

代码实现

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        from collections import Counter
        import heapq
        count = Counter(nums)
        return heapq.nlargest(k, count.keys(), key=count.get)

复杂度分析

时间复杂度：O(n log k) — nlargest 内部用堆

空间复杂度：O(n)

变体练习

• LC 692 前K个高频单词（频率+字典序）
• LC 451 根据字符出现频率排序

🎯 题目三：排序数组 (LC 912)

题目描述：给你一个整数数组 nums，请你将该数组升序排列。要求时间复杂度 O(n log n)。

思路分析

代码实现（归并排序）

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2
        left = self.sortArray(nums[:mid])
        right = self.sortArray(nums[mid:])
        return self._merge(left, right)
    
    def _merge(self, 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

复杂度分析

时间复杂度：O(n log n)

空间复杂度：O(n)

变体练习

• LC 912 用快速排序实现（练习手写快排）
• LC 148 排序链表（归并排序在链表上的应用）

📝 课后练习

1. LC 912 用快速排序实现（练习手写快排）
2. LC 56 合并区间（排序+贪心）
3. LC 75 颜色分类（荷兰国旗问题，三路快排）
4. LC 378 有序矩阵中第 K 小的元素
5. LC 451 根据字符出现频率排序

🔑 本课要点回顾

• 比较排序下界 Ω(n log n)，非比较排序可突破但有条件
• TopK 问题：排序 O(n log n) / 堆 O(n log k) / 快选 O(n)
• 前K高频：Counter统计 + 堆或桶排序
• 快速排序：选pivot + 分区 + 递归，随机化避免最坏
• 归并排序：分治 + 合并，稳定但需额外空间
• 排序常作为预处理：排序+双指针/贪心/二分

📚 扩展阅读

• 《算法导论》第6-8章（堆排序、快速排序、线性时间排序）
• 排序可视化：visualgo.net/en/sorting
• 排序专题：LeetCode 排序标签

🔬 排序的实战策略

面试中很少要求手写排序，但排序作为预处理步骤的场景非常多。这里总结排序在面试中的实战策略。

1. 排序 + 双指针

许多看似需要 O(n²) 的问题，排序后用双指针可以降到 O(n log n + n)。

# 排序 + 双指针的典型场景
# 两数之和（有序版）、三数之和、最接近的三数之和
# 关键: 排序后可以根据大小关系决定指针移动方向

def twoSumSorted(nums, target):
    nums.sort()  # O(n log n)
    left, right = 0, len(nums) - 1
    while left < right:  # O(n)
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1

2. 自定义排序 key

Python 的 sort 支持任意 key 函数，灵活运用可以简化很多问题。

# 按多个条件排序
# 例: 先按分数降序，同分按名字升序
students.sort(key=lambda x: (-x.score, x.name))

# 按自定义规则排序
# 例: 重新排列日志(字母日志在前，数字在后)
logs.sort(key=lambda x: (x.split()[1].isdigit(), 
                          x.split()[1:], x.split()[0]))