algorithm - 减少正数排序任务以证明 nlogn 复杂性

Question

事实证明，基于比较的排序具有复杂性 T(n)=nlogn。因此，如果我们有正整数数组(不是特定的整数，因此无法应用 counting 或 radix 排序)如何确定 Sort 的适当减少> 到 SortPositiveNumbers(例如)以证明存在多项式和正确的变换并且 SortPositiveNumbers 也有 nlogn 的下界？

如有任何帮助，我们将不胜感激。

Answer 1

我们可以使用以下伪代码将 Sort 简化为 SortPositiveNumbers:

Sort(A[1..n])
   B[1..n]
   p <- n+1
   s <- 0
   for k <- 1 to n
       if A[k] > 0
          p <- p-1
          B[p] <- A[k]
       else if A[k] < 0
          s <- s+1
          B[s] <- -A[k]

   SortPositiveNumbers(B[1...s])
   SortPositiveNumbers(B[p...n])

   for k <- 1 to s
       A[k] <- -B[s+1-k]
   for k <- s+1 to p-1
      A[k] <- 0
   for k <-p to n
      A[k] <- B[k]

这里的归约是线性的 (2n)，所以它是多项式的并且是正确的，因为它使用 SortPositiveNumbers 仅对 A 中的正数进行排序(负数转换为正数)，最后再次归约将正数转换为负数并将它们相加放入排序数组的所需索引中。