严格按O（n）时间对整数数组进行排序

I was asked this question in interview recently .

我最近在采访中被问到这个问题。

Given a sorted integer array containing negative and positive numbers , how to resort the array based on absolute values of elements ?

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

This had to be done strictly in O(n) time.

这必须在O（n）时间内严格完成。

Input

输入

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

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

Output

产量

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

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

What are the possible solutions other than O(n) time ?

除了O（n）时间以外，有哪些可能的解决方案？

3 个解决方案

#1

Basically, we're going to have 2 heads, one looking at the end of the array, one at the beginning.

基本上，我们将有两个头，一个看着阵列的末端，一个在开头。

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

We compare the absolute value of the 2 entries our heads are pointing at and insert the larger into our new, sorted array. So here it would be 14.

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

New array: {14}

We then move the head of whichever item we selected closer to the center. So here we move our head pointing at 14 to 8.

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

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

We then repeat the process, inserting the larger of the 2 absolute values into the beginning of our new, sorted array. Here that would be -9, as |-9| > |8|

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

New array: {-9, 14}

And after we move the head again:

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

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

Repeat until both heads meet in the center

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

#2

Let's take your example:

我们举个例子：

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

You could rewrite this into two parts:

您可以将其重写为两部分：

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

Two obvious observations:

两个明显的观察：

The left part is sorted descending
左侧部分按降序排序
The right part is sorted ascending
正确的部分按升序排序

Now you basically just merge these two sorted subarrays, which is possibly in linear time. Have a look for the algorithm here How to merge two sorted arrays into a sorted array?.

现在你基本上只是合并这两个排序的子阵列，这可能是线性时间。在这里查看算法如何将两个排序的数组合并为一个排序的数组？

Since you don't have these arrays split up, you find the point in the array which flips negative to positive. From that split-point, you can go index by index until the boundaries of the array and reconstruct a sorted array again.

由于您没有拆分这些阵列，因此您可以在阵列中找到将负数翻转为正数的点。从该分割点开始，您可以逐个索引，直到数组的边界，然后再次重新构建排序的数组。

#3

As mentioned in the comments, you are basically looking at a merge sort. The original data is already sorted, so all you have to do is retrieve the values in order from each of the negative and positive sets of numbers, merging them according to their absolute values.

正如评论中所提到的，您基本上是在查看合并排序。原始数据已经排序，因此您所要做的就是从每组负数和正数组中按顺序检索值，并根据它们的绝对值合并它们。

The code would look something like this:

代码看起来像这样：

int[] input = { -9, -7, -3, 1, 6, 8, 14 };
int[] output = new int[input.Length];
int negativeIndex, positiveIndex = 0, outputIndex = 0;

while (input[positiveIndex] < 0)
{
    positiveIndex++;
}

negativeIndex = positiveIndex - 1;

while (outputIndex < output.Length)
{
    if (negativeIndex < 0)
    {
        output[outputIndex++] = input[positiveIndex++];
    }
    else if (positiveIndex >= input.Length)
    {
        output[outputIndex++] = input[negativeIndex--];
    }
    else
    {
        output[outputIndex++] = -input[negativeIndex] < input[positiveIndex] ?
          input[negativeIndex--] : input[positiveIndex++];
    }
}

The above is IMHO somewhat easier to grasp, but as another answer points out, you can do it without even scanning to the 0-point of the data, by sorting from the other end. The code for that would look something like this:

以上是恕我直言，有点容易掌握，但另一个答案指出，你可以做到这一点，甚至没有扫描到数据的0点，从另一端排序。代码看起来像这样：

int[] output = new int[input.Length];
int negativeIndex =  0, positiveIndex = input.Length -1, outputIndex = input.Length - 1;

while (outputIndex >= 0)
{
    if (input[negativeIndex] >= 0)
    {
        output[outputIndex--] = input[positiveIndex--];
    }
    else if (input[positiveIndex] < 0)
    {
        output[outputIndex--] = input[negativeIndex++];
    }
    else
    {
        output[outputIndex--] = -input[negativeIndex] < input[positiveIndex] ?
            input[positiveIndex--] : input[negativeIndex++];
    }
}

#1