数据结构与算法-归并排序

数据结构与算法-归并排序

    归并排序的核心思想是使用分治的策略来进行排序。分治是将大问题分成一些小问题，小问题解决后在合并在一起。

    我们来看一下这一排数据: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++];    }}

可关注公众号了解更多的面试技巧