algorithm - 排序算法可以破坏预先存在的元素顺序吗？

Question

我想知道我遇到的一个问题。

我的情况如下所示:

我有一组数据和 2 个比较器。 您可以假设第一个比较器按字母顺序对项目进行排序，另一个比较器根据其他一些条件(例如自定义级别值)对项目进行排序。

所以给定以下数据:

1: b / lvl 1
2: c / lvl 1
3: a / lvl 1
4: d / lvl 2

第一次排序后应该是这样的:

a, b, c, d

在第二个之后:

d, a, b, c

到目前为止一切顺利。 我知道可以破坏第一次排序(例如使用 Bogosort)。 所以这可能是第二种输出:

d, b, c, a

但是是否有任何“适当的”排序算法也可以做到这一点？

Answer 1

你说的是stability :

When sorting some kinds of data, only part of the data is examined when determining the sort order. For example, in the card sorting example to the right, the cards are being sorted by their rank, and their suit is being ignored. The result is that it's possible to have multiple different correctly sorted versions of the original list. Stable sorting algorithms choose one of these, according to the following rule: if two items compare as equal, like the two 5 cards, then their relative order will be preserved, so that if one came before the other in the input, it will also come before the other in the output.

许多算法是稳定的，而许多其他算法则不稳定。

两个相当著名的例子 -(典型)quick-sort不稳定，merge-sort稳定。

参见 Wikipedia一长串排序算法，包括它们是否稳定。