使用预定义的排序顺序对数组进行排序

Question

我需要递归地对 k 排序数组进行排序，其中数组是一组 "sort of" 排序值。

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

这方面的一个例子是数组 {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

让我们调用你的数组 A，其中 k = k_original。

要以递归方式执行此操作，您可以将其分成 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[10], A[11], A[12], ... 只取3个元素并跳过接下来的2个（它们用于另一个小数组），按照问题的规则，A[0] < A[ 5], A[1] < A[6], ... 所以这个小数组满足 (k=3)
其余元素进入第二个数组（在本例中为 k=2），它们也将满足 (k=2) 的规则。

继续分解，如果分解后，(k=1)然后return数组，你可以确定它已经排序了。

然后用 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 整除时，你需要注意 case，但这真的不难，就像我的例子一样。

使用预定义的排序顺序对数组进行排序

Sort an array with a pre-defined sort order

sorting

algorithm

pseudocode