c++ - C++ 算法稳定性

Question

如何判断算法是否稳定？...

此外，此算法 Bucketsort 与 Mergesort、Quicksort、Bubblesort 和 Insertionsort 相比如何？

Answer 1

乍一看，如果您的队列是 FIFO，那么它似乎是稳定的。但是，我认为课堂或其他家庭作业中的一些背景可以帮助您做出更坚定的决心。

来自维基百科：

稳定性 稳定的排序算法保持具有相同键的记录的相对顺序。如果所有的键都不同，那么这种区别就没有必要了。但是如果有相等的键，那么排序算法是稳定的，如果每当有两条记录（比如 R 和 S）具有相同的键，并且 R 在原始列表中出现在 S 之前，那么 R 将始终出现在 S 之前排序列表。当相等的元素无法区分时，例如整数，或者更一般地说，任何以整个元素为关键的数据，稳定性都不是问题。但是，假设以下成对的数字将按它们的第一个组件排序：

http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

与其他算法相比。维基百科上有一个简洁的条目：

http://en.wikipedia.org/wiki/Bucket_sort#Comparison_with_other_sorting_algorithms

另外：https ://stackoverflow.com/a/7341355/1416221