将数字列表排序为交替的低 - 高 - 低序列的最有效方法是什么？

Question

假设给出了一个未排序的正整数列表,并且您希望以这样的方式对它们进行排序:元素交替为:(小于前一个元素),(大于前一个元素),(小于前一个元素)等. ..输出列表中的第一个元素可能会忽略该规则.例如,假设您的列表是:1,4,9,2,7,5,3,8,6.

一个正确的输出将是...... 1,9,2,8,3,7,4,6​​,5

另一个是...... 3,4,2,7,5,6,1,9,8

假设列表不包含重复项,任意大,并且尚未排序.

实现这一目标的处理效率最高的算法是什么？

现在,标准方法是首先按升序对列表进行排序,然后交替从列表末尾剥离元素.但是,我想知道:如果没有先对列表进行排序,是否有更省时的方法？

我的理由是:(只在你关心的情况下阅读此内容)

显然这是我姐姐的男朋友在旧金山的求职面试中给人们提出的一个问题.我妹妹问了我这个问题,我立刻想出了标准回答.这就是每个人都回答的问题.然而,显然有一个女孩提出了一个完全不同的解决方案,不需要对列表进行排序,它似乎工作.我妹妹无法向我解释这个解决方案,但自从昨晚以来,这个想法让我感到困惑.我很感激任何帮助!谢谢!

Answer 1

您可以在O(n)中执行此操作,方法是将每个元素依次放在最后,或者根据与当前最后一个元素的比较,在倒数第二个位置放置.

例如,

1,4,9,2,7,5,3,8,6
Place 1 at end, current list [1]
4>1 true so place 4 at end, current list [1,4]
9<4 false so place 9 at penultimate position [1,9,4]
2>4 false so place 2 at penultimate [1,9,2,4]
7<4 false so place 7 at penultimate [1,9,2,7,4]
5>4 true so place 5 at end [1,9,2,7,4,5]
3<5 true so place 3 at end [1,9,2,7,4,5,3]
8>3 true so place 8 at end [1,9,2,7,4,5,3,8]
6<8 true so place 6 at end [1,9,2,7,4,5,3,8,6] 

请注意,相等性测试是交替的,如果相等性为真,则放在最后,如果不成立,则放在倒数第二个位置.

示例Python代码

A=[1,4,9,2,7,5,3,8,6]
B=[]
for i,a in enumerate(A):
    if i==0 or (i&1 and a>B[-1]) or (i&1==0 and a<B[-1]):
        B.insert(i,a)
    else:
        B.insert(i-1,a)
print B