arrays - 如何输出 B 的排列，使得 A 是一个摆动的？

Question

我遇到了以下问题:

Given an unsorted array B[1 . . 2n+1] of real numbers, give a linear time algorithm that outputs a permutation A[1..2n+1] of B such that A is a wiggly.

我基本上做了一个合并排序并改变了它:

 MergeSort(a,n)
      int i=2;
     while (i ≤ n)
     {
       Swap(a[i−1], a[i]);
       i=i+2;
     }

但时间复杂度为 O(nlogn) + O(n)(分别来自排序和循环)，产生 O(nlogn)。但我想在 O(n) 时间内完成。

我是否应该使用计数排序/基数排序/桶排序来获得线性时间，然后对其进行修改以获得一个摇摆不定的数组？

Answer 1

有一个简单的线性解决方案:

for i = 2 ... 2 * n - 1:
     if i % 2 == 0 and a[i] < a[i - 1] or i % 2 == 1 and a[i] > a[i - 1]:
         swap(a[i], a[i - 1])

正确性证明:

让我们使用归纳法:

1. 基本情况:只处理一个元素，不违反任何约束。

2. 步骤:if i % 2 == 0:如果我们在这一步不交换任何东西，前缀仍然有效。否则，我们会遇到以下情况:a[i - 2] >= a[i - 1] > a[i]。当我们进行交换时，我们可以看到 i - 2 和 i - 1 元素没有违反约束，并且最后一个位置是固定的。对于奇数 i，情况类似。