哪个排序算法是最适合进行重新排序几乎完全排序列表？ [英] Which sorting algorithm is best suited to re-sort an almost fully sorted list?

问题描述

我已存储了由特定的比较函数的字符串列表。

I have a list of strings which has been sorted by a specific comparison function.

现在我不得不重新排序使用的不同的的比较函数列表中。

Now I have to re-sort this list using a different comparison function.

这个新的比较功能，例如比较某些特殊字符时，像变音符号表现略有不同。在大多数情况下，元素已被移动一个或两个时隙到达正确的位置。

This new comparison function behaves slightly different when comparing certain special characters, like Umlauts for example. In most cases the element has to be moved just one or two slots to get to the correct position.

哪个排序算法是最适合重新梳理这几乎完全分类列表中运行时执行速度方面？

Which sorting algorithm is best suited to re-sort this almost fully sorted list in terms of runtime execution speed?

推荐答案

插入排序小效果很好或近排序的列表。

Insertion sort works well on small or nearly sorted lists.

从这个 ACM纸：

这是随机生成的列表测试   列表长度的各种组合   和小有序性比率指示   该直插入排序就是最好的   对于小型或非常接近排序的列表   那Quickersort是最好的   并非如此。

Tests on randomly generated lists of various combinations of list length and small sortedness ratios indicate that Straight Insertion Sort is best for small or very nearly sorted lists and that Quickersort is best otherwise.

从wiki文章插入排序：

如果输入数组已经排序，   插入排序进行尽可能少的为N-1   比较，从而使插入   鉴于排序时，排序更有效   或近排序的阵列。

If the input array is already sorted, insertion sort performs as few as n-1 comparisons, thus making insertion sort more efficient when given sorted or "nearly-sorted" arrays.

SO问题：<一href="http://stackoverflow.com/questions/736920/is-there-ever-a-good-reason-to-use-insertion-sort">Is有过一个很好的理由来使用插入排序？

这篇关于哪个排序算法是最适合进行重新排序几乎完全排序列表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！