经典排序算法与毕业项目

第 17 章 · 经典排序算法与毕业项目

本章目标：理解排序时间/空间复杂度与稳定性；手写 冒泡、快速、归并、堆 排序；掌握 Java Collections.sort 与 Comparator；完成 toolkit-demo 毕业项目——日志分析 + CSV 运营日报；按 100 分验收表自评提交。

学时建议：6～8 小时（含算法练习 2 小时 + 项目 4 小时）

前置：完成 ch01～ch16（含进阶篇泛型、设计模式、并发进阶、JVM）；已配置 ~/learn-java/ 与 Maven 环境。

17.1 为什么要学排序

场景	排序的作用
商品列表	按价格、销量展示
排行榜	Top N 用户与商品
日志分析	按耗时找慢请求、按时间合并
数据库	`ORDER BY` 依赖索引或排序

未排序 → 查找成本高
排序后 → 二分、双指针、Top K 算法才好用

原则：工程里 99% 用内置排序；手写是为了理解复杂度与面试思维。

17.2 评价指标

指标	含义
时间复杂度	随 n 增长的操作次数（平均/最坏）
空间复杂度	额外内存
稳定性	相等元素排序后相对顺序是否不变

符号	直觉
O(n²)	双重循环朴素排序
O(n log n)	优秀通用排序下界
O(1)	原地、无额外数组

17.3 算法总览

算法	平均	最坏	空间	稳定	场景
冒泡	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)	❌	Top K、优先队列

工程选型：日常用 Collections.sort / List.sort（TimSort）；只要 Top K 用堆或 PriorityQueue。

17.4 冒泡排序

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

相邻比较，大的「冒泡」到末尾；已有序时可提前结束。

17.5 快速排序

public static void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[left + (right - left) / 2];
    int i = left, j = right;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    quickSort(arr, left, j);
    quickSort(arr, i, right);
}

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

分区思想：选 pivot，小于放左、大于放右，递归。最坏 O(n²)（已有序 + 固定 pivot）；工程用随机 pivot。

17.6 归并排序

public static void mergeSort(int[] arr) {
    if (arr.length <= 1) return;
    int mid = arr.length / 2;
    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);
    mergeSort(left);
    mergeSort(right);
    merge(arr, left, right);
}

private static void merge(int[] dest, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            dest[k++] = left[i++];
        } else {
            dest[k++] = right[j++];
        }
    }
    while (i < left.length) dest[k++] = left[i++];
    while (j < right.length) dest[k++] = right[j++];
}

分治 + 合并两个有序数组；稳定，适合外部大文件排序。

17.7 堆排序与 Top K

/** 原地堆排序：大顶堆 + 逐个交换到末尾，空间 O(1)，与 17.3 总览表一致 */
public static void heapSort(int[] arr) {
    int n = arr.length;
    // 建堆：从最后一个非叶子节点向上沉降
    for (int i = n / 2 - 1; i >= 0; i--) {
        siftDown(arr, i, n);
    }
    // 每次取堆顶（最大值）换到末尾，堆规模减一
    for (int end = n - 1; end > 0; end--) {
        swap(arr, 0, end);
        siftDown(arr, 0, end);
    }
}

private static void siftDown(int[] arr, int root, int size) {
    while (true) {
        int largest = root;
        int left = 2 * root + 1;
        int right = 2 * root + 2;
        if (left < size && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < size && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest == root) {
            return;
        }
        swap(arr, root, largest);
        root = largest;
    }
}

private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

注意：网上常见用 PriorityQueue 全部入堆再逐个 poll() 的「堆排序」写法，空间实为 O(n)，不是严格意义的原地堆排。PriorityQueue 更适合 Top K 场景：

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.List;

// Top K：销量前 3 商品（n 很大时优于全排序）
record Sale(String sku, int qty) {}

List<Sale> top3 = sales.stream()
    .sorted((a, b) -> Integer.compare(b.qty, a.qty))
    .limit(3)
    .toList();

// 或用大小为 K 的小顶堆维护 Top K：超出容量即淘汰堆顶，空间仅 O(K)
PriorityQueue<Sale> minHeap = new PriorityQueue<>(Comparator.comparingInt(Sale::qty));
for (Sale s : sales) {
    minHeap.offer(s);
    if (minHeap.size() > 3) {
        minHeap.poll();
    }
}

场景	做法
全量排序	`Arrays.sort` / `Collections.sort`
Top K	`PriorityQueue` 或 `limit` + 堆
第 K 大	大小为 K 的堆

17.8 Java 内置排序

List<String> titles = new ArrayList<>(List.of("笔记本", "钢笔", "书包"));
titles.sort(Comparator.naturalOrder());
titles.sort(Comparator.comparing(String::length).reversed());

int[] nums = {3, 1, 4, 1, 5};
Arrays.sort(nums);

// 多字段
products.sort(Comparator
    .comparingInt(Product::sales).reversed()
    .thenComparing(Product::price));

List.sort 默认 TimSort（归并 + 插入混合），稳定，对局部有序数据极快。

17.9 毕业项目背景

toolkit-demo 是虚构工具套件运营场景。运营同学每日需要：

分析 Web 访问日志，找出慢请求与错误状态码；
汇总 订单 CSV，计算销售额与 Top 商品；
输出 控制台摘要 + report.txt + summary.csv。

不连接真实生产系统，数据均为本地样本；数据库练习可对接虚构 db.example.com 教学库（选修）。

对标 python-dev ch16～ch17 的 shop-demo 日报，Java 版强调 Maven 结构与 JUnit 测试。

工程说明：可在 ch01 的 toolkit-demo 工程上继续扩展（新增 demo.report 包），或新建 toolkit-demo-graduation 目录；二者 groupId 均建议 com.example.learn。日志格式采用 ch07 管道分隔 基础版（时间|路径|状态码），与 ch09 详版（含 ms=）兼容——LogParser 应能解析两种格式或统一为一种。