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

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