排序算法最适合对排序数组进行排序

Question

当对已经排序的数组进行排序时，哪种排序算法最适合使用？

Answer 1

插入排序适用于几乎排序的数据。您接近最佳结果。

这里是一个伟大的动画，显示的排序将如何执行：http://www.sorting-algorithms.com/insertion-sort

Answer 2

这要看情况。数组的大小？ “已经几乎排序”是什么意思 - 就像数据的百分比已经按顺序排列了一样？你的编程和数据存储环境是什么 - 内存中的数据，数据库，文件？说了这么多，你可以从研究Timsort开始。这是一种相对较新的排序算法，它将处理大型数据集，利用“运行”（数据已按排序顺序排列）。

Answer 3

如果您将“几乎排序”定义为具有相反数量的数据点对，而不是正确的顺序（例如，想象一下采取排序列表，然后采用不相交的连续数据点对并倒转他们），那么一个气泡排序将工作得非常好，你做了一个修改，如果你交换两个元素，那么你继续向左搜索并交换，只要相邻元素失序。如果不成对的数量是O（n），则这将具有复杂度O（n）。