快速排序：分治思想和供应链订单优先级排序

快速排序是一种典型的分治算法。它选择一个基准值，把数组拆分成“小于基准”和“大于基准”的两部分，再递归处理左右区间。平均时间复杂度是 O(n log n)，在理解排序算法、递归和分治思想时非常重要。

整体流程

快速排序流程

基础思想

快速排序包含三步：

  1. 选择基准值 pivot。
  2. 分区：把小于 pivot 的元素放左边，大于 pivot 的元素放右边。
  3. 递归排序左右区间。

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public void quickSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;
    }

    int pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
}

private int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int storeIndex = left;

    for (int i = left; i < right; i++) {
        if (arr[i] <= pivot) {
            swap(arr, storeIndex, i);
            storeIndex++;
        }
    }
    swap(arr, storeIndex, right);
    return storeIndex;
}

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

这段代码使用最后一个元素作为 pivot，便于理解，但生产实现通常会使用更稳健的 pivot 选择策略。

Pivot 选择和递归边界

快速排序的性能很依赖 pivot。如果每次 pivot 都把数组切得很不均匀，递归深度会接近 n，最坏时间复杂度会退化到 O(n^2)。例如数据已经按订单创建时间升序排列，而实现又总是选择最后一个元素作为 pivot，就容易出现这种问题。

一个常见优化是随机选择 pivot：

1
2
3
4
5
private int randomizedPartition(int[] arr, int left, int right) {
    int pivotIndex = ThreadLocalRandom.current().nextInt(left, right + 1);
    swap(arr, pivotIndex, right);
    return partition(arr, left, right);
}

还有一种做法是“三数取中”，从左端、中间、右端选一个更接近中位数的值作为 pivot。它不能完全避免最坏情况，但能降低有序数据导致退化的概率。

递归边界也要写清楚：当 left >= right 时直接返回。否则空区间、单元素区间会继续递归，轻则浪费调用栈，重则造成栈溢出。

供应链业务例子

假设订单履约系统需要把待处理订单按综合优先级排序：

1
2
3
4
客户等级
订单时效
是否缺货风险
创建时间

如果订单量很大，排序应该优先下推到数据库或搜索引擎，让索引和分页机制发挥作用：

1
2
3
4
5
SELECT *
FROM scm_order
WHERE status = 'WAIT_FULFILL'
ORDER BY customer_level DESC, promise_time ASC, created_at ASC
LIMIT 100;

如果是在内存中对少量候选订单做二次排序，可以使用 Java 内置排序：

1
2
3
4
orders.sort(Comparator
        .comparing(OrderCandidate::getCustomerLevel).reversed()
        .thenComparing(OrderCandidate::getPromiseTime)
        .thenComparing(OrderCandidate::getCreatedAt));

学习快速排序的意义，不是让业务代码手写排序，而是理解“分而治之”的思路。比如订单分仓、波次拆分、库存重算，都可以把大任务拆成多个小区间并行处理。

分治思想在履约任务里的应用

分治思想在供应链系统中很常见。假设一天有几十万张待履约订单，如果直接由一个任务串行处理，会遇到处理时间长、失败重试成本高、单点压力大的问题。更合理的做法是先拆分：

1
按仓库拆分 -> 按承诺发货日期拆分 -> 按波次拆分 -> 每个分片独立处理

拆分以后，每个任务只处理一个相对小的订单集合。失败时可以只重试某个仓库、某个波次，而不是重跑整批数据。

在 Java 里可以用线程池并行处理这些分片：

1
2
3
for (OrderShard shard : shards) {
    executor.submit(() -> fulfillmentService.process(shard));
}

这里和快速排序类似：先把大问题切小，再分别处理，最后合并结果。区别是排序算法合并的是有序区间，业务系统合并的是处理状态、异常结果和监控指标。

复杂度和风险

快速排序特点：

  1. 平均时间复杂度：O(n log n)。
  2. 最坏时间复杂度：O(n^2)，通常发生在 pivot 选择很差且数据分区极不均衡时。
  3. 空间复杂度：平均 O(log n)，来自递归调用栈。
  4. 稳定性：通常不稳定。

为了降低最坏情况风险，可以使用随机 pivot、三数取中，或者在小区间切换为插入排序。JDK 内部排序实现已经处理了很多细节，业务代码一般不要重复造轮子。

小结

快速排序的核心价值是分治。供应链系统中，排序只是表象，更重要的是理解如何拆分大任务、减少无效扫描、控制单次处理的数据量。真正落地时，要优先使用数据库排序、索引、分页和 JDK 排序工具。