亲宝软件园·资讯

展开

C++ 归并排序(merge sort) C++ 归并排序(merge sort)案例详解

Joe_Somebody 人气:0
想了解C++ 归并排序(merge sort)案例详解的相关内容吗,Joe_Somebody在本文为您仔细讲解C++ 归并排序(merge sort)的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C++,归并排序,C++,merge,sort,下面大家一起来学习吧。

核心思想:“分”与“合”。

主体流程

先将一个序列分成很多个不能再分割的子序列,将各个子序列分别排序后再将子序列合并。其实就是重复两个步骤:【1】分【2】合并。
首先是第一个小问题,怎么分?
比如说一个序列:12 ,23,1,44,233,10,9,8。我们先分成两段:12 ,23,1,44 和 233,10,9,8,
发现还能再分成4段:12 ,23 和 1,44------233,10 和 9,8。
再分成8段:12--23--1--44 和233--10--9--8。
这时候开始把子序列进行排序合并,一个元素就是有序的。所以不用排序。
合并成2个一组排序得到:12,23----1,44---10,233---8,9。
再合并成4个一组排序得到:1,12,23,44---8,9,10,233。
最后合并得到最终结果:1,8,9,10,12,23,44,233。

下面是分段的代码,用递归实现。

void mergesort(int a[], int first, int last, int temp[])  
{  
    if (first < last)  
    {  
        int mid = (first + last) / 2;  
        mergesort(a, first, mid, temp);    //左边有序  
        mergesort(a, mid + 1, last, temp); //右边有序  
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并  
    }  
}

整体思路很清晰,还差一个小问题没解决,怎么合并?
现在问题就变成了怎么合并两个有序序列,思路是比较两个有序序列的第一个元素,谁小把谁放进最终序列的结尾,并把它从原来的队列里面删掉直到有个序列为空。
这时候另一个序列可能还有剩余的数据。没关系,因为他们本身是有序的,所以我们只要按顺序把他们添加到最终序列的尾部就好了。
这样两个有序序列就合并成一个有序序列了。
实现代码:

void mergearray(int a[], int first, int mid, int last, int temp[])  
{  
    int i = first, j = mid + 1;  
    int m = mid,   n = last;  
    int k = 0;  
      
    while (i <= m && j <= n)  
    {  
        if (a[i] <= a[j])  
            temp[k++] = a[i++];  
        else  
            temp[k++] = a[j++];  
    }  
  
    while (i <= m)  
        temp[k++] = a[i++];  
  
    while (j <= n)  
        temp[k++] = a[j++];
}

整体测试代码:

#include<iostream>  
#include<math.h>  
#include<stdlib.h>  
using namespace std;  
  
//将有二个有序数列a[first...mid]和a[mid...last]合并。  
void mergearray(int a[], int first, int mid, int last, int temp[])  
{  
    int i = first, j = mid + 1;  
    int m = mid,   n = last;  
    int k = 0;  
      
    while (i <= m && j <= n)  
    {  
        if (a[i] <= a[j])  
            temp[k++] = a[i++];  
        else  
            temp[k++] = a[j++];  
    }  
      
    while (i <= m)  
        temp[k++] = a[i++];  
      
    while (j <= n)  
        temp[k++] = a[j++];  
      
    for (i = 0; i < k; i++)  
        a[first + i] = temp[i];  
}  
void mergesort(int a[], int first, int last, int temp[])  
{  
    if (first < last)  
    {  
        int mid = (first + last) / 2;  
        mergesort(a, first, mid, temp);    //左边有序  
        mergesort(a, mid + 1, last, temp); //右边有序  
        mergearray(a, first, mid, last, temp); //再将二个有序数列合并  
    }  
}  
  
bool MergeSort(int a[], int n)  
{  
    int *p = new int[n];  
    if (p == NULL)  
        return false;  
    mergesort(a, 0, n - 1, p);  
    delete[] p;  //删除p临时数组
    return true;  
}  
  
int main()  
{  
    int i=0,temp=0;  
    int a[10]={0};  
    for(i=0;i<10;i++)  
{  
  
 a[i]=rand();  
 cout<<a[i]<<" ";  
  
}  
cout<<endl;  
MergeSort(a,10);  
for(i=0;i<10;i++) 
{  
    
    cout<<a[i]<<" ";  
  
}  
return 0;  
 }  

加载全部内容

相关教程
猜你喜欢
用户评论