通過一張圖了解什么是歸并排序
歸并排序?qū)嶋H上運(yùn)用了“分”和“治”的思想。怎樣理解“分”和“治”?
分:就是將一個(gè)大的數(shù)組逐漸分解為多個(gè)最大長度不超過2的數(shù)組腥光。
治:就是將這些小的數(shù)組依次合并排序,最后變成一個(gè)最大長度且有序的數(shù)組。
通過上面的歸并排序的圖解能夠很自然的想到要實(shí)現(xiàn)這個(gè)排序需要用到遞歸箱季。
首先講怎樣進(jìn)行"分"的操作:
void mergeSort(int *nums,int low,int high){
? int mid = (low+high)/2;
? if(low<high) {
? ? mergeSort(nums,low,mid);
? ? mergeSort(nums,mid+1,high);
? ? merge(nums,low,mid,high);//關(guān)于"治"的函數(shù)
? }
}
怎樣理解這段代碼?為了便于敘述,建立數(shù)組
7253
執(zhí)行上面的mergeSort函數(shù):
1.第一次調(diào)用該方法，初始數(shù)據(jù)為:
nums[4] = {7,2,5,3};
low =0;
high =3;
2.得到mid=(0+3)/2?= 1;由于low<high,所以有
mergeSort(nums,low,mid);//此時(shí)的low=0,mid=1。令此函數(shù)為A
mergeSort(nums,mid+1,high);//此時(shí)的miid+1=2,high=3兔辅。令此函數(shù)為B
merge(nums,low,mid,high);
3.執(zhí)行函數(shù)A,得到mid=(0+1)/2=0;由于low<high，所以有
mergeSort(nums,low,mid);//此時(shí)的low=0,mid=0萍程。令此函數(shù)為C
mergeSort(nums,mid+1,high);//此時(shí)的miid+1=1,high=1幢妄。令此函數(shù)為D
merge(nums,low,mid,high);//令此函數(shù)為E
4.執(zhí)行函數(shù)C,得到mid=(0+0)/2=0;由于low=high,所以函數(shù)C執(zhí)行完畢,返回到步驟3執(zhí)行函數(shù)D。
5.執(zhí)行函數(shù)D,得到mid=(1+1)/2=1;由于low=high,所以函數(shù)D執(zhí)行完畢,返回到步驟3執(zhí)行函數(shù)E(就到了"治"的階段)茫负。
6.執(zhí)行完步驟5,返回到步驟2執(zhí)行函數(shù)B蕉鸳。
7.執(zhí)行函數(shù)B,得到mid= (2+3)/2=2;由于low<high,所以有
mergeSort(nums,low,mid);// 此時(shí)的low=2,mid=2。令此函數(shù)為F
mergeSort(nums,mid+1,high);// 此時(shí)的miid+1=3,high=3。令此函數(shù)為G
merge(nums,low,mid,high);// 令此函數(shù)為H
8.執(zhí)行函數(shù)F,得到mid=(2+2)/2=2;由于low=high,所以函數(shù)F執(zhí)行完畢,返回到步驟7執(zhí)行函數(shù)G潮尝。
9.執(zhí)行函數(shù)G,得到mid=(3+3)/2=?3;由于low=high,所以函數(shù)G執(zhí)行完畢,返回步驟7執(zhí)行函數(shù)H("治")榕吼。
10.執(zhí)行完函數(shù)G,返回步驟2執(zhí)行函數(shù)merge。
再講怎樣進(jìn)行"治"的操作:
voidmerge(int*nums,intlow,intmid,int high) {?
intcopyArray[numsSize],flag,i,j,q;//numsSize為數(shù)組的長度
for(q =0;q
在執(zhí)行mergeSort函數(shù)的過程中,步驟5第一次執(zhí)行了merge函數(shù)勉失。這里著重對第一次執(zhí)行merge函數(shù)做一個(gè)詳細(xì)的解釋羹蚣。
初始數(shù)據(jù)
nums[4] = {7,2,5,3};
copyArray[4] = {7,2,5,3};
low =0;
mid =1;
high =1;
執(zhí)行循環(huán)
for(i = low,j = mid+1,flag=low;i<=mid && j<=high;) {
if(copyArray[j]
初始i、j乱凿、flag的值為
1i =0;2j =1;3flag =0;
因?yàn)?/p>
copyArray[0]>copyArray[1]//copyArray[0]=7? copyArray[1] = 2
所以有
nums[0] =2顽素；
flag++ =1；//右邊的值是flag++以后的值3j++ =2;
因?yàn)?/p>
high =1;
j =2;
不滿足循環(huán)條件
j<=high
故for循環(huán)終止徒蟆。接著執(zhí)行
while(i<=mid) {
nums[flag++] = copyArray[i++];
}
while(j<=high) {
nums[flag++] = copyArray[j++];
}
由于i<=mid,故執(zhí)行第一個(gè)while循環(huán)
nums[1] =7//copyArray[0] = 72i++ =1;
因?yàn)閕>mid,循環(huán)結(jié)束,merge函數(shù)調(diào)用結(jié)束胁出。此時(shí)的數(shù)組變成
nums[4] = {2,7,5,3};
第二次和第三次merge函數(shù)調(diào)用過程類似。
大家有興趣學(xué)習(xí)C/C++的可以關(guān)注微信公眾號：C語言愛好者
原文鏈接：https://www.cnblogs.com/jching/p/13291660.html
