在 C++ 中，我必须实现一个“Excel/Access-like”（引用）查询构建器以允许对数据集进行自定义排序。如果您在 Excel 中使用查询生成器或 SQL 中的“ORDER BY a, b, c”按列 A、B 和 C 排序，您将按顺序获得所有 As，每组相同 As 中的所有 B 按顺序排列，并且每组相同 B 中的所有 C 按顺序排列，这就是大多数人所理解的“按 a、b、c 排序/排序”。这似乎与“按 c 排序”，然后“按 b 排序”，然后“按 a 排序” - 即。以相反的顺序在每一列上单独排序 - 只要您使用 stable_sort。这就是我在我的程序中实现它的方式。用户说“按 a、b、c 排序”，程序按 c、stable_sort 按 b、stable_sort 按 a - 结果相同，所有数据集 I' 到目前为止使用过。我的问题是，这是一个众所周知的对等式是否适用于任何数据集（提供了一个稳定的排序算法）和列的任何组合，甚至有数学证明吗？到目前为止，我还没有通过谷歌或其他方式（询问程序员、统计学家和数学家）找到任何这样的证据。
问问题
221 次
1 回答
4
是的，这是正确的。“证明”在稳定排序的定义中：
一个排序算法是稳定的，如果有两个记录 R 和 S 具有相同的键，并且 R 在原始列表中出现在 S 之前，那么 R 在排序列表中总是出现在 S 之前。
考虑通过排序然后排序来实现“排序a，然后排序”的算法。第一次排序 (on ) 使所有较低的记录领先于较高的记录- 因为它是一种排序算法（稳定性不是第一次排序的要求）。bbabbb
第二种排序（on ）必须只在s 相同时才a注意。由于是稳定的，这种排序使具有相同s 的记录以与排序之前相同的顺序保留 - 即按 排序。这正是您按 排序，然后按排序时所要实现的。baabab
通过观察添加更多排序步骤会使先前步骤的结果保持原始顺序，可以将相同的证明扩展到对两个以上键进行排序，这正是我们希望在键的相等组中具有的顺序更高的排序优先级。
于 2013-10-31T16:57:26.983 回答