在說這個題目之前先來說說一個排序演算法 “歸并演算法”
歸并演算法采取思想是分治思想，分治思想簡單說就是分而治之，將一個大問題分解為小問題，將小問題解答后合并為大問題的答案，
乍一看跟遞回思想很像，確實如此，分治思想一般就是使用遞回來實作的，但是需要注意的是：遞回是代碼實作的方式，分治屬于理論，
接下來看一副圖理解下：
說完它的思想：我們再來分析下時間復雜度，歸并演算法采用的是完全二叉樹的形式，所以可以由完全二叉樹的深度可以得知，整個歸并排序需要進行log2n次，
然后每一次需要消耗O{n}時間，所以總的時間復雜度為o{nlog2n}，歸并排序是一種比較占用記憶體，但是效率高且穩定的演算法
貼上代碼：
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 < newArr.Length - 1; 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;
//進行比較，注意這里++是后執行的，先取出來陣列中的值然后++
while (start1 <= end1 && start2 <= end2)
result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
//將每個分組剩余的進行復制
while (start1 <= end1)
result[k++] = arr[start1++];
//將每個分組剩余的進行復制
while (start2 <= end2)
result[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = result[k];
return result;
}
說完了歸并演算法回到題目上來 首先分析下 題目給定的是兩個已經排好序的陣列合并，關鍵字“合并”，“兩個”，正好符合我們的歸并演算法，并且已經分類好了，只需要去合并就可以了，
來看下幾張圖，
藍色的箭頭表示最終選擇的位置，而紅色的箭頭表示兩個陣列當前要比較的元素，比如當前是2與1比較，1比2小，所以1放到藍色的箭頭中，藍色的箭頭后移，1的箭頭后移，
然后2與4比較，2比4小那么2到藍色的箭頭中，藍色箭頭后移，2后移，繼續比較.......
歸并思路就是這樣了，最后唯一需要注意的是那個先比較完的話，那么剩下的直接不需要比較，把后面的直接移上去就可以了，這個需要提前判定一下，
貼上代碼：
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 < newArr.Length - 1; 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 < arr1.Length && j < arr2.Length)
{
if (arr1[i] < arr2[j])
{
newArr[k] = arr1[i];
i++;
k++;
}
else
{
newArr[k] = arr2[j];
j++;
k++;
}
}
while (i < arr1.Length)
newArr[k++] = arr1[i++];
while (j < arr2.Length)
newArr[j++] = arr2[j++];
return newArr;
}
最后感謝一下大佬提供的思路：https://blog.csdn.net/k_koris/article/details/80508543
原文鏈接：https://blog.csdn.net/weixin_40097554/article/details/108656165/
著作權宣告：本文為CSDN博主「貂蟬要睡覺」的原創文章，遵循CC 4.0 BY-SA著作權協議，轉載請附上原文出處鏈接及本宣告，
近期熱文推薦：
1.1,000+ 道 Java面試題及答案整理(2021最新版)
2.別在再滿屏的 if/ else 了，試試策略模式，真香！！
3.臥槽！Java 中的 xx ≠ null 是什么新語法？
4.Spring Boot 2.5 重磅發布，黑暗模式太炸了！
5.《Java開發手冊（嵩山版）》最新發布，速速下載！
覺得不錯，別忘了隨手點贊+轉發哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/320855.html
標籤：其他