??前言
? 什么是歸并？通過歸并排序就能讓數(shù)據(jù)有序？分治法是怎么在歸并排序上應(yīng)用的？本文將對歸并排序進(jìn)行細(xì)致入微的講解，庖丁解牛般讓你徹底明白歸并排序！
???歸并排序的思想
??基本思想
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide andConquer）的一個(gè)非常典型的應(yīng)用。
將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
??歸并的思想實(shí)現(xiàn)
? 將兩個(gè)有序數(shù)組合并成一個(gè)有序數(shù)組的操作。在歸并排序中，通過不斷地將數(shù)組分成兩半，分別對每一半進(jìn)行排序，然后將排好序的兩個(gè)子數(shù)組合并成一個(gè)有序數(shù)組，最終得到整個(gè)數(shù)組有序的結(jié)果。
??分治法
? 分治法在歸并排序中的應(yīng)用是將問題分解成更小的子問題，然后分別解決這些子問題，最后將子問題的解合并起來得到原問題的解。具體來說，歸并排序的分治法應(yīng)用如下：
- 分解：將待排序的數(shù)組分成兩個(gè)子數(shù)組，分別為左子數(shù)組和右子數(shù)組。
- 解決：遞歸地對左子數(shù)組和右子數(shù)組進(jìn)行歸并排序。
- 合并：將排好序的左子數(shù)組和右子數(shù)組合并成一個(gè)有序數(shù)組。
???歸并排序的實(shí)現(xiàn)
??核心操作步驟
靜圖全步驟概覽：
動(dòng)圖一步步的邏輯實(shí)現(xiàn)：
??遞歸版歸并實(shí)現(xiàn)
//歸并
void _MergeSort(int* a, int* tmp, int begin, int end)
{
if (end <= begin)
{
return;
}
int mid = (begin + end) / 2;
_MergeSort(a, tmp, begin, mid);
_MergeSort(a, tmp, mid + 1, end);
// a->[begin, mid][mid+1, end]->tmp
//歸并
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int index = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
//歸并(遞歸版)
void MergeSort(int* a, int n)
{
int* tmp = malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
_MergeSort(a, tmp, 0, n - 1);
free(tmp);
}
? 歸并需要開一個(gè)同樣大的tmp數(shù)組來存放數(shù)據(jù),相當(dāng)于是拿空間來換時(shí)間了.
?代碼實(shí)現(xiàn)詳解:
- 首先，將整個(gè)序列分為兩部分，分別遞歸調(diào)用_MergeSort函數(shù)對左右兩部分進(jìn)行排序。
- 在_MergeSort函數(shù)中，首先判斷遞歸終止條件，如果end小于等于begin，則表示當(dāng)前子序列只有一個(gè)元素或者為空，無需排序，直接返回。
- 然后，計(jì)算中間位置mid，并分別遞歸調(diào)用_MergeSort函數(shù)對左右兩部分進(jìn)行排序。
- 接下來，進(jìn)行歸并操作。首先，設(shè)置四個(gè)指針begin1、end1、begin2、end2分別指向左右兩部分的起始和結(jié)束位置，以及一個(gè)指針index指向當(dāng)前歸并結(jié)果的位置。
- 然后，使用兩個(gè)循環(huán)比較左右兩部分的元素大小，并將較小的元素放入tmp數(shù)組中，同時(shí)移動(dòng)相應(yīng)的指針。
- 最后，將剩余的元素復(fù)制到tmp數(shù)組中。
- 最后，將tmp數(shù)組中的元素復(fù)制回原數(shù)組a中，完成歸并排序。
??非遞歸版歸并實(shí)現(xiàn)
? 非遞歸版是在遞歸上進(jìn)行了修改,將其遞歸改為了循環(huán)。
//歸并(非遞歸版)
void _MergeSortNotR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
int gap = 1;
while (gap < n)
{
for (int i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (begin2 >= n)
{
break;
}
if (end2 >= n)
{
end2 = n - 1;
}
int index = i;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[index++] = a[begin1++];
}
else
{
tmp[index++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = a[begin2++];
}
memcpy(a+i, tmp+i, (end2-i+1) * sizeof(int));
}
gap *= 2;
}
free(tmp);
}
?代碼實(shí)現(xiàn)詳解:
-
分配一個(gè)臨時(shí)數(shù)組tmp，用于存儲(chǔ)歸并結(jié)果。
-
設(shè)置一個(gè)變量gap為1，表示歸并的間隔大小。
-
接下來，循環(huán)執(zhí)行以下操作，直到gap大于等于n：
-
- 遍歷整個(gè)數(shù)組，每次取兩個(gè)相鄰的子序列進(jìn)行歸并。
- 計(jì)算左右兩個(gè)子序列的起始和結(jié)束位置。
- 判斷右子序列的結(jié)束位置是否超過了數(shù)組的長度，如果超過，則將結(jié)束位置設(shè)置為數(shù)組的最后一個(gè)元素的下標(biāo)。
- 使用兩個(gè)指針begin1和begin2分別指向左右兩個(gè)子序列的起始位置，使用指針end1和end2分別指向左右兩個(gè)子序列的結(jié)束位置。
- 使用一個(gè)指針index指向當(dāng)前歸并結(jié)果的位置。
- 使用一個(gè)循環(huán)，比較左右兩個(gè)子序列的元素大小，并將較小的元素放入臨時(shí)數(shù)組tmp中，同時(shí)移動(dòng)相應(yīng)的指針。
- 如果左子序列還有剩余元素，則將剩余元素復(fù)制到tmp數(shù)組中。
- 如果右子序列還有剩余元素，則將剩余元素復(fù)制到tmp數(shù)組中。
- 將tmp數(shù)組中的元素復(fù)制回原數(shù)組a中。
- 將gap乘以2，進(jìn)行下一輪歸并。
-
最后，釋放臨時(shí)數(shù)組tmp的內(nèi)存空間。
???歸并排序特性總結(jié)
- 穩(wěn)定性：歸并排序是一種穩(wěn)定的排序算法，即相等元素的相對順序在排序后不會(huì)改變。
- 時(shí)間復(fù)雜度：歸并排序的時(shí)間復(fù)雜度是O(nlogn)，其中n是待排序序列的長度。這是由于歸并排序的核心操作是將序列分成兩個(gè)子序列，然后分別進(jìn)行排序，再將排序好的子序列合并，而分割和合并操作都需要O(logn)的時(shí)間，所以總的時(shí)間復(fù)雜度是O(nlogn)。
- 空間復(fù)雜度：歸并排序的空間復(fù)雜度是O(n)，其中n是待排序序列的長度。這是由于歸并排序需要一個(gè)與待排序序列相同大小的額外空間來存儲(chǔ)臨時(shí)的合并結(jié)果。
- 非原地排序：歸并排序不是原地排序算法，即它需要額外的空間來存儲(chǔ)臨時(shí)的合并結(jié)果。這是因?yàn)樵诤喜⒉僮髦?，需要同時(shí)訪問兩個(gè)子序列的元素，并將它們按照順序合并到一個(gè)新的序列中。
- 遞歸實(shí)現(xiàn)：歸并排序通常使用遞歸的方式來實(shí)現(xiàn)，即將待排序序列不斷分割成更小的子序列，直到子序列的長度為1，然后再將這些子序列按照順序合并成一個(gè)有序的序列。遞歸實(shí)現(xiàn)的歸并排序代碼簡潔易懂，但是由于遞歸調(diào)用的開銷比較大，所以在實(shí)際應(yīng)用中可能會(huì)使用迭代的方式來實(shí)現(xiàn)歸并排序。
- 適用性：歸并排序適用于各種數(shù)據(jù)規(guī)模的排序，而且對于大規(guī)模數(shù)據(jù)的排序效果較好。它的時(shí)間復(fù)雜度穩(wěn)定在O(nlogn)，不會(huì)因?yàn)閿?shù)據(jù)規(guī)模的增大而導(dǎo)致時(shí)間復(fù)雜度的增加。此外，歸并排序還適用于外部排序，即對于無法一次性加載到內(nèi)存的大規(guī)模數(shù)據(jù)進(jìn)行排序。
???全篇總結(jié)
? 經(jīng)過對歸并排序的思想，特性，代碼實(shí)現(xiàn)這些細(xì)致入微的講解，相信聰明的你肯定已經(jīng)學(xué)會(huì)了叭????！文章來源：http://www.zghlxwxcb.cn/news/detail-715470.html
?? 好了，由于篇幅有限,本章只是對歸并進(jìn)行了深度解刨，后序會(huì)出更多的排序算法哦！
看到這里希望給博主留個(gè):??點(diǎn)贊??收藏??關(guān)注！
你們的點(diǎn)贊就是博主更新最大的動(dòng)力！
有問題可以評論或者私信呢秒回哦！
文章來源地址http://www.zghlxwxcb.cn/news/detail-715470.html
到了這里，關(guān)于【排序算法】 歸并排序詳解！分治思想！的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
