感謝Will同學(xué)指出的問題，我仔細(xì)思考后發(fā)現(xiàn)不只是代碼的問題，算法思想上就有錯了，我沒有在每次交換后保持兩個子序列的有序性，這樣就無法保證i和j指向正確的位置，而如果想要保持子序列有序，雖然可以引入一個臨時變量并通過交換實(shí)現(xiàn)，但算法復(fù)雜度就不是線性的了，所以結(jié)論是暫時沒有可以簡單實(shí)現(xiàn)的線性時間原地歸并。事實(shí)上，有一些paper描述了很多線性時間原地歸并的算法，但是復(fù)雜度都相當(dāng)高，感興趣的朋友可以自行g(shù)oogle。
為了不誤導(dǎo)大家，把題目改了，至于下面的筆試題，希望牛人給予解答啊，謝謝。
---------------------------------------原文分割線-----------------------------------------------
快要找工作了，現(xiàn)在在回顧一些算法和數(shù)據(jù)結(jié)構(gòu)的知識，除了看書，爭取每天挑一兩道有趣的題目來練練手。本人沒參加過ACM，解算法題的實(shí)力也相當(dāng)菜鳥，但本人對于任何能夠鍛煉思維能力的題目都相當(dāng)熱衷，不怕做不出來，就怕不敢做，做多了，思考多了，總是有幫助的，呵呵，所以希望各位看到我的文章中有錯誤的地方請不吝賜教，在下感激不盡。
Share is happiness.
今天的題目是在網(wǎng)上看到的，ms是一道baidu的筆試題：
給定一個序列a[0...n-1]和一整數(shù)m，滿足0<=m<=n-1，且a[0...m-1]和a[m...n-1]都為有序子序列，要求設(shè)計一個時間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)的算法，實(shí)現(xiàn)將這兩個子序列合并為一個完整的有序序列a[0...n-1]。
題意很簡單，就是要設(shè)計一個線性時間的原地歸并算法，我給出的思路：
從左到右遍歷數(shù)組，將當(dāng)前未遍歷元素中的最小值置換到它所應(yīng)在的位置。這個簡單的描述有點(diǎn)像選擇排序，但選擇排序O(N^2)的復(fù)雜度明顯是不允許的，這里，利用兩個子序列已有序的性質(zhì)，我們可以設(shè)計更高效的O(N)算法：首先易知未遍歷元素中的最小值必定是兩個子序列的最小值中的更小者，將改值交換到它應(yīng)在的位置；利用有序性，可以在遍歷過程中分別記錄兩個子序列的當(dāng)前最小元素的位置，這樣就省去了選擇排序中每次都要遍歷剩余序列找出最小值的開銷，每次遍歷內(nèi)部為常數(shù)次的比較和交換操作，所以整個算法的時間復(fù)雜度為O(N)。