金華建站價格深圳電子網(wǎng)絡(luò)推廣查詢
本文旨在講解歸并排序的實現(xiàn)（遞歸及非遞歸）搬好小板凳，干貨來了！
?
前序：
在介紹歸并排序之前，需要給大家介紹的是什么是歸并，歸并操作，也叫歸并算法，指的是將兩個順序序列合并成一個順序序列的方法，相信不少小伙伴之前都做過合并兩個有序鏈表或者兩個有序數(shù)組的例題，歸并就是將兩個數(shù)組或鏈表合并成一個鏈表或數(shù)組，還得保證與其原來的順序相同！那么歸并排序就是用到了歸并這個思想，將一組元素完成排序的算法！
歸并排序的介紹?
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
歸并排序的時間復(fù)雜度和空間復(fù)雜度
時間復(fù)雜度：O（N*logN），因為其是一種二叉樹結(jié)構(gòu)，其高度為logN,每層需要排序的個數(shù)都是N個，所以其時間復(fù)雜度為O（N*logN）。
空間復(fù)雜度：因為創(chuàng)建了一個新的數(shù)組，所以其空間復(fù)雜度為O（N）；
歸并排序的思想與思路
歸并排序就是本質(zhì)上是分治的方法來實現(xiàn)的，是將一組數(shù)據(jù)分割成若干組有序數(shù)組，然后對這若干個有序數(shù)組兩兩進行歸并即可得到我們想要的排序！
歸并排序的思路圖
歸并排序的動態(tài)圖展示
歸并排序的大致實現(xiàn)思路?
歸并排序其實現(xiàn)的思路其實很簡單，就是將一組數(shù)據(jù)分割，分割到若干組有序數(shù)組，然后兩兩進行歸并，那么如何保證分割的數(shù)組為有序數(shù)組呢，這其實很簡單，當(dāng)分割到數(shù)組中只有一個元素的時候，那么該數(shù)組就是有序的數(shù)組了！然后進行歸并拷貝到原數(shù)組上即可！
歸并排序的代碼實現(xiàn)
（C版本遞歸）
void _MergeSort(int* a, int left, int right, int* tem)
{//當(dāng)再次需要調(diào)用的區(qū)間不存在時，返回即可！if (left == right) //很顯然，left不會大于right，保險起見，加上大于條件沒有影響！{return;}//每次取出中間坐標(biāo)，用于下次的左半邊的遞歸，右半邊遞歸同理！int mid = (left + right) / 2;_MergeSort(a, left, mid, tem);_MergeSort(a, mid + 1, right, tem);//到此，分割區(qū)間已經(jīng)結(jié)束，每組區(qū)間都能保證時有序的了！下一步就開始進行歸并！int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int i = left; //i用于對tem數(shù)組的下標(biāo)進行表示！//下面開始歸并兩個有序數(shù)組，當(dāng)兩個有序數(shù)組其中一個遍歷完成就退出循環(huán)！while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tem[i++] = a[begin1++];}else{tem[i++] = a[begin2++];}}while (begin1 <= end1){tem[i++] = a[begin1++];}while (begin2 <= end2){tem[i++] = a[begin2++];}//歸并結(jié)束后，將tem數(shù)組中的數(shù)據(jù)，拷貝到元素組中相應(yīng)的位置即可！memcpy(a + left, tem + left, sizeof(int)*(right - left + 1));//個數(shù)為右邊界減去左邊加1，因為為閉區(qū)間！//至此，歸并結(jié)束，拷貝結(jié)束!
}
void MergeSort(int* a, int n)
{//在堆上申請開辟一個tem數(shù)組，用來最后拷貝到原數(shù)組中！int* tem = (int *)malloc(sizeof(int) * n);//因為存在遞歸的調(diào)用，所以再創(chuàng)建一個函數(shù)，若仍在此函數(shù)上重復(fù)調(diào)用時，則會重復(fù)開辟新的空間，可能導(dǎo)致空間不足！_MergeSort(a, 0, n - 1, tem);//用完之后釋放到tem數(shù)組！free(tem);
}需要注意的是：當(dāng)進行遞歸歸并排序的時候，需要注意返回的條件，當(dāng)區(qū)間不存在或者區(qū)間內(nèi)部只有一個元素的時候就可以返回了！還需要注意的是，因為要進行拷貝，不能在原數(shù)組上直接拷貝，所以需要創(chuàng)建一個新的數(shù)組用來存儲歸并后的元素的位置，最后歸并結(jié)束重新拷貝到原數(shù)組中即可！
（C版本非遞歸）
分段拷貝
// 歸并排序非遞歸實現(xiàn)//思路如下：要想實現(xiàn)歸并排序的非遞歸，那么需要注意分組，從每組一個元素開始，因為當(dāng)只有一個元素的時候，默認是有序的，然后
//進行歸并拷貝即可，每組一個元素遍歷結(jié)束之后，進行每組兩個，依次進行每組2倍個元素進行歸并！，當(dāng)每組的元素為所有元素的一半或大于一半，
//即可完成排序，需要特別注意的是，進行非遞歸歸并排序的時候，需要注意區(qū)間的取值，在此有兩個拷貝方式，一種是整體拷貝，一組是歸并一段拷貝一段！//進行非遞歸實現(xiàn)歸并的時候也需要創(chuàng)建一個新的數(shù)組，不能在原數(shù)組上進行對數(shù)據(jù)的改變，因為可能會造成數(shù)據(jù)的覆蓋，導(dǎo)致數(shù)據(jù)不能完成排序！
//創(chuàng)建一個新數(shù)組，然后讓每組元素為一個依次遞增二倍，進行歸并拷貝，直至每組的元素個數(shù)大于數(shù)組個數(shù)結(jié)束歸并即可完成排序！//下面先來進行分段拷貝！
//void MergeSortNonR(int* a,int n)
//{
// //注意：gap代表的是每組歸并時的元素的個數(shù)！
// int gap = 1;
// int* tem = (int*)malloc(sizeof(int) * n);
// while (gap < n) //當(dāng)gap大于n時結(jié)束循環(huán)即可完成！
// {
// int j = 0;
// //每組為一個的進行遍歷！
// for (int i = 0; i <n ; i+=2*gap)
// {
//
// //每組個數(shù)為1的進行歸并排序！
// //區(qū)間范圍如下!
// int begin1 = i, end1 = i + gap - 1;
// int begin2 = i + gap, end2 = i + 2 * gap - 1;
//
// //當(dāng)end1>n,begin2>n時，不需要進行歸并！
// if (end1 >= n||begin2>=n)
// {
// break;
// }
//
// //對end2邊界進行修改！
// if (end2 >= n)
// {
// end2 = n-1;
// }
//
// //開始進行歸并拷貝！
// while (begin1 <= end1 && begin2 <= end2)
// {
// if (a[begin1] < a[begin2])
// {
// tem[j++] = a[begin1++];
// }
// else
// {
// tem[j++] = a[begin2++];
// }
// }
// while (begin1 <= end1)
// {
// tem[j++] = a[begin1++];
// }
// while (begin2 <= end2)
// {
// tem[j++] = a[begin2++];
// }
//
// //注意：需要注意的是：當(dāng)求元素的個數(shù)時，應(yīng)該用end2-i,不能減去begin1，因為begin1每次都會改變，記錄的不再是數(shù)組開始拷貝的地方！
// memcpy(a + i, tem + i, sizeof(int) * (end2 - i + 1));
// }
// gap *= 2;
// }
// free(tem);
//}整體拷貝
//整段拷貝！
void MergeSortNonR(int* a, int n)
{//注意：gap代表的是每組歸并時的元素的個數(shù)！int gap = 1;int* tem = (int*)malloc(sizeof(int) * n);while (gap < n) //當(dāng)gap大于n時結(jié)束循環(huán)即可完成！{//j的聲明必須寫在for循環(huán)的外面，因為若寫到for循環(huán)內(nèi)部時，在每組循環(huán)都會將原來歸并好的數(shù)據(jù)放到前面的那些位置//導(dǎo)致以及歸并好的又被覆蓋，導(dǎo)致排序失敗！（每組的歸并都放在前兩組內(nèi)部，導(dǎo)致不能將全部歸并結(jié)束，！）int j = 0;//每組為一個的進行遍歷！for (int i = 0; i < n; i += 2 * gap){//每組個數(shù)為1的進行歸并排序！//區(qū)間范圍如下!int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//當(dāng)end1>n,begin2>n時，不需要進行歸并！if (end1 >= n){end1 = n - 1;//將第二塊區(qū)間設(shè)置為不存在的區(qū)間！如果設(shè)置為n-1那么會造成對最后一個數(shù)據(jù)的重復(fù)使用，拷貝，導(dǎo)致排序錯誤！begin2 = n;end2 = n - 1;}else if (begin2 >= n){begin2 = n;end2 = n - 1;}else if(end2>=n){end2 = n - 1;}//開始進行歸并拷貝！while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){tem[j++] = a[begin1++];}else{tem[j++] = a[begin2++];}}while (begin1 <= end1){tem[j++] = a[begin1++];}while (begin2 <= end2){tem[j++] = a[begin2++];}//注意：需要注意的是：進行整段拷貝的時候，不需要再從a+begin1的位置開始拷貝啦，直接將所有tem中的元素拷貝到原數(shù)組即可！}memcpy(a, tem, sizeof(int) * n);gap *= 2;}free(tem);
}需要注意的是：非遞歸的歸并排序，整體拷貝和分段拷貝大致思路是一樣的，只是最后進行memcpy的起始位置和個數(shù)有所不同！相關(guān)細節(jié)與思路都在源代碼上加有注釋標(biāo)明，需要注意的是：當(dāng)進行整體拷貝的時候，用于標(biāo)記tem數(shù)組的j的坐標(biāo)的定義一定要在for循環(huán)外部定義賦值，若在內(nèi)部賦值定義，則每進行一次都會覆蓋原來已經(jīng)歸并好的數(shù)據(jù)上面，導(dǎo)致歸并排序不能正確進行！
今日的歸并排序分享到此結(jié)束，歡迎大家積極評論支持。若有不足及補充，及時提出，必將改正！?
