数组排序与前半部分和后半部分排序

Question

可能重复：
Regarding in-place merge in an array

在本次采访的问题绊倒了。 给定一个大小为n的数组，其中前n/2是排序的，后半部分是 。将整个阵列排序。 现在我能想到的地方有点像插入排序，将有空间复杂度为O（1），但时间复杂度将超过O（n）。 O（n）到位解决方案是否可能出现此问题？

Answer 1

有两个（逻辑）指针 - 让我们称它们为x和y。 x指向前n/2个元素的第一个元素。 y指向第二个n/2元素的第一个元素。如果在y处的元素小于x处的元素（我们称n（y）和n（x）），则在x处插入n（y），并将y加1 x。否则，将x增加1并再次检查。一旦y点击'n'，停止y并继续重复直到x == y。

E.g.

2 4 7 8 1 3 5 6 
x  y 

1 2 4 7 8 3 5 6 
    x  y 

1 2 4 7 8 3 5 6 
    x  y 

1 2 3 4 7 8 5 6 
     x  y 

1 2 3 4 7 8 5 6 
     x y 

1 2 3 4 5 7 8 6 
      x y 

1 2 3 4 5 6 7 8 
      x y 

1 2 3 4 5 6 7 8 
       (x,y) 

Answer 2

通常为了排序两个已排序的列表，您可以使用合并排序;最简单的方法是将某个半数组复制到某处。这不是就地，但工作。

交换元件不工作的，因为它不保证该阵列的第一半的最大值小于在右半最小值：

{ 3 4 4 1 2 4 } 

交换I = 0，J = 3

{ 1 4 4 3 2 4 } 

交换I = 1，J = 5

{ 1 2 4 3 4 4 } 

通过在进一步交换的结果修正此O（N^2）气泡排序。