排序

第 12 章 · 数据结构与算法

一、排序概述与稳定性

比较排序：只通过「比较两个元素大小」得到顺序，不利用数值范围。可以证明：比较排序在最坏情况下至少需要 Ω(n log n) 次比较。稳定性：若排序前有相等元素 a 与 b 且 a 在 b 前，排序后 a 仍在 b 前，则称该排序算法稳定。稳定排序在多关键字排序时有用（先按次关键字排，再按主关键字排，主关键字相同时会保持次关键字的顺序）。

二、简单排序（O(n²)）简述

冒泡：相邻两两比较，逆序则交换，每轮把最大「冒」到末尾，O(n²)，稳定。选择：每轮选未排序部分的最小元放到已排序末尾，O(n²)，不稳定。插入：将未排序部分的首元素插入到已排序部分的正确位置，O(n²)，稳定；对近似有序的序列很快。三者都是原地排序，适合 n 很小时或教学。

三、归并排序

归并排序（merge sort）：分治。把数组分成两半，分别递归排序，再把两个有序数组合并成一个。合并时用双指针，每次取两段中较小的放入结果，O(n)。总时间 T(n)=2T(n/2)+O(n)，即 O(n log n)；需要额外 O(n) 空间存临时数组。归并排序是稳定的（合并时相等时取前一段的即可）。

from typing import List


def merge_sort(arr: List[int]) -> None:
    """
    归并排序：原地排序 arr。辅助数组用于合并，合并时取等取左以保证稳定。
    """
    n = len(arr)
    tmp: List[int] = [0] * n

    def merge(l: int, mid: int, r: int) -> None:
        i, j, k = l, mid, l
        while i < mid and j < r:
            if arr[i] <= arr[j]:  # 相等取左，稳定
                tmp[k] = arr[i]
                i += 1
            else:
                tmp[k] = arr[j]
                j += 1
            k += 1
        while i < mid:
            tmp[k] = arr[i]
            i += 1
            k += 1
        while j < r:
            tmp[k] = arr[j]
            j += 1
            k += 1
        arr[l:r] = tmp[l:r]

    def sort(l: int, r: int) -> None:
        if r - l <= 1:
            return
        mid = (l + r) // 2
        sort(l, mid)
        sort(mid, r)
        merge(l, mid, r)

    sort(0, n)

四、快速排序

快速排序（quick sort）：选一个基准（如首元、尾元或随机），将数组划分成「小于基准」「等于基准」「大于基准」三段（或两段），递归排序左右。划分可双指针：左指针找大于基准的、右指针找小于基准的，交换后继续，直到相遇。平均时间 O(n log n)，最坏 O(n²)（如已有序且总选到最值作基准）；可随机选基准或三数取中降低最坏概率。快排一般不稳定；可写成稳定版但需额外空间。原地实现空间 O(log n) 递归栈。

from typing import List
import random


def quick_sort(arr: List[int]) -> None:
    """
    快速排序：选最后一个为基准，双指针划分 [l, i) ≤ pivot，[i, j) 未处理，[j, r] ≥ pivot。
    然后交换 pivot 到位置 i，递归 [l, i) 和 [i+1, r]。
    """

    def partition(l: int, r: int) -> int:
        # 随机选一个与 arr[r-1] 交换，避免有序时退化
        rand = random.randint(l, r - 1)
        arr[rand], arr[r - 1] = arr[r - 1], arr[rand]
        pivot = arr[r - 1]
        i = l
        for j in range(l, r - 1):
            if arr[j] <= pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
        arr[i], arr[r - 1] = arr[r - 1], arr[i]
        return i

    def sort(l: int, r: int) -> None:
        if r - l <= 1:
            return
        q = partition(l, r)
        sort(l, q)
        sort(q + 1, r)

    sort(0, len(arr))

五、堆排序

堆排序（heap sort）：先建大根堆（上一章已讲），然后每次把堆顶（当前最大）与末尾交换，堆大小减一，对根做下沉，重复直到堆为空。这样从后往前得到升序。时间 O(n log n)，原地，不稳定。Python 中可用 heapq 建小根堆再依次弹出得到升序，但那样需要额外空间。

from typing import List


def heap_sort(arr: List[int]) -> None:
    """
    堆排序：先建大根堆，再不断将堆顶与末尾交换并下沉，得到升序。
    """
    n = len(arr)

    def sift_down(start: int, end: int) -> None:
        """大根堆下沉：从 start 到 end 的子树中，start 不满足则与较大子交换。"""
        i = start
        while 2 * i + 1 < end:
            left = 2 * i + 1
            right = left + 1
            largest = i
            if arr[left] > arr[largest]:
                largest = left
            if right < end and arr[right] > arr[largest]:
                largest = right
            if largest == i:
                break
            arr[i], arr[largest] = arr[largest], arr[i]
            i = largest

    # 建堆：从最后一个非叶开始下沉
    for i in range((n - 2) // 2, -1, -1):
        sift_down(i, n)
    # 每次堆顶与末尾交换，堆范围减 1，再下沉
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(0, end)

六、算法对比

七、小结

比较排序下界 Ω(n log n)。归并分治合并、稳定、O(n) 空间；快排划分、平均 O(n log n)、不稳定；堆排原地、最坏 O(n log n)、不稳定。下一章讲查找与二分。

八、例题

以下例题使用 Python 3 类型标注与注释。

from typing import Optional


class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None) -> None:
        self.val = val
        self.next = next


def sort_list(head: Optional[ListNode]) -> Optional[ListNode]:
    """归并排序链表：找中点（快慢指针）、断链、递归、合并。"""

    def mid_and_split(h: Optional[ListNode]) -> tuple:
        if not h or not h.next:
            return h, None
        slow, fast = h, h.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None
        return h, mid

    def merge(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        p = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                p.next = l1
                l1 = l1.next
            else:
                p.next = l2
                l2 = l2.next
            p = p.next
        p.next = l1 or l2
        return dummy.next

    if not head or not head.next:
        return head
    left, right = mid_and_split(head)
    left = sort_list(left)
    right = sort_list(right)
    return merge(left, right)

from typing import List


def sort_colors(nums: List[int]) -> None:
    """
    三路划分：i 左侧全 0，k 右侧全 2，j 为当前指针；遇到 0 与 i 交换并 i,j 右移，遇到 2 与 k 交换并 k 左移，遇到 1 仅 j 右移。
    """
    i, j, k = 0, 0, len(nums) - 1
    while j <= k:
        if nums[j] == 0:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j += 1
        elif nums[j] == 2:
            nums[j], nums[k] = nums[k], nums[j]
            k -= 1
        else:
            j += 1

from typing import List


def merge_intervals(intervals: List[List[int]]) -> List[List[int]]:
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    result: List[List[int]] = [intervals[0][:]]
    for i in range(1, len(intervals)):
        start, end = intervals[i][0], intervals[i][1]
        last = result[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            result.append([start, end])
    return result

from typing import List
from functools import cmp_to_key


def largest_number(nums: List[int]) -> str:
    """比较规则：a 在前当且仅当 str(a)+str(b) >= str(b)+str(a)。"""
    strs = [str(x) for x in nums]

    def cmp(a: str, b: str) -> int:
        if a + b > b + a:
            return -1
        if a + b < b + a:
            return 1
        return 0

    strs.sort(key=cmp_to_key(cmp))
    result = "".join(strs)
    return "0" if result[0] == "0" else result