O(n)时间复杂度中的波排序

Question

波按时间复杂度对进行排序O(n)

波排序按数组排列，从而形成一个波。对于ex：3, 1, 4, 2, 8, 7，这将是应用wave排序后排序的数组

如果输入为1, 3, 4, 2, 7, 8，则期望1, 3, 4, 2, 7, 8的输出。产出可能因执行情况不同而有所不同。主要目标是在阵列中有一个波峰和波谷，并在O(n)中这样做。

Answer 1

请注意，您可以从线性排序数组中获得一个"wave“排序数组，只需简单地沿着数组走一次，并交换所遇到的每一对数字。使用您的示例输入：

1, 2, 3, 4, 7, 8

我们可以遍历数组并交换每对数字，给出：

2, 1, 4, 3, 7, 8

使用合并排序或类似的分而治之方法排序数组的代价是O(N*lgN)，其中N是数组的大小。最重要的是，我们需要一个单独的O(N)操作来强制执行wave排序。因此，总的顺序可以是：

O(N*lgN + N) = O(N*lgN)

Answer 2

谢谢你帮忙。但是我找到了一个在O(n)中运行的解决方案。

def waveSort(a):
    n = len(a)
    for i in range(0, n-1, 2):

        if i > 0 and a[i-1] > a[i]:
            a[i], a[i-1] = a[i-1], a[i]

        if i <= n-2 and a[i+1] > a[i]:
            a[i], a[i+1] = a[i+1], a[i]
    return arr

这是指向github上完整文件的链接

github.com/WaveSort