按照预定义的排序顺序对数组进行排序

Question

我需要递归地对k排序的数组进行排序，其中数组是一组“排序”的排序值。

由以下等式A [i]定义的k个排序数组<=每个i的A [i + k]

一个例子是数组{6，1，3，7，2，4}和k = 3这是因为A [0] <= A [3]，A [1] <= A [4]，A [2] <= A [3]其中A [i] <= A [i + k]

我如何开始解决这个问题？它需要递归完成，我什至不知道从哪里开始。

Answer 1

让我们用k = k_original调用数组A。

要递归执行此操作，您可以将其分成2个较小的数组他们的k = k_original / 2。

例如：您的k_original = 5，然后将其分成2个数组，其中k = 3和k = 2。

• 首先通过（k = 3）取元素：A [0]，A [1]，A [2]，A [5]，A [6]，A [7]，A [8]， A [10]，A [11]，A [12]，...仅取3个元素并跳过下2个元素（它们用于另一个小数组），请遵循问题的规则，A [0]

• 其余元素进入第二个数组（在这种情况下为k = 2），它们还将满足（k = 2）的规则。

如果要分解，请先分解（k = 1），然后返回数组，可以确定它已经被排序。

然后使用2个较小的已排序数组，只需merge 2 sorted array即可将它们组合。

这是我的伪代码：

function sortK (A, k) :
    if (k=1) return A;
    A_first_half = A[0 ~ k/2] + A[k ~ 3k/2] + A [2k ~ 5k/2] + ...
    A_second_half = A[k/2 ~ k] + A[3k/2 ~ 2k] + A[5k/2 ~ 3k] + ...
    sorted_first_half = sortK (A_first_half, k/2);
    sorted_second_half = sortK (A_second_half, k/2);
    return merge(A_first_half, A_second_half);

注意：当k不能除以2时，需要注意大小写，但实际上并不难，请像我的示例那样做。