以O(n * Log(K))复杂度对几乎排序的数组进行排序 [英] Sorting nearly sorted array with O(n*Log(K)) complexity

问题描述

问题-即将排序的数组-给定一个n个元素的数组，每个元素与已排序数组中的实际位置相距最多K个位置，设计一种算法，以O(nLogK)时间进行排序.

Problem -Nearly Sorted Array- Given an array of n elements , each of which is atmost K Position away from it's actual position in the sorted array , devise an algorithm that sorts in O(nLogK) time.

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 
achieve complexity O(nLogK).
Comparing K and n/K depends on values of n and K.

任何人都可以帮助我进行最终的合并操作或更好的方法.

Can anyone help me with the final merging operation or a better approach.

PS:我当时不知道堆或队列，因此我正在寻找一种不涉及这些的解决方案.

PS : I do not know heaps or queues at the time so I am looking for a solution which does not involve these.

推荐答案

首先，将数组划分为至少包含k+1个元素的组.这样，每个元素的合法位置要么在元素当前所在的组中，要么在左边或右边的组中，但不能更远.然后对每个组进行排序.

First, divide the array into groups of at least k+1 elements. So that each element's rightful position is either within the group where the element currently is or within the group to the left or to the right, but not further. Then sort each group.

此步骤需要O((n/k) * k log k) = O(n log k).

然后，在对每个组进行排序之后，可以将第i个组与i+1组合并，将i从1转换为n/(k+1) - 1.

Then, after sorting each group, you can merge ith group with the i+1 group, for i from 1 to n/(k+1) - 1.

通过合并，我从合并排序中了解了合并过程.这些团体不团结.它们的大小保持不变.

By merge I understand the merge procedure from a merge sort. The groups do not unite. Their sizes remain the same.

每个合并花费O(n/k)，此步骤总计为O(n).

Each merge takes O(n/k), in total this step is O(n).

这篇关于以O(n * Log(K))复杂度对几乎排序的数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！