Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

绿色网站无广告
会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

归并排序算法(递归实现)

来源: flying0033 分享至:

归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

  将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

 

#ifndef MERGESORT_H
#define MERGESORT_H
#include <stdlib.h>
template<class T> inline void MergeSort(T *a,int len) //归并排序算法
{
	T *TR = (T *)malloc(sizeof(T) * len); //动态分配一个额外的存储空间
	MSort(a,TR,0,len-1); //分裂然后调用归并排序
	free(TR); //释放内存
}
template<class T> void Merge(T a[],T TR[],int low,int mid,int high) //归并排序
{
	int i = low;
	int j = mid + 1;
	int k = 0;
	while(i <= mid && j <= high)
	{
		if(a[i] < a[j])  //进行排序存入动态分配的数组中
			TR[k++] = a[i++];
		else
			TR[k++] = a[j++];
	}
	while(i <= mid) //如果前一半中还有未处理完的数据,按顺序移入动态分配的数组内
		TR[k++] = a[i++];
	while(j <= high) //如果后一半中还有未处理完的数据,按顺序移入动态分配的数组内
		TR[k++] = a[j++];
	for(int v = 0,i = low;i <= high;++v,++i) //将排序好的数据移回到原序列中
		a[i] = TR[v];
}
template<class T> void MSort(T a[],T temp[],int low,int high)
{
	int mid;
	if(low < high)
	{
		mid = (low + high) / 2; //进行分裂
		MSort(a,temp,low,mid); //将前一半继续分裂
		MSort(a,temp,mid + 1,high); //将后一半继续分裂
		Merge(a,temp,low,mid,high); //进行归并排序
	}
}
#endif //MERGESORT_H


 

#include "MergeSort.h"
#include <stdio.h>
int main()
{
	int a[] = {20,19,35,33,17,42,15,55,9,5,8,3,1};
	int len = sizeof(a) / sizeof(*a);
	MergeSort(a,len);
	printf("排序后的数组序列:\n");
	for(int i = 0;i < len;++i)
		printf("%d ",a[i]);
	printf("\n");
	return 0;
}


 


Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史