Chapter 28: Sorting Algorithms

排序算法把一个半开区间 [first, last) 中的元素重新排列，使后续查找、合并、分组、截断和展示可以依赖稳定的顺序前提。本章讨论的主问题是：给定一个需要按规则排列的数据区间，如何在 std::sort、std::stable_sort、std::partial_sort、std::nth_element、std::is_sorted 和 std::is_sorted_until 之间做出可验证的选择，并判断比较器是否让结果具有标准库算法可依赖的语义。

贯穿材料使用一个成绩记录区间。每条记录包含姓名、分数和录入序号。分数决定排名，录入序号用于观察等价分数之间的相对顺序。这个材料能同时暴露四个排序问题：全量排名、同分顺序保留、只取前 K 名、定位中位数或阈值元素。

排序算法的共同输入是迭代器区间和比较器。区间决定算法能读写哪些元素，迭代器能力决定算法可使用的访问方式，比较器决定“排在前面”的关系。对调用者而言，排序结果的可靠性来自三条线索：区间必须有效，元素必须能被算法移动、交换或赋值，比较器必须形成严格弱序。

读完本章后，读者应能按固定顺序检查排序需求：先确定目标是全排序、稳定全排序、局部有序还是选择第 N 个位置；再检查区间和迭代器能力；接着验证比较器的严格弱序；最后用复杂度、稳定性、额外内存和比较成本决定具体算法。

28.1 sort、stable_sort、partial_sort 与 nth_element

std::sort、std::stable_sort、std::partial_sort 和 std::nth_element 都会重排输入区间，但它们交付的结果强度不同。全排序交付完整顺序，稳定排序在完整顺序之上保留等价元素的原相对顺序，局部排序只保证前段有序，选择算法只保证第 N 个位置及其两侧分区关系。

先看贯穿材料。下面的记录中，seq 表示进入系统的原始顺序。比较器只看 score，分数高的记录排在前面。同分记录在这个比较器下是等价元素，因为 comp(a, b) 和 comp(b, a) 都返回 false。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

struct ScoreRecord {
    std::string name;
    int score;
    int seq;
};

bool higher_score(const ScoreRecord& left, const ScoreRecord& right) {
    return left.score > right.score;
}

void print_records(const std::vector<ScoreRecord>& records) {
    for (const auto& r : records) {
        std::cout << r.name << ':' << r.score << "#" << r.seq << ' ';
    }
    std::cout << '\n';
}

这个比较器没有处理同分时的姓名或序号。它表达的顺序目标是“分数高者在前”，同时把同分者放入同一个等价类。后续算法的差异集中出现在等价类、前 K 个位置和第 N 个位置上。

std::sort 交付完整非降序或按比较器定义的完整顺序。对 higher_score 来说，排序后任意后方元素都不会被比较器认为应排到前方元素之前。它适合需要遍历完整排名、对整个区间执行二分查找、再进入集合算法或合并算法的场景。

std::vector<ScoreRecord> records = {
    {"Ada", 90, 0}, {"Bjarne", 95, 1}, {"Chloe", 90, 2},
    {"Dennis", 80, 3}, {"Edsger", 95, 4}, {"Fay", 70, 5}
};

std::sort(records.begin(), records.end(), higher_score);
print_records(records);

这段代码能保证 95 分记录在 90 分记录之前，90 分记录在 80 分记录之前。它对 Bjarne 与 Edsger 的相对顺序没有保留承诺，对 Ada 与 Chloe 也没有保留承诺。这个边界来自 std::sort 的算法语义：排序结果满足比较关系，等价元素的原顺序可以改变。

std::stable_sort 交付完整顺序，并保留等价元素的原相对顺序。把同一批记录按 higher_score 稳定排序后，Bjarne 仍位于 Edsger 前方，因为它们同为 95 分且原 seq 为 1 和 4；Ada 仍位于 Chloe 前方，因为它们同为 90 分且原 seq 为 0 和 2。

std::stable_sort(records.begin(), records.end(), higher_score);

稳定性服务两类工程需求。第一类是多阶段排序，例如先按姓名排，再按分数稳定排序，从而得到“主键分数、次键姓名”的效果。第二类是保留业务时间线，例如同分者保持报名顺序、订单保持创建顺序、日志保持到达顺序。稳定性属于结果语义，不能用复杂度或实现习惯替代。

