严格按O(n)时间对整数数组进行排序

Question

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

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

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

输入

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

产量

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

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

Answer 1

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

  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}

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

New array: {-9, 14}

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

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

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