美團(tuán)一面：兩個有序的數(shù)組，如何高效合并成一個有序數(shù)組？
點(diǎn)擊關(guān)注公眾號，Java干貨及時(shí)送達(dá)
在說這個題目之前先來說說一個排序算法 “歸并算法”
歸并算法采取思想是分治思想，分治思想簡單說就是分而治之，將一個大問題分解為小問題，將小問題解答后合并為大問題的答案。
乍一看跟遞歸思想很像，確實(shí)如此，分治思想一般就是使用遞歸來實(shí)現(xiàn)的。但是需要注意的是：遞歸是代碼實(shí)現(xiàn)的方式，分治屬于理論。另外，數(shù)據(jù)結(jié)構(gòu)和算法系列面試題和答案全部整理好了，微信搜索Java技術(shù)棧，在后臺發(fā)送：面試，可以在線閱讀。
接下來看一副圖理解下：
說完它的思想：我們再來分析下時(shí)間復(fù)雜度。歸并算法采用的是完全二叉樹的形式。所以可以由完全二叉樹的深度可以得知，整個歸并排序需要進(jìn)行l(wèi)og2n次。
然后每一次需要消耗O{n}時(shí)間。所以總的時(shí)間復(fù)雜度為o{nlog2n}。歸并排序是一種比較占用內(nèi)存，但是效率高且穩(wěn)定的算法。
static?void?Main(string[]?args)?{
????int[]?arr?=?new?int[]?{?14,12,15,13,11,16?,10};
????int[]?newArr?=?Sort(arr,?new?int[7],?0,?arr.Length?-?1);
????for?(int?i?=?0;?i?????{
????????Console.WriteLine(newArr[i]);
????}
????Console.ReadKey();
}
public?static?int[]?Sort(int[]?arr,?int[]?result,?int?start,?int?end)
{
????if?(start?>=?end)
????????return?null;
????int?len?=?end?-?start,?mid?=?(len?>>?1)?+?start;
????int?start1?=?start,?end1?=?mid;
????int?start2?=?mid?+?1,?end2?=?end;
????Sort(arr,?result,?start1,?end1);
????Sort(arr,?result,?start2,?end2);
????int?k?=?start;
????//進(jìn)行比較。注意這里++是后執(zhí)行的，先取出來數(shù)組中的值然后++
????while?(start1?<=?end1?&&?start2?<=?end2)
????????result[k++]?=?arr[start1]?????//將每個分組剩余的進(jìn)行復(fù)制
????while?(start1?<=?end1)?
????????result[k++]?=?arr[start1++];
????//將每個分組剩余的進(jìn)行復(fù)制
????while?(start2?<=?end2)
????????result[k++]?=?arr[start2++];?
????for?(k?=?start;?k?<=?end;?k++)
????????arr[k]?=?result[k];
????return?result;
}
來看下幾張圖。
藍(lán)色的箭頭表示最終選擇的位置，而紅色的箭頭表示兩個數(shù)組當(dāng)前要比較的元素，比如當(dāng)前是2與1比較，1比2小，所以1放到藍(lán)色的箭頭中，藍(lán)色的箭頭后移，1的箭頭后移。
然后2與4比較，2比4小那么2到藍(lán)色的箭頭中，藍(lán)色箭頭后移，2后移，繼續(xù)比較.......
歸并思路就是這樣了，最后唯一需要注意的是那個先比較完的話，那么剩下的直接不需要比較，把后面的直接移上去就可以了，這個需要提前判定一下。另外，數(shù)據(jù)結(jié)構(gòu)系列面試題和答案全部整理好了，微信搜索Java技術(shù)棧，在后臺發(fā)送：面試，可以在線閱讀。
static?void?Main(string[]?args)?{
????int[]?arr1?=?new?int[]?{?2,?3,?6,?8?};
????int[]?arr2?=?new?int[]?{?1,?4,?5,?7?};
????int[]?newArr?=?Sort(arr1,?arr2);
????for?(int?i?=?0;?i?????{
????????Console.WriteLine(newArr[i]);
????}
????Console.ReadKey();
}
public?static?int[]?Sort(int[]?arr1,int[]?arr2)
{
????int[]?newArr?=?new?int[arr1.Length?+?arr2.Length];
????int?i?=?0,?j?=?0,?k?=?0;
????while?(i?????{
????????if?(arr1[i]?????????{
????????????newArr[k]?=?arr1[i];
????????????i++;
????????????k++;
????????}
????????else
????????{
????????????newArr[k]?=?arr2[j];
????????????j++;
????????????k++;
????????}
????}
????while?(i?????????newArr[k++]?=?arr1[i++];
????while?(j?????????newArr[j++]?=?arr2[j++];
????return?newArr;
}
https://blog.csdn.net/k_koris/article/details/80508543
原文鏈接：https://blog.csdn.net/weixin_40097554/article/details/108656165/
版權(quán)聲明：本文為CSDN博主「貂蟬要睡覺」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
關(guān)注Java技術(shù)?？锤喔韶?/strong>
