排序算法的稳定性是什么，为什么如此重要? [英] What is stability in sorting algorithms and why is it important?

问题描述

我很好奇，为什么稳定性在排序算法中很重要或不重要?

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:

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.

这篇关于排序算法的稳定性是什么，为什么如此重要?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！