我很好奇，为什么稳定性在排序算法中很重要或者不重要?
当前回答
如果你假设你正在排序的只是数字，并且只有它们的值才能识别/区分它们(例如，具有相同值的元素是相同的)，那么排序的稳定性问题是没有意义的。
然而，排序中具有相同优先级的对象可能是不同的，有时它们的相对顺序是有意义的信息。在这种情况下，不稳定排序会产生问题。
例如，你有一个数据列表，其中包含所有玩家在游戏中使用关卡[L]清理迷宫的时间成本[T]。 假设我们需要根据玩家清理迷宫的速度来对他们进行排名。然而，这里还有一个附加规则:无论花费多长时间，以更高级别清理迷宫的玩家总是拥有更高的等级。
当然，你也可以尝试着将配对值[T,L]映射到一个实数[R]，然后根据[R]值对所有玩家进行排序。
然而，如果稳定排序是可行的，那么你可以简单地按照[T](更快的玩家优先)和[L]对整个列表进行排序。在这种情况下，玩家的相对顺序(根据时间成本)不会在你根据他们清理的迷宫级别对他们进行分组后发生改变。
PS:当然，对特定问题进行两次排序的方法并不是最好的解决方案，但对于解释海报的问题来说，这应该足够了。
其他回答
Some more examples of the reason for wanting stable sorts. Databases are a common example. Take the case of a transaction data base than includes last|first name, date|time of purchase, item number, price. Say the data base is normally sorted by date|time. Then a query is made to make a sorted copy of the data base by last|first name, since a stable sort preserves the original order, even though the inquiry compare only involves last|first name, the transactions for each last|first name will be in data|time order.
一个类似的例子是经典的Excel，它一次只能对3列进行排序。要对6列进行排序，首先对最低有效度的3列进行排序，然后对最高有效度的3列进行排序。
A classic example of a stable radix sort is a card sorter, used to sort by a field of base 10 numeric columns. The cards are sorted from least significant digit to most significant digit. On each pass, a deck of cards is read and separated into 10 different bins according to the digit in that column. Then the 10 bins of cards are put back into the input hopper in order ("0" cards first, "9" cards last). Then another pass is done by the next column, until all columns are sorted. Actual card sorters have more than 10 bins since there are 12 zones on a card, a column can be blank, and there is a mis-read bin. To sort letters, 2 passes per column are needed, 1st pass for digit, 2nd pass for the 12 11 zone.
后来(1937年)出现了卡片整理(合并)机，可以通过比较字段来合并两副牌。输入是两副已经排序的牌，一副主牌和一副更新牌。整理器将两个甲板合并为一个新的主箱和一个存档箱，存档箱可选地用于主副本，以便新的主箱在出现副本时只有更新卡。这可能是最初(自底向上)归并排序背后思想的基础。
我知道这个问题有很多答案，但对我来说，罗伯特·哈维的这个答案总结得更清楚:
稳定排序是一种保留输入集原始顺序的排序，其中[不稳定]算法不区分两个或多个项。
源
稳定性之所以重要，有几个原因。一个是，如果两个记录不需要交换，交换它们可能会导致内存更新，一个页面被标记为脏，并且需要重新写入磁盘(或其他慢介质)。
这取决于你做什么。
假设您有一些具有姓和名字段的人员记录。首先按名字排序。如果使用稳定的算法按姓氏对列表进行排序，那么您将得到一个按姓和名排序的列表。
如果你假设你正在排序的只是数字，并且只有它们的值才能识别/区分它们(例如，具有相同值的元素是相同的)，那么排序的稳定性问题是没有意义的。
然而，排序中具有相同优先级的对象可能是不同的，有时它们的相对顺序是有意义的信息。在这种情况下，不稳定排序会产生问题。
例如，你有一个数据列表，其中包含所有玩家在游戏中使用关卡[L]清理迷宫的时间成本[T]。 假设我们需要根据玩家清理迷宫的速度来对他们进行排名。然而，这里还有一个附加规则:无论花费多长时间，以更高级别清理迷宫的玩家总是拥有更高的等级。
当然，你也可以尝试着将配对值[T,L]映射到一个实数[R]，然后根据[R]值对所有玩家进行排序。
然而，如果稳定排序是可行的，那么你可以简单地按照[T](更快的玩家优先)和[L]对整个列表进行排序。在这种情况下，玩家的相对顺序(根据时间成本)不会在你根据他们清理的迷宫级别对他们进行分组后发生改变。
PS:当然，对特定问题进行两次排序的方法并不是最好的解决方案，但对于解释海报的问题来说，这应该足够了。