std::partial_sort 交付前段有序。调用形状是 partial_sort(first, middle, last, comp)，结果保证 [first, middle) 包含整个 [first, last) 中最靠前的 middle - first 个元素，并且这段本身已经按比较器排序。[middle, last) 的剩余元素顺序没有指定。

auto top3_end = records.begin() + 3;
std::partial_sort(records.begin(), top3_end, records.end(), higher_score);

for (auto it = records.begin(); it != top3_end; ++it) {
    std::cout << it->name << ':' << it->score << ' ';
}
std::cout << '\n';

这个调用适合排行榜首页、最小的 K 个延迟、最大的 K 个订单金额。它不为尾部建立完整顺序，因此后续代码只能把 [records.begin(), top3_end) 当作有序前缀使用。尾部如需继续二分查找或按顺序展示，应再排序尾部或选择全排序算法。

std::nth_element 交付第 N 个位置的选择结果。调用后，nth 指向的元素等于完整排序后该位置会出现的某个元素；[first, nth) 中的元素都不会被比较器认为应排在 *nth 后方；[nth, last) 中的元素都不会被比较器认为应排在 *nth 前方。两侧区间内部顺序没有排序承诺。

auto median = records.begin() + records.size() / 2;
std::nth_element(records.begin(), median, records.end(), higher_score);

std::cout << "threshold = " << median->score << '\n';

这个调用适合中位数、百分位阈值、只需判断 Top K 分界线的场景。若代码随后需要按顺序输出 Top K，nth_element 之后还需要对前段再调用 sort 或 partial_sort。它的优势来自结果强度更弱：算法只建立分区和第 N 个位置，不支付完整排序的比较成本。

四个算法的判断可以压缩成一组稳定问题。需要整个区间有序时选择 std::sort；需要整个区间有序且保留等价元素原相对顺序时选择 std::stable_sort；只需要前 K 个元素按顺序出现时选择 std::partial_sort；只需要第 K 个分界点或任意一侧分区时选择 std::nth_element。

这四个算法都要求随机访问迭代器。std::vector、std::array、原生数组和 std::deque 的迭代器满足这个要求；std::list 和 std::forward_list 的迭代器不满足这个要求。链表排序应使用容器自己的成员函数，例如 list.sort(comp)，因为节点式容器可以通过重连节点完成排序，同时保持链表迭代器语义。

下面的图把四个算法的结果强度放在同一条路径上。图只表达结果承诺，具体实现策略在后续小节讨论。

这条判断路径对应源码阅读时的入口选择。看到排序调用后，先看它消费的结果范围。如果后续代码遍历整个区间，它依赖全排序；如果只读取前 K 个元素，它依赖局部排序；如果只读取某个位置或阈值，它依赖选择结果。结果范围比函数名更能说明调用者真正需要的语义。

28.2 is_sorted 与 is_sorted_until

std::is_sorted 和 std::is_sorted_until 负责检测有序性。它们不重排元素，只扫描区间并回答“当前顺序是否满足比较器”。检测算法的价值在于把排序前提变成可观察证据，尤其适合调试二分查找、集合算法和增量数据管线。

std::is_sorted(first, last, comp) 返回布尔值。它适合在进入后续算法之前做前置检查。例如二分查找算法要求区间已经按同一比较器排序；集合算法也要求输入区间有序。把检测放在边界处，可以把“调用者承诺”转换成断言。

std::vector<ScoreRecord> records = {
    {"Bjarne", 95, 1}, {"Edsger", 95, 4}, {"Ada", 90, 0},
    {"Chloe", 90, 2}, {"Dennis", 80, 3}, {"Fay", 70, 5}
};

if (!std::is_sorted(records.begin(), records.end(), higher_score)) {
    std::cerr << "score records are not sorted by descending score\n";
}

这里的检查必须使用和排序阶段相同的比较器。若排序时使用 higher_score，检查时使用姓名比较器，检测结论与后续按分数二分或合并的前提无关。排序前提由“区间 + 比较器”共同定义，单独说一个区间“已经有序”会丢失核心条件。

std::is_sorted_until(first, last, comp) 返回第一个破坏有序性的迭代器。如果整个区间有序，它返回 last。这个返回值比布尔值更适合定位数据管线中的断点：前缀 [first, bad) 已经满足比较器，bad 是第一个使关系失败的位置。

