在排序算法的稳定性 [英] Stability in sorting algorithms
问题描述
我米很好奇，为什么稳定或不重要的排序算法？
I m very curious, why stability is or is not important in sorting algorithms?
任何想法？
推荐答案
一个排序算法被认为是稳定的，如果两个对象具有相同的键出现在相同的顺序排序输出它们出现在输入数组中进行排序。有些排序算法是稳定的由像插入排序自然，归并排序，冒泡排序等，而有些排序算法不一样，堆排序，快速排序等。
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:
桃 稻草 苹果 叉勺
在第一个字母稳定，排序为我们提供了：
Stable-sorting by the first letter gives us:
苹果 桃 稻草 叉勺
在一个不稳定的算法，稻草或叉勺可以互换，但在稳定的排序，他们留在同一个相对位置（也就是，因为稻草出现在输入叉勺前，它也出现叉勺前 '中的输出）。
In an unstable algorithm, straw or spork may be interchanged, but in stable sort, 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 stable sort by the first name, then 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.
这篇关于在排序算法的稳定性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
