数据结构与算法 / 系统课时

排序问题与评价指标

排序问题与评价指标

排序算法不只是“把数字从小到大排列”。本课建立一套评价框架,帮助你区分稳定、原地、在线与比较排序,并用可运行程序观察比较次数、移动次数和相同关键字元素的相对顺序。

学习目标

  • 准确定义排序问题中的记录、关键字与目标顺序。
  • 区分原地排序、稳定排序、在线排序和比较排序。
  • 使用时间、空间、稳定性与输入特征评价排序算法。

核心概念与评价指标

排序的输入通常是一组记录,每条记录包含用于比较的关键字以及需要随记录一起移动的其他数据。排序结果必须满足关键字有序,同时不能丢失、重复或篡改任何记录。

概念 判断标准 典型关注点
原地排序 只使用常数级额外存储空间 不等于完全不使用临时变量
稳定排序 关键字相等的记录保持原相对顺序 对多字段排序和业务记录很重要
在线排序 元素逐个到达时仍可维护已有元素的有序状态 适合流式输入或增量处理
比较排序 仅通过关键字之间的比较决定顺序 决策树模型下最坏情况需要 Ω(nlog⁡n)\Omega(n \log n) 次比较

这些属性彼此独立。一个算法可以稳定但不是原地,也可以原地但不稳定。稳定性只有在记录包含重复关键字时才有意义;若所有关键字都不同,仅看输出值无法判断算法是否稳定。

评价排序算法时,应至少检查以下维度:

  1. 正确性:输出是否有序,且与输入包含完全相同的记录。
  2. 时间复杂度:最好、平均和最坏情况是否符合使用场景。
  3. 空间复杂度:除输入本身外需要多少辅助空间。
  4. 稳定性:相等关键字记录的相对顺序是否保留。
  5. 适应性:输入已经接近有序时,算法能否减少工作量。

容易混淆的边界

原地排序通常指辅助空间为 O(1)O(1),不是“内存零开销”。递归算法即使不分配辅助数组,也可能因为调用栈使用 O(log⁡n)O(\log n) 空间。这里的在线指每来一个元素即可更新已见部分的有序状态。未来元素可能排在更前面,因此该属性不保证能提前输出不可更改的最终前缀。

实例验证

下面的 Java 17 程序把带标签的记录按 key 排序。排序核心改写原数组,校验环节另外保留输入副本。标签用于验证相同关键字元素是否保持原顺序;程序同时统计关键字比较次数和元素右移次数。这里把插入排序作为测量样本,具体实现与正确性证明将在下一课展开。

将代码保存为 SortingMetricsDemo.java。

java
import java.util.Arrays;
import java.util.Comparator;

public class SortingMetricsDemo {

    private record Item(int key, String tag) {
        @Override
        public String toString() {
            return "(" + key + "," + tag + ")";
        }
    }

    private record Metrics(long comparisons, long shifts) {
    }

    public static void main(String[] args) {
        Item[] items = {
            new Item(2, "A"),
            new Item(1, "B"),
            new Item(2, "C"),
            new Item(1, "D")
        };

        System.out.println("原始序列: " + format(items));
        Item[] original = items.clone();
        Metrics metrics = stableInsertionSort(items);

        System.out.println("排序结果: " + format(items));
        System.out.println("比较次数: " + metrics.comparisons());
        System.out.println("元素右移次数: " + metrics.shifts());
        System.out.println("稳定性检查: " + matchesStableOrder(original, items));
    }

    private static Metrics stableInsertionSort(Item[] items) {
        long comparisons = 0;
        long shifts = 0;

        for (int i = 1; i < items.length; i++) {
            Item current = items[i];
            int j = i - 1;

            // 只移动关键字严格更大的元素,保留相等元素的原顺序。
            while (j >= 0) {
                comparisons++;
                if (items[j].key() <= current.key()) {
                    break;
                }
                items[j + 1] = items[j];
                shifts++;
                j--;
            }
            items[j + 1] = current;
        }

        return new Metrics(comparisons, shifts);
    }

    private static boolean matchesStableOrder(Item[] before, Item[] after) {
        if (before.length != after.length) {
            return false;
        }
        Item[] expected = before.clone();
        Arrays.sort(expected, Comparator.comparingInt(Item::key));
        for (int i = 0; i < expected.length; i++) {
            if (expected[i] != after[i]) {
                return false;
            }
        }
        return true;
    }

    private static String format(Item[] items) {
        StringBuilder result = new StringBuilder("[");
        for (int i = 0; i < items.length; i++) {
            if (i > 0) {
                result.append(", ");
            }
            result.append(items[i]);
        }
        return result.append("]").toString();
    }
}

编译并运行:

bash
javac -encoding UTF-8 SortingMetricsDemo.java
java SortingMetricsDemo

预期输出

text
原始序列: [(2,A), (1,B), (2,C), (1,D)]
排序结果: [(1,B), (1,D), (2,A), (2,C)]
比较次数: 5
元素右移次数: 3
稳定性检查: true

比较次数只统计关键字比较,右移次数不包含每轮放回当前记录的写入。校验以 Java 对象数组的稳定排序为参考,并逐项比较记录身份,因此丢记录、替换记录或等键乱序都能发现。一次运行只能核对该输入。验证稳定性时,应准备至少两组具有相同关键字但标签不同的记录,并检查它们排序前后的相对位置。

本课总结

  • 排序结果不仅要有序,还必须保持输入记录的完整性。
  • 原地、稳定、在线和比较排序是相互独立的评价维度。
  • 复杂度需要结合输入规模与输入分布分析,单次运行数据只能用于观察行为。

下一课预告

下一课将学习“插入排序”,从有序前缀的扩展过程出发实现算法,并使用循环不变式证明它在终止时得到正确的排序结果。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

排序问题与评价指标

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通