近似排序算法

Question

有谁知道对数组进行 k 近似排序的算法吗？

我们被要求找到 k 近似排序的算法，它应该在 O(n log(n/k)) 中运行。但我似乎找不到任何。

K-大约。排序意味着数组和任何 1 <= i <= nk 使得 sum a[j] <= sum a[j] i<=j<= i+k-1 i+1<=j<= i+k

Answer 1

我知道我这个问题已经很晚了......但是假设k是 0 和 1 之间的某个近似值（当 0 完全未排序且 1 完全排序时），答案肯定是快速排序（或合并排序） 。

考虑以下数组：

[4, 6, 9, 1, 10, 8, 2, 7, 5, 3]

假设这个数组是“未排序”的 - 现在以第 (length[array]/2) 个^元素作为基准，对该数组应用快速排序的一次迭代：length[array]/2 = 5。所以第 5^个元素是我们的枢轴（即 8）：

[4, 6, 2, 1, 3, 9, 7, 10, 8]

现在这个数组没有排序 - 但它比一次迭代前排序得更好，即它近似排序，但近似值较低，即k值较低。在数组的两半上再次重复此步骤，它就会变得更加排序。随着k向 1 增加（即完美排序），复杂度变为O(N log(N/1)) = O(N log(N))。