稳定排序总是在相同的输入上返回相同的解(排列)。

例如，[2,1,2]将使用稳定排序作为排列[2,1,3](第一个是索引2，然后是索引1，然后是索引3)，这意味着输出总是以相同的方式洗牌。其他不稳定，但仍然正确的排列是[2,3,1]。

快速排序是不稳定的排序，同一元素之间的排列差异取决于选取枢轴的算法。有些实现是随机的，可以快速排序，使用相同的算法对相同的输入产生不同的排列。

稳定排序算法具有一定的确定性。

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

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

稳定排序算法:

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

不稳定排序算法:

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

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

稳定性之所以重要，有几个原因。一个是，如果两个记录不需要交换，交换它们可能会导致内存更新，一个页面被标记为脏，并且需要重新写入磁盘(或其他慢介质)。

这取决于你做什么。

假设您有一些具有姓和名字段的人员记录。首先按名字排序。如果使用稳定的算法按姓氏对列表进行排序，那么您将得到一个按姓和名排序的列表。

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

背景:一个“稳定的”排序算法使具有相同排序键的项保持有序。假设我们有一个5个字母的单词列表:

peach
straw
apple
spork

如果我们只根据每个单词的首字母对列表进行排序，那么稳定排序将产生:

apple
peach
straw
spork

在不稳定排序算法中，稻草和叉叉可能会互换，但在稳定排序算法中，它们的相对位置保持不变(即由于稻草在输入中出现在叉叉之前，因此在输出中也出现在叉叉之前)。

我们可以使用这个算法对单词列表进行排序:按第5列、第4列、第3列、第2列、第1列进行稳定排序。 最后，它将被正确排序。说服你自己。(顺便说一下，这个算法叫做基数排序)

现在来回答你的问题，假设我们有一个名字和姓氏的列表。我们被要求“先按姓，再按名”排序。我们可以先按名字排序(稳定或不稳定)，然后按姓氏排序。在这些排序之后，列表主要按照姓氏排序。但是，如果姓氏相同，则对名字进行排序。

你不能以同样的方式堆叠不稳定的类型。