?前言?：
演算法是一個程式員的內功，能很好的體現程式員的編程思維，通過學習和掌握常見的演算法，不僅能提高coding能力，還能更加容易在筆面試中脫穎而出，本專欄將記錄博主刷演算法題的程序，不定期的會更新一些優質的演算法題，如果對大家有幫助，別忘了三連支持喲！
目錄
?前言?：
?歸并排序的思想?
💎歸并排序的總思路💎
💎具體是如何歸并的呢？💎
?歸并排序的總代碼?
?歸并排序的時間復雜度的分析?
?歸并排序的思想?
💡：我們常見的歸并排序大都是用遞回寫就的，歸并排序是基于比較的排序，而歸并排序所有的交換都是在歸并階段完成的，所以要理解歸并排序，就要在把握歸并排序的總思路下，深挖掘歸并的具體操作！
相信通過上述內容，大家已經知道了如何學習歸并排序，那么接下來我來講解歸并的總思路，
💎歸并排序的總思路💎
🔑：大家應該都熟悉遞回的本質了，遞回其實就是一種將問題逐步簡化的方法，因此我們在寫遞回時一定要宏觀把握，把握住化簡問題的總思路，
歸并排序的總思路是我們想讓一個范圍內有序，我們只需要將這個范圍一分為二，先讓這個范圍內的左半部分有序，再讓這個范圍的右半部分有序，然后我們只需要把兩個有序的序列合并成整個序列全有序（歸并操作），我們只需要沿著這個總思路，將整個陣列不斷二分，不斷遞進，直到最后一次二分導致一個半區只有一個元素時停止，我們只需要通過回溯時不斷合并，最終就能讓整體有序，
💎具體是如何歸并的呢？💎
🔑：我們通過上述學習知道了我們在遞回回溯時進行歸并，而每次歸并前都已經保證了左半部分和右半部分均有序，在這個前提下問題就轉化成了如何將兩個有序的序列合并成一個整體并保證其有序，
那如何解決這個問題呢？
這個問題很簡單相信大家很快就能想到，我們知道合并出來的最小值必定在左右兩部分的最小值中產生，這樣我們就得到了最小值，我們再從左右兩半部分中去掉這個最小值，同理可得，第二小的數值必定在此時左右兩半部分中現存最小值中產生，以此類推我們就得到了，整體有序，當然因為要存放這個整體，所以我們需要開辟一個輔助陣列來儲存整體，
💡：聽到這里相信大家仍然有很多疑惑，畢竟光說不上代碼永遠是空架子，接下來我給出代碼，希望大家能認真分析代碼，并自己手敲多練幾次，很多疑惑在練習中就能解決，
?歸并排序的總代碼?
#include<stdio.h>
#include<stdlib.h>
void print_arr(int arr[], int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
}
void merge(int arr[], int L, int M, int R)
{
int p1 = L;
int p2 = M + 1;
int i = 0;
int* help = (int*)malloc((R + 1 - L) * sizeof(int));
while (p1 <= M && p2 <= R)
{
//比較左右兩部分 小的放入（現存整體最小值放入）
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];//創建一個輔助陣列
}
while (p1 <= M)
{
help[i++] = arr[p1++];
}
while (p2 <= R)
{
help[i++] = arr[p2++];
}
for (int i = 0; i < (R + 1 - L); i++)
{
arr[L + i] = help[i];
}
free(help);
help= NULL;
}
void process(int arr[], int L, int R)
{
if (L == R)
{
return;
}
int mid = L + ((R - L) >> 1);
process(arr, L, mid);//遞回讓左邊有序
process(arr, mid + 1, R);//遞回讓右邊有序
merge(arr,L,mid,R);//歸并操作
}
void mergeSort(int arr[], int sz)
{
process(arr,0,sz-1);
}
int main()
{
//這是一次測驗
int arr[10] = { 2,7,5,1,3,9,10,2,8,4 };
int sz = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, sz);//歸并排序
print_arr(arr, sz);
return 0;
}?歸并排序的時間復雜度的分析?
以上代碼，還可做優化在此僅作參考，若有更好的演算法，還望能夠私信告知，多謝各位，
由于本人水平十分有限，若有錯誤請即使告知！如果有幫助別忘了，萬分感謝，
點贊👍 收藏? 關注?
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/304517.html
標籤：java
下一篇：6000字總結動態記憶體管理