小编Dre*_*mer的帖子

问题 - 几乎排序的数组 - 给定一个包含 n 个元素的数组，每个元素离它在排序数组中的实际位置至多 K 位置，设计一个算法，在 O(nLogK) 时间内进行排序。

Approach - I divide the array in n/K elements each(n/k + 1 , if n%k!=0).

Then I run a loop n/k times ,inside which I sort eack n/k group using 
MergeSort(Complexity = KLogK).So complexity for the loop is O(nLogK).

Finally I merge the n/k groups using a Merge Function(similar to Merging 
K Sorted arrays, complexity = nLog(n/k)).

So overall complexity is between nLogK and nLog(n/K) but I have to …

我写了一个合并 K 排序数组。我发现其他站点上kn的最佳时间复杂度为 O(n k Logk)，其中是数组的数量，是每个数组中的元素数量。我认为我的是 O(n k)。

有人可以证实这一点吗？？代码如下。

private static void MergeKSortedArrays()
{
    int[][] arr = { new int[] { 3, 5, 7 }, new int[] { 1, 2, 4 }, new int[] { 6, 8, 9 } };
    int k = 3, n = 3;

    int[] output = new int[n * k];
    int[] temp = new int[k];

    for (int i = 0; i < k - 1; i++)
    {
        temp = …