本文共 1771 字，大约阅读时间需要 5 分钟。

归并排序是一种稳定快速地排序方法，该算法采用分治法的一个应用。也许这个名字刚听起来不是很好听，我一直将他说成是并归排序哈哈。

为什么会叫归并排序呢？不知道大家有没有这个疑问？

归并排序的整体思路就是先归后并，归是递归，将数组分为两部分，然后将左右两部分再分别递归分配咯，并就是合并，把分开的各个数组依次合并，最终完成一个无序数组的排序啦。

来我们再看看归并排序的基本步骤：

1.首先将数组分为两两一组

2.相邻进行比较合并。

举例才是王道：

请看

{2,8,6,9,4,7,3,9,1}

首先进行分组同时进行比较:

{2,6,8,9},{3,4,7,9},{1} 比较6次

{2,3,4,6,7,8,9，9}，{1} 比较7次

{1,2,3,4,6,7,8,9,9,} 比较一次

完毕！

代码才是王道了，下面是C++的案例：

/*实际上使用的是C，不是C++*/#include 
   
    #include 
    
     #include 
     
      using namespace std;void Merge(int sourceArr[],int tempArr[],int startIndex,int midIndex,int endIndex){    //设置前一个数组的首元素i，后一个数组的首元素j，k为拷贝原来大小的新数组的首元素    int i = startIndex,j = midIndex+1,k = startIndex;    //当两个数组元素都不未读取完成    while(i!=midIndex+1 &&j!=endIndex+1)    {        if(sourceArr[i] > sourceArr[j])            tempArr[k++] = sourceArr[j++];        else            tempArr[k++] = sourceArr[i++];    }    //当j数组元素读取完成，i数组剩余元素直接添加到后面    while(i != midIndex +1)        tempArr[k++] = sourceArr[i++];    //当i数组元素读取完成，j数组剩余元素直接添加到后面    while(j != endIndex +1)        tempArr[k++] = sourceArr[j++];    //将排好导入的新数组里的内容复制到原来的数组    for(i=startIndex;i<=endIndex;i++)        sourceArr[i] = tempArr[i];}void MergeSort(int sourceArr[], int tempArr[], int startIndex,int endIndex){    int midIndex;    //判断是否递归    if(startIndex < endIndex)    {        //midIndex是前后两个相邻的数组的前一个数组最后的一个元素        midIndex= (startIndex + endIndex)/2;        //递归前半部分        MergeSort(sourceArr,tempArr,startIndex,midIndex);        //递归后半部分        MergeSort(sourceArr,tempArr,midIndex+1,endIndex);        //归并的合并阶段啦        Merge(sourceArr,tempArr,startIndex,midIndex,endIndex);    }}int main(){    int a[10] = {2,3,6,5,9,10,20,3,12,6};    int i ,b[10];    MergeSort(a,b,0,9);    for(i=0;i<10;i++)        cout<
      
       <<" ";}
      
     
    
   

转载地址：https://islet.blog.csdn.net/article/details/75472966 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！