數組排序與前半部分和後半部分排序

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）氣泡排序。