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年)出现了卡片整理(合并)机，可以通过比较字段来合并两副牌。输入是两副已经排序的牌，一副主牌和一副更新牌。整理器将两个甲板合并为一个新的主箱和一个存档箱，存档箱可选地用于主副本，以便新的主箱在出现副本时只有更新卡。这可能是最初(自底向上)归并排序背后思想的基础。

如果两个具有相同键的对象在排序输出中以与在输入未排序数组中相同的顺序出现，则排序算法称为稳定的。一些排序算法本质上是稳定的，如插入排序，归并排序，冒泡排序等。有些排序算法不是，比如堆排序，快速排序等等。

然而，任何给定的不稳定排序算法都可以被修改为稳定排序算法。可以有排序算法特定的方法使其稳定，但一般来说，任何基于比较的排序算法本质上不稳定，都可以通过改变键比较操作来修改为稳定，以便两个键的比较将位置作为具有相同键的对象的一个因素。

引用: http://www.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

排序稳定性是指具有相同键的记录在排序前后保持相对顺序。

因此，当且仅当你要解决的问题需要保持相对顺序时，稳定性才重要。

如果你不需要稳定性，你可以从库中使用一个快速的、占用内存的算法，比如堆排序或快速排序，然后忘记它。

如果你需要稳定，那就更复杂了。稳定算法比不稳定算法具有更高的大o CPU和/或内存使用量。所以当你有一个大的数据集时，你必须在CPU和内存之间做出选择。如果CPU和内存都受到限制，就有问题了。一种较好的折衷稳定算法是二叉树排序;维基百科上有一个基于STL的c++实现，简单得可怜。

通过添加原始记录号作为每条记录的最后位置键，可以将不稳定的算法变为稳定的算法。

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:当然，对特定问题进行两次排序的方法并不是最好的解决方案，但对于解释海报的问题来说，这应该足够了。

稳定排序算法是将相同的元素按照它们在输入中出现的相同顺序进行排序，而不稳定排序可能不满足这种情况。-我感谢我的算法讲师Didem Gozupek提供了关于算法的见解。

我再次需要编辑这个问题，因为有些人没有理解演讲的逻辑。它演示了对w.r.t. first元素进行排序。另一方面，您可以考虑由键-值对组成的示例。

稳定排序算法:

插入排序 归并排序 冒泡排序 蒂姆排序 计数排序 块排序 Quadsort 图书馆分类 鸡尾酒摇酒器 Gnome排序 奇偶排序

不稳定排序算法:

堆排序 选择排序 壳类 快速排序 Introsort(受制于快速排序) 树的种类 循环排序 Smoothsort 比赛排序(以Hesapsort为准)