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

Question

可能重复:
关于数组中的就地合并

偶然发现了这个采访问题.给定一个大小为n的数组,其中第一个n/2被排序,而后半部分被排序.对整个阵列进行排序.现在我能想到的有点像插入排序,它的空间复杂度为O(1),但时间复杂度将超过O(n).O(n)到位解决方案是否可能解决此问题？

Answer 1

有两个(逻辑)指针 - 让我们称之为x和y.x指向前n/2个元素的第1个元素.y指向第二个n/2元素的第一个元素.

如果y处的元素小于x处的元素(让我们调用n(y)和n(x)),则将n(y)插入x并将x和y递增1.否则将x递增1并再次检查.一旦y命中'n',停止y并继续重复直到x == y.

例如

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)