什么是排序算法的稳定性，为什么它很重要?

如果具有相同键的两个对象在排序输出中的出现顺序与它们出现在要排序的输入数组.一些排序算法本质上是稳定的，如插入排序、归并排序、冒泡排序等.而一些排序算法则不是，如堆排序、快速排序等.

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.

背景:稳定"排序算法使具有相同排序键的项目按顺序排列.假设我们有一个由 5 个字母组成的单词列表:

Background: a "stable" sorting algorithm keeps the items with the same sorting key in order. Suppose we have a list of 5-letter words:

peach
straw
apple
spork

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

If we sort the list by just the first letter of each word then a stable-sort would produce:

apple
peach
straw
spork

在不稳定排序算法中，straw 或 spork 可以互换，但在稳定算法中，它们保持相同的相对位置(也就是说，由于 straw 在输入中出现在 spork 之前，它在输出中也出现在 spork 之前).

In an unstable sort algorithm, straw or spork may be interchanged, but in a stable one, they stay in the same relative positions (that is, since straw appears before spork in the input, it also appears before spork in the output).

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

We could sort the list of words using this algorithm: stable sorting by column 5, then 4, then 3, then 2, then 1. In the end, it will be correctly sorted. Convince yourself of that. (by the way, that algorithm is called radix sort)

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

Now to answer your question, suppose we have a list of first and last names. We are asked to sort "by last name, then by first". We could first sort (stable or unstable) by the first name, then stable sort by the last name. After these sorts, the list is primarily sorted by the last name. However, where last names are the same, the first names are sorted.

你不能以同样的方式堆叠不稳定的排序.

You can't stack unstable sorts in the same fashion.