c# - 在严格的 O(n) 时间内对整数数组进行排序

Question

我最近在面试中被问到这个问题。

给定一个包含负数和正数的排序整数数组，如何根据元素的绝对值对该数组进行求值？

这必须严格在 O(n) 时间内完成。

Input

{-9,-7,-3,1,6,8,14}

Output

{1,-3,6,-7,8,-9,14}

除了 O(n) 时间之外还有哪些可能的解决方案？

Answer 1

基本上，我们将有 2 个头，一个在数组的末尾，一个在开头。

  v                   v
{-9, -7, -3, 1, 6, 8, 14}

我们比较我们的头指向的 2 个条目的绝对值，并将较大的插入到我们新的排序数组中。所以这里是 14。

New array: {14}

然后我们将我们选择的任何项目的头部移近中心。所以在这里我们将头指向 14 到 8。

  v                v   
{-9, -7, -3, 1, 6, 8, 14}

然后我们重复这个过程，将两个绝对值中较大的一个插入到我们新的排序数组的开头。这里是-9，如|-9| > |8|

New array: {-9, 14}

在我们再次移动头部之后:

      v            v        
{-9, -7, -3, 1, 6, 8, 14}

重复直到两个头在中心相遇