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