c++ - sort a, b, c是否等同于sort c；排序 b;排序？

Question

在 C++ 中，我必须实现一个“类似 Excel/Access”(引用)的查询生成器，以允许对数据集进行自定义排序。如果您在 Excel 中使用查询构建器或 SQL 中的“ORDER BY a, b, c”按列 A、B 和 C 排序，您将按顺序获得所有 A，按顺序获得每组相同 A 中的所有 B，以及每组相同 B 中的所有 C 按顺序排列，这就是大多数人对“按 a、b、c 排序/排序”的理解。这似乎与“按 c 排序”，然后“按 b 排序”，然后“按 a 排序”相同 - 即。以相反的顺序在每一列上单独排序——只要你使用 stable_sort。这就是我在我的程序中实现它的方式。用户说“按 a、b、c 排序”，程序按 c 进行稳定排序，按 b 进行稳定排序，按 a 进行稳定排序——相同的结果，以及我目前使用的所有数据集。我的问题是，这是对任何数据集(提供稳定的排序算法)和任何列组合都适用的众所周知的等价性吗？是否有数学证明？到目前为止，我还没有通过谷歌或其他方式(询问程序员、统计学家和数学家)找到任何此类证据。

Answer 1

是的，这是正确的。 “证明”就在稳定排序的定义中:

A sorting algorithm is stable if whenever there are two records R and S with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list.

考虑通过在 b 上排序然后在 a 上排序来实现“按 a 排序，然后按 b 排序”的算法。第一种排序(在 b 上)将所有具有较低 b 的记录排在具有较高 b 的记录之前 - 由于是一种排序算法(稳定性不是第一种排序的要求)。

第二种排序(在a上)一定要注意b只有当a相同的时候。由于稳定，这种排序使具有相同 a 的记录的顺序与排序之前的顺序相同 - 即按 b 排序>。当您按 a 排序，然后按 b 排序时，这正是您要实现的目标。

通过观察添加更多排序步骤可以使先前步骤的结果保持原始顺序，可以将相同的证明扩展到对两个以上的键进行排序，这正是我们希望在等式组中具有的顺序具有较高排序优先级的键。