什么是将数字列表按低高低序列排序的最有效方法？

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

假定列表不包含重复项，任意大，且未排序。

最高效的处理该问题的算法是什么？

标准方法是首先按升序对列表进行排序，然后交替地从列表的两端获取元素。然而，我想知道：是否有更节省时间的方法可以在不先对列表进行排序的情况下完成此操作？

我的提问原因：（只有在您关心的情况下才阅读此内容）

显然，这是我妹妹男友在旧金山的面试中向人们提出的问题。 我妹妹问了我这个问题，我立即想到了标准答案。 那就是每个人都会回答的。 然而，显然有一个女孩想出了一个完全不需要对列表进行排序的解决方案，看起来它可以工作。 我妹妹无法向我解释这个解决方案，但从昨晚开始，这个想法一直让我感到困惑。 我会非常感激任何帮助！ 谢谢！

- user3151680

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

- Peter de Rivaz

---

非常感谢！这样简单而优雅的解决方案让我有点尴尬，因为我没有看到它。我还有很多要学习的... - user3151680

Answer 2

一个解决方案是这样的。以伪代码给出。

假设，`nums` 至少有两个元素，并且 `nums` 中的所有元素都是不同的。

nums   = [list of numbers]

if nums[0] < nums[1]: last_state = INCREASING else: last_state = DECREASING

for i = 2 to len(nums - 1):
   if last_state = INCREASING:
      if nums[i] > nums[i-1]:
        swap (nums[i], nums[i-1])
      last_state = DECREASING
   else
      if nums[i] < nums[i-1]:
        swap (nums[i], nums[i-1])
      last_state = INCREASING

正确性证明：

每次循环迭代后，nums中索引 i 之前的元素保持交替，并且last_state表示 i 和 i-1 元素的顺序。

请注意，仅当最后考虑的3个项按顺序排列（递增或递减）时才会发生交换。因此，如果我们将第 i 个元素与 i-1 个元素交换，则 i-2 个元素和 i-1 个元素的顺序不会改变。

- Buddhima Gamlath