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

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

稳定排序算法:

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

不稳定排序算法:

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

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

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

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

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

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

这取决于你做什么。

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

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

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

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

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