归并排序的核心思想是使用分治的策略来进行排序。分治是将大问题分成一些小问题,小问题解决后在合并在一起。
我们来看一下这一排数据:9,4,5,1,2,7,3,8,6,0。算法流程大概就是以下图所示,将数组拆分,然后每一个小数组进行排序合并。
再看一下局部的两个小数组如何进行合并的,进行合并的两个红色数组里面的数已经是有序的,上图黑色框部分
申请一个临时数据,存放排序后的结果。
第一行:红色左边数组跟红色右边数组进行对比,小的就放入黑色的临时数组中
第二行:进行下一个数的对比,将小的放入黑色的临时数组中
第三行:再次进行下一个数的对比
红色右边数组已经对比完,将红色左边数组剩下的数按顺序放入到临时数组中
最后将黑色临时数组的数值拷贝回红色数组。
实现代码:
void sortmerge(int *pArray, int nLeft, int nRight) {
if(nLeft == nRight) return ;
int mid = (nLeft + nRight) / 2;
//拆分
sortmerge(pArray, nLeft, mid);
sortmerge(pArray, mid+1, nRight);
//排序合并
int x = nLeft;
mid = (nLeft + nRight) / 2;
int y = mid + 1;
int tmpArray[1000];
int ans = 0;
while(x <= mid && y <= nRight) { //数组合并进行对比
if(pArray[x] < pArray[y]) {
tmpArray[ans++] = pArray[x++];
}
else {
tmpArray[ans++] = pArray[y++];
}
}
while(x <= mid) { //左边数组还有剩下的数,存入临时数组
tmpArray[ans++] = pArray[x++];
}
while(y <= nRight) { //右边数组还有剩下的数,存入临时数组
tmpArray[ans++] = pArray[y++];
}
ans = 0;
for(int i=nLeft; i<=nRight; i++) { //将临时数组的数拷贝回原数组中
pArray[i] = tmpArray[ans++];
}
}
可关注公众号了解更多的面试技巧