auto bad = std::is_sorted_until(records.begin(), records.end(), higher_score);

if (bad != records.end()) {
    std::cout << "first broken record: " << bad->name
              << ", score=" << bad->score << '\n';
}

is_sorted_until 的断点含义来自相邻关系。对排序区间来说，若每一对相邻元素都没有出现“后者应排在前者之前”的情况，则整个区间有序。算法只需沿区间向前推进，比较当前元素和前一个元素。一旦发现 comp(*current, *previous) 为 true，current 就是第一个断点。

这个检测只要求前向迭代器。它能处理 forward_list 这样的单向范围，因为它只需要从左到右扫描一次，不需要随机跳转或交换元素。这个差异帮助读者区分两类能力：排序修改区间需要随机访问；有序性检测只读取相邻元素，前向遍历已经足够。

空区间和单元素区间按定义是有序的。这个结论对边界代码有直接影响：在进入排序检测前无需专门处理 size() == 0 或 size() == 1。检测函数会把它们视为满足有序条件，后续代码再根据业务是否允许空结果做判断。

is_sorted 与 is_sorted_until 的工程使用顺序是：在调试和边界检查中优先使用 is_sorted_until 获取断点；在生产路径需要快速表达前置条件时使用 is_sorted；在性能敏感热路径中，把检测放到输入接入、批处理边界或 debug 构建，让大区间扫描集中发生在可控位置。

28.3 introsort、稳定性与算法策略

标准库通常不规定排序算法的内部名称，它规定接口效果、复杂度、迭代器要求和比较器要求。源码阅读中应把“标准承诺”和“常见实现形状”分开：前者决定可移植语义，后者帮助理解性能、临时内存和极端输入下的行为。

std::sort 的常见实现形状是 introsort。Introsort 是一种混合策略：先用 quicksort 风格的分区获得较好的平均性能；递归深度超过阈值时切换到 heap sort 风格的路径，限制最坏情况比较次数；小区间再用 insertion sort 风格收尾，减少常数开销。这个策略解释了 std::sort 同时追求平均速度和最坏复杂度的原因。

下面的伪代码描述常见实现形状。它是教学简化代码，不对应某个标准库实现的真实源码符号或行号。

template <class RandomIt, class Compare>
void sort_shape(RandomIt first, RandomIt last, Compare comp) {
    auto depth_limit = 2 * floor_log2(last - first);
    introsort_loop(first, last, depth_limit, comp);
    final_insertion_sort(first, last, comp);
}

这段形状说明三个关键点。第一，last - first 暴露了随机访问迭代器要求，因为算法需要常数时间计算距离和跳转。第二，深度限制把分区策略的极端递归纳入控制。第三，小区间插入排序是常见常数优化，不能由此推导出标准强制某个具体算法。

std::stable_sort 的常见实现形状更接近 merge sort。它需要在合并两个有序子区间时保留等价元素的相对顺序，因此稳定性来自合并规则：当左侧元素和右侧元素等价时，优先输出左侧先出现的元素。实现通常尝试申请临时缓冲区；缓冲充足时合并成本较低，缓冲不足时会选择额外比较次数更多的路径。

template <class RandomIt, class Compare>
void stable_sort_shape(RandomIt first, RandomIt last, Compare comp) {
    if (last - first <= small_range_limit) {
        insertion_sort_stable(first, last, comp);
        return;
    }

    auto mid = first + (last - first) / 2;
    stable_sort_shape(first, mid, comp);
    stable_sort_shape(mid, last, comp);
    stable_merge_preserving_left_equivalent(first, mid, last, comp);
}

这段形状把稳定性的来源落到合并阶段。稳定排序的代价通常体现在临时内存、移动次数和常数开销上。若元素很大、移动昂贵或比较器成本较高，稳定排序的选择应由业务语义驱动。只在同分、同键或多阶段排序需要保留原顺序时，它才是结果语义的必要条件。

std::partial_sort 的常见实现形状是维护一个大小为 K 的堆。算法先把 [first, middle) 建成堆，然后扫描剩余元素。每遇到一个应进入前 K 的元素，就替换堆顶并调整堆。最终再把前 K 个元素转成有序前缀。这个策略解释了它的复杂度约为 $N \log K$，其中 $K = middle - first$。

std::nth_element 的常见实现形状是 selection algorithm，常见名称是 introselect。它通过分区反复缩小包含 nth 的一侧，只关注目标位置所在的子区间。平均比较次数为线性级别，结果只保证目标位置和两侧分区关系。若后续代码需要前半部分内部有序，选择算法提供的语义还不够。

这张图对应 nth_element 的核心工作：它持续把问题缩小到包含目标位置的一侧。与全排序相比，它少做了很多“让两侧内部也有序”的工作。调用者若只需要中位数或分位阈值，这个结果强度刚好匹配；若需要排序后的完整前缀，应换成 partial_sort 或在选择后再排序前缀。

源码阅读时可以用四个问题识别排序策略。算法是否需要随机跳转和距离计算，决定它是否依赖随机访问迭代器；算法是否保留等价元素原顺序，决定它是否为稳定算法；算法是否申请临时缓冲，影响内存峰值和失败路径；算法是否建立完整顺序，决定后续代码能否安全使用二分、集合和合并算法。

28.4 comparator 与 strict weak ordering

比较器是排序算法的语义核心。对 comp(a, b) 的工作定义是：当它返回 true 时，a 应排在 b 之前。标准库排序算法要求比较器形成严格弱序（strict weak ordering）。这个要求让算法能够把元素划分为有序的等价类，并在交换、分区、合并和剪枝时保持一致结论。

严格弱序可以用四个可检查条件理解。第一，自反位置返回 false，即 comp(a, a) 为 false。第二，若 comp(a, b) 为 true，则 comp(b, a) 为 false。第三，若 comp(a, b) 与 comp(b, c) 都为 true，则 comp(a, c) 也应为 true。第四，等价关系 !comp(a, b) && !comp(b, a) 本身应具有传递性。

贯穿材料中的 higher_score 满足这些条件。对于同一个记录，分数不会大于自身。若 left.score > right.score 成立，反向的 right.score > left.score 就不成立。分数大小关系具有传递性。等价类由相同分数形成，同分记录之间的等价关系也具有传递性。

工程中常见错误是把“小于等于”或“大于等于”写进比较器。下面的比较器在相等分数时返回 true，它破坏了 comp(a, a) == false 这条条件。

bool broken_higher_score(const ScoreRecord& left, const ScoreRecord& right) {
    return left.score >= right.score;
}

这个比较器会告诉排序算法：一个元素应排在自己之前，两个同分元素也可以互相排在对方之前。分区和交换逻辑在这种关系下无法形成稳定的“前方”和“后方”。标准库算法遇到不满足比较要求的输入时，结果不具备可移植语义；实践中可能表现为顺序混乱、断言失败、无限循环或只在特定实现上偶发错误。

另一个错误是比较器依赖会变化的外部状态。下面的比较器把调用次数混入结果，第一次和第二次比较同一对元素可能给出不同答案。

struct FlippingComparator {
    mutable int calls = 0;

    bool operator()(const ScoreRecord& left, const ScoreRecord& right) const {
        ++calls;
        if (calls % 2 == 0) {
            return left.score > right.score;
        }
        return left.name < right.name;
    }
};

排序算法会多次比较同一批元素，并且比较顺序由实现策略决定。比较器必须像一个稳定关系，调用前后应给出一致结论。若关系随着调用次数、系统时间、随机数或可变全局变量改变，算法内部已经建立的局部结论会被后续调用推翻。

比较器也不应修改被比较对象。排序算法会把元素移动、交换和分区，比较阶段只负责观察。若比较器在观察时改变对象内容，后续比较面对的输入已经被隐藏修改，结果关系无法闭合。对对象进行缓存、日志统计或懒加载时，应把副作用放在算法调用前后，比较器本身保持只读。

多字段排序应把业务顺序显式写成词典序。比如“分数降序，分数相同时按录入序号升序”可以写成如下比较器。它把等价类从“同分”缩小为“同分且同序号”，排序结果也由此拥有更强的确定性。

bool score_desc_seq_asc(const ScoreRecord& left, const ScoreRecord& right) {
    if (left.score != right.score) {
        return left.score > right.score;
    }
    return left.seq < right.seq;
}

这段比较器仍满足严格弱序。它先用分数划分主顺序，再用序号划分次顺序。若业务希望同分记录保留进入区间时的原顺序，也可以保持 higher_score，然后选择 std::stable_sort。前者把次序写进比较器，后者把次序交给稳定算法保留；两种方式的语义边界不同。

验证比较器时，可以使用小样本手工检查。选取三个元素 a、b、c，覆盖小于、等价和大于三种关系。先检查 comp(a, a)，再检查互斥性，再检查传递性，最后检查等价关系传递性。比较器越接近业务规则，越应把这些检查放进单元测试，尤其是涉及浮点数、空值、大小写折叠、区域排序和多字段条件时。

28.5 排序算法复杂度和工程选型

排序选型应从结果需求开始，再映射到具体算法名称。完整排序、稳定完整排序、前 K 有序和第 N 位置选择交付的结果不同。结果需求确定后，再看规模、稳定性、比较成本、移动成本、额外内存、迭代器能力和后续算法前提。

复杂度的第一层是比较次数。std::sort 的比较次数为 $O(N \log N)$；std::stable_sort 在临时内存充足时通常也是 $O(N \log N)$，缓冲不足时可能退化到 $O(N \log^2 N)$ 比较；std::partial_sort 约为 $N \log K$；std::nth_element 平均为 $O(N)$ 比较；std::is_sorted 和 std::is_sorted_until 是线性扫描。

复杂度的第二层是元素移动和内存访问。排序算法会交换或移动元素，元素越大，移动成本越高。若元素包含大字符串、动态数组或外部资源句柄，比较成本和移动成本都应被单独评估。工程上常见做法是排序轻量索引、指针或 std::reference_wrapper，再用结果访问原对象。

下面的例子把记录对象保留在原存储中，只排序记录下标。它适合记录对象体积大、排序视图多、原数据需要保持物理顺序的场景。

std::vector<ScoreRecord> records = {
    {"Ada", 90, 0}, {"Bjarne", 95, 1}, {"Chloe", 90, 2},
    {"Dennis", 80, 3}, {"Edsger", 95, 4}, {"Fay", 70, 5}
};

std::vector<std::size_t> order(records.size());
for (std::size_t i = 0; i < order.size(); ++i) {
    order[i] = i;
}

std::sort(order.begin(), order.end(), [&](std::size_t left, std::size_t right) {
    return records[left].score > records[right].score;
});

for (std::size_t index : order) {
    std::cout << records[index].name << ' ';
}
std::cout << '\n';

这个写法的代价从“移动完整记录”变成“移动下标”。比较器多了一次间接访问，数据局部性可能下降。若记录很小，直接排序记录更简单；若记录很大或有多套排序视图，下标排序能降低移动开销并保留原始存储顺序。

稳定性是独立于复杂度的语义要求。需要保留等价元素原相对顺序时，选择 std::stable_sort 或把次级规则写入比较器。两者交付不同结果：稳定排序保留输入顺序，次级规则建立新的确定顺序。若输入顺序本身就是业务时间线，稳定排序表达更直接；若次级规则来自业务字段，比较器表达更直接。

局部结果是降低成本的入口。只展示前 20 条时，全量 sort 会对所有尾部元素建立顺序；partial_sort 只保证前 20 条有序。只需要中位数、90 分位阈值或 Top K 分界线时，nth_element 能减少比较工作。若后续又要排序 Top K，常见组合是先 nth_element 切出前 K，再对 [first, kth) 调用 sort。

auto kth = records.begin() + 3;
std::nth_element(records.begin(), kth, records.end(), higher_score);
std::sort(records.begin(), kth, higher_score);

这段组合适合“数据很大、K 相对较小、需要 Top K 有序展示”的场景。nth_element 先把前 K 个候选放到前缀，sort 再只整理这个前缀。若 K 很接近 N，直接 sort 的常数和实现优化可能更合适。选型应通过数据规模和真实比较成本验证。

迭代器能力是硬性入口。排序修改算法需要随机访问迭代器；检测算法只需要前向迭代器。对 std::list 这类节点式容器，使用成员 sort 能利用节点重连。把链表强行复制到 vector 再排序，有时是合理选择：当后续需要随机访问、二分或连续内存遍历时，复制成本可能被后续收益抵消。

异常和执行策略也会影响边界。普通排序调用中，比较器抛异常会中断算法，区间中元素仍是有效对象，但具体顺序通常只能视为未完成的中间状态。C++17 起的标准执行策略重载有额外规则，标准策略下被调用函数抛出异常可能导致 std::terminate。排序比较器在并行策略中还应满足无共享可变状态、可并发调用和结果稳定的要求。

最终选型顺序可以固定为七步。第一，确定后续代码读取整个区间、前 K 前缀、第 N 个位置还是只检查前提。第二，确定等价元素是否需要保留输入顺序。第三，确认迭代器能力。第四，确认比较器严格弱序且只读。第五，估算 N、K、比较成本和移动成本。第六，判断额外内存峰值是否可接受。第七，用小样本断言 is_sorted、is_sorted_until 或分区关系，验证调用结果与需求一致。

最小自检任务

给定下面的数据结构和比较器，回答四个问题：一，比较器是否满足排序算法需要的严格弱序；二，只输出分数最高的 3 条且要求这 3 条内部按分数降序时应选哪个算法；三，只求第 3 名分数阈值时应选哪个算法；四，若同分记录必须保留原输入顺序，应怎样改调用或比较器。

struct ScoreRecord {
    std::string name;
    int score;
    int seq;
};

bool comp(const ScoreRecord& left, const ScoreRecord& right) {
    return left.score >= right.score;
}

答案要点

这个比较器不满足严格弱序。对任意记录 x，comp(x, x) 会返回 true，违反自反位置返回 false 的要求。同分的两个记录也会互相认为对方应排在前面，排序算法无法建立一致的前后关系。正确的分数降序比较器应写成 left.score > right.score。

只输出分数最高的 3 条且要求这 3 条内部有序时，直接选择 std::partial_sort(first, first + 3, last, higher_score)。它保证前 3 条是全区间中分数最高的 3 条，并且前缀内部按比较器排序。尾部顺序没有承诺，后续代码不应依赖尾部有序。

只求第 3 名分数阈值时，选择 std::nth_element(first, first + 2, last, higher_score)。调用后 first + 2 位置保存完整排序后第 3 个位置会出现的某个元素，两侧满足分区关系。两侧内部顺序没有排序承诺。

同分记录需要保留原输入顺序时，有两条合法路径。第一，保持比较器为 left.score > right.score，并使用 std::stable_sort 进行完整稳定排序。第二，把次级规则写入比较器，例如分数相同时比较 seq，使用普通 std::sort 得到“分数降序、序号升序”的确定顺序。若需求明确是保留输入顺序，稳定排序更直接；若需求明确是按字段打破同分，复合比较器更直接。

本章知识点总结

• 排序目标：排序算法选型应先确定要完整顺序、稳定完整顺序、前 K 有序、位置阈值还是有序性检测。
• sort：std::sort 交付完整有序区间，等价元素原相对顺序没有保留承诺。
• stable_sort：std::stable_sort 交付完整有序区间，并保留等价元素的原相对顺序。
• partial_sort：std::partial_sort 只保证前缀包含全区间最靠前的 K 个元素，且该前缀内部有序。
• nth_element：std::nth_element 保证目标位置与两侧分区关系，两侧内部顺序没有排序承诺。
• 有序检测：std::is_sorted 返回整体判断，std::is_sorted_until 返回第一个破坏有序性的断点。
• 迭代器能力：排序修改算法需要随机访问迭代器，有序性检测只需要前向迭代器。
• 常见策略：std::sort 常见实现形状是 introsort，稳定排序常见实现形状依赖合并和临时缓冲。
• 稳定性：稳定性是结果语义要求，适用于同键保留输入顺序和多阶段排序。
• 严格弱序：比较器必须让自反位置为假、互斥关系成立、传递关系成立，并形成可传递的等价类。
• 错误比较器：使用 <=、>=、可变外部状态或修改元素的比较器会破坏排序算法的语义前提。
• 复合比较器：多字段排序应把主键和次键写成清晰的词典序规则。
• 移动成本：元素体积大或资源重时，可以排序下标、指针或引用包装器来降低移动开销。
• 局部结果：Top K 和分位阈值需求应优先考虑 partial_sort、nth_element 或二者组合。
• 选型顺序：先看结果范围，再看稳定性、迭代器、比较器、规模成本、内存峰值和验证方式。