分治法进行合并排序

合并排序

合并排序算法是用分治策略实现对n个元素进行排序的算法，其基本思想是：将待排序元素分成大小大致相同的两个子集合，分别对两个子集合进行排序，最终将排好序的子集合合并成要求的排好序的集合。合并排序算法可以递归地描述如下：

template<class Type>
void MergeSort(Type a[],int left,int right)
{
	//至少有两个元素
	if(left<right)
	{
		//取中点
		int i = (left + right) / 2;
		MergeSort(a,left,i);
		MergeSort(a,i+1,right);
		//合并到b数组
		Merge(a,b,left,i,right);
		//复制回到a数组
		Copy(a,b,left,right);
	}
}

事实上，算法MergeSort的递归过程只是将待排序集合一分为二，直至待排序集合只剩下一个元素为止，然后不断合并两个排好序的数组段。按此机制，可以先将数组a中相邻元素两两配对。用合并算法将他们排序，构成n/2组长度为2的排好序的子数组段，再将他们排序成长度为4的排好序的子数组段。如此继续下去，直至整个数组排好序。
但在这里我们会创建两个数组，不断将原数组从中间分开，然后放入两个数组中，将两个数组中的元素逐一进行比较放入原数组中。

代码

#include "iostream"
#include "time.h"
#include "stdlib.h"
using namespace std;
//合并函数
//q为我们的切分点
void Merge(int *_Array, int p, int q, int r) {// p:第0个;r:第n-1个数,q:第(r + p) / 2个数
    int len1 = q - p + 1;
    int len2 = r - q;
    int *L = new int[len1 + 1];//用动态数组储存左边的数
    int *R = new int[len2 + 1];//用动态数组储存右边的数
    for (int i = 0; i < len1; i++) {// 把Array数组左边的数放入L数组
        L[i] = _Array[p + i];
    }
    for (int j = 0; j < len2; j++) {// 把Array数组右边的数放入R数组
        R[j] = _Array[q + 1 + j];
    }
    L[len1]=R[len2]=INT_MAX;    //定义无穷大
    int i = 0, j = 0;
    for (int k = p; k <= r; k++) {
        if (L[i] < R[j]) {//小的放左边，大的放右边
            _Array[k] = L[i];
            i++;
        }
        else {
            _Array[k] = R[j];
            j++;
        }
    }
}
//  归并排序
void MergeSort(int _Array[], int p, int r) {
    if (p < r) {//p:第0个;r:第n-1个数。数组至少要有两个数据
        int q;
        q = (r + p) / 2;//拆分两组
        MergeSort(_Array , p , q);//拆分第0个到第 (r + p) / 2个 ，即拆分左半部分
        MergeSort(_Array , q+1 , r);//拆分第(r + p) / 2个到第r个 ，即拆分右半部分
        Merge(_Array , p , q , r);//调用合并函数，从第0个到第n-1个排好
    }
}
int main() {
    int n;
    cout << "输入产生的数组个数：";
    cin >> n;
    cout << endl;
    int *Array = new int[n];
    cout << "产生的随机数组为：";
    srand((unsigned)time(0));
    for (int i = 0; i < n; i++) {
        Array[i] =  (rand()%(100-0+1))+0;
        //cin>>;
        cout<<Array[i]<<"  ";
    }
    cout<<endl;
    MergeSort(Array,0,n-1);
    cout << "排序后的数组为：";
    for(int j  = 0;j<n;j++){
        cout<<Array[j]<<"  ";
    }
    return 0 ;
}