美團(tuán)一面：兩個有序的數(shù)組，如何高效合并成一個有序數(shù)組？

在說這個題目之前先來說說一個排序算法 “歸并算法”

歸并算法采取思想是分治思想，分治思想簡單說就是分而治之，將一個大問題分解為小問題，將小問題解答后合并為大問題的答案。

乍一看跟遞歸思想很像，確實如此，分治思想一般就是使用遞歸來實現(xiàn)的。但是需要注意的是：遞歸是代碼實現(xiàn)的方式，分治屬于理論。另外，數(shù)據(jù)結(jié)構(gòu)和算法系列面試題和答案全部整理好了，微信搜索互聯(lián)網(wǎng)架構(gòu)師，在后臺發(fā)送：2T，可以在線閱讀。

接下來看一副圖理解下：

說完它的思想：我們再來分析下時間復(fù)雜度。歸并算法采用的是完全二叉樹的形式。所以可以由完全二叉樹的深度可以得知，整個歸并排序需要進(jìn)行l(wèi)og2n次。

然后每一次需要消耗O{n}時間。所以總的時間復(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的箭頭后移。

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/