0

这个问题与哪种排序算法对大多数排序数据最有效？

不同之处在于我还有其他非常重要的限制：每次排序后值都会少量更改。

这意味着向量几乎保持排序，并且移位的值几乎在它们的位置。在进行了一些测试之后，似乎相同的答案适用于我的案例。

你知道在这种情况下可能更好的其他算法吗？

4

5 回答 5

1

考虑 timsort 或 smoothsort。这些设计考虑了大部分排序的数据。

于 2012-08-17T16:09:55.157 回答
0

如果是频繁更新的情况，维护一个索引结构（即二叉搜索树）可能比一遍又一遍地对向量进行排序更好。

于 2012-08-17T06:37:40.117 回答
0

插入排序和冒泡排序对于已经排序的输入都具有线性最佳情况复杂度（这是最佳的，因为值不断变化，即您必须查看输入向量的每个元素），它们是稳定（考虑到您的问题描述，这似乎是一个有用的属性）。

于 2012-08-17T10:14:29.253 回答
0

比较所有对 a[i] <= a[i+1]。如果这是错误的，则将第二个元素移动到新数组中。

对新数组进行排序（合并排序、堆排序或任何其他 O(n*log n) 算法），然后再次合并新旧数组。

于 2012-08-17T17:51:13.750 回答
0

这个怎么样：

Def CheckedMergeSort(L)

    Count = 0
    S(1) = 0

    For I in 2 to |L|
       If (L(I-1) < L(I))
           Count = Count + 1
           S(I) = Count

    Def MergeSort(A, B)
        If (A != B and S(B)-S(A) != B-A)
            C = (B + A) / 2
            MergeSort(A,C)
            MergeSort(C+1,B)
            InplaceMerge(L(A..C), L(C+1..B))

    MergeSort(1, |L|)

对输入进行线性时间预传递以填充 S(i)，它跟踪 i 之前有多少对已按排序顺序排列。

然后通过减去两个边界 S(j)-S(i) 并将其与 j-1 进行比较，我们可以确定任何子序列 L(i..j) 是否按排序顺序。

然后，合并排序可以跳过它在恒定时间内递归中找到的任何排序序列。

（例如，如果数组在入口处排序，则 MergeSort(1, |L|) 变为 noop。）

于 2012-08-17T18:14:33.157 回答