arrays - 混合数组遵守某些约束的算法

Question

我有这个问题:

我必须开发一种算法来获取一个 int 数组并根据这些约束重新排列元素:

对于每个元素，必须低于其邻居或大于其邻居:

for each x in array a,
( a[x-1]<=a[x] AND a[x+1]<=a[x] )
OR
( a[x-1]>=a[x] AND a[x+1]>=a[x] )

在最坏的情况下，这一切都在 theta(n log n) 中

我不知道该怎么做，我唯一的直觉是我必须做一些类似于合并排序的事情......

抱歉我的英语不好

Answer 1

1. 对数组进行排序

2. 把它切成两半

3. 将前半部分的元素放在后半部分的元素之间

4. 如果元素个数不足则将最后一个元素移到最前面

例子:

1. 2 3 1 5 7 8 6 4 9

2. 1 2 3 4 5 6 7 8 9

3. 1 5 2 6 3 7 4 8 9

4. 9 1 5 2 6 3 7 4 8