如何输出B的排列使得A是一个摇摆不定的？

Question

我遇到了以下问题:

给定一个未排序的阵列B[1 . . 2n+1]的实数,给其输出的一个排列的线性时间算法A[1..2n+1]的B,使得A一个波浪.

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

 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,情况类似.