近似排序算法

Question

近似排序算法

arraysalgorithmsortingapproximation

5

有没有人知道一种可以对数组进行k近似排序的算法？

我们被要求找到一种k近似排序的算法，它应该在O(n log(n/k))的时间复杂度内运行，但我似乎找不到任何合适的。

K近似排序意味着对于一个数组和任意的1 <= i <= n-k，满足 sum a[j] <= sum a[j] i<=j<= i+k-1 i+1<=j<= i+k。

- Abdullah Raya

我在想这里的目标是否是将n个元素分成k组，使得第0组中的所有元素都小于第1组中的所有元素，第1组中的元素小于第2组中的元素，...第k-2组中的元素小于第k-1组中的元素。每个组中的元素不会被排序。这可以使用快速选择算法和中位数中位数（n/5版本）来完成。 - rcgldr

不，不完全是。K-近似排序意味着一个数组和任何1<= i <= n-k，使得

                  sum    a[j]  <=  sum  a[j] 
            i<=j<= i+k-1          i+1<=j<= i+k

都成立。 - Abdullah Raya

ASort算法的思想是将产品划分为一系列等大小的排序箱，使得每个箱中的元素的排名小于后续箱中任何元素的排名。该算法出自《近似排序pdf》（http://www.inf.ethz.ch/personal/smilos/approx.pdf）。我搜寻了K-近似排序，但仅得到了关于近似排序的结果，所以我可能有所遗漏。 - rcgldr

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- John Devitt · Accepted Answer

我知道我回答得很晚...但是假设k是在0到1之间的近似值（当0表示完全未排序，而1表示已完美排序），那么这个问题的答案肯定是快速排序（或归并排序）。

考虑以下数组：

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

假设这个数组是“未排序”的 - 现在对这个数组应用快速排序算法的一个迭代，以 (length[array]/2)th 个元素作为枢轴: 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))。