// 归并排序.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
#define N 100
using namespace std;
typedef int DataType;
//合并data1[begin...mid]和data1[mid+1.end]到data2[begin,end]中,然后复制到data1[begin,end]中
void merge(DataType *data1,DataType *data2,int begin,int mid,int end)
{
int i,j,k;
for(i = begin,j=mid+1,k = begin;i<=mid&&j<=end;k++)
{
if(data1[i]<=data1[j])
data2[k] = data1[i++];
else
data2[k] = data1[j++];
}
if(i<=mid)
while(i<=mid)
data2[k++] = data1[i++];
else
while(j<=end)
data2[k++] = data1[j++];
for(i=begin;i<=end;i++)
data1[i] = data2[i];
}
//归并排序
void Msort(DataType *data1,DataType *data2,int begin,int end)
{
if(begin==end)
data1[begin] = data1[begin];
else
{
int mid = (begin+end)/2;
Msort(data1,data2,begin,mid);
Msort(data1,data2,mid+1,end);
merge(data1,data2,begin,mid,end);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
//data1存储原数据和排序后的数据,data2为辅助数据
DataType data1[N],data2[N];
int cases;
cout<<"请输入案例个数:";
cin>>cases;
while(cases--)
{
int n;
cout<<"请输入元素个数:";
cin>>n;
int i;
cout<<"请输入待排序元素:"<<endl;
for(i=1;i<=n;i++)
cin>>data1[i];
cout<<"归并排序前:"<<endl;
for(i=1;i<=n;i++)
cout<<data1[i]<<" ";
cout<<endl;
Msort(data1,data2,1,n);
cout<<"归并排序后:"<<endl;
for(i=1;i<=n;i++)
cout<<data1[i]<<" ";
cout<<endl;
}
system("pause");
return 0;
}
--------------------------------------------------测试程序-----------------------------------------------------请输入案例个数:2
请输入元素个数:9
请输入待排序元素:
87 65 2 77 88 54 2 7 8
归并排序前:
87 65 2 77 88 54 2 7 8
归并排序后:
2 2 7 8 54 65 77 87 88
请输入元素个数:10
请输入待排序元素:
10 9 8 7 6 5 4 3 2 1
归并排序前:
10 9 8 7 6 5 4 3 2 1
归并排序后:
1 2 3 4 5 6 7 8 9 10
请按任意键继续. . .
分享到:
相关推荐
用C++实现归并排序,题目基于MIT的算法导论中的第二章中的归并排序算法要求,visual studio 2010 实现
使用C++编写的插入&归并排序小程序,略简单,只实现基本功能
C++典型的归并排序C++典型的归并排序C++典型的归并排序C++典型的归并排序C++典型的归并排序
归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
基于visual studio2010,的程序开发,...............................................................................................
归并排序,插入排序,以及两种排序算法的结合C++实现
计算机算法课程的作业,用c++实现了归并排序和快速排序,并比较了两种算法的速度。测试数据为随机生成,可设置为10万、100万、1000万大小的数组。在代码中提供了详细的注释,在容易出错的地方进行了解释。下面是得到...
插入排序、冒泡排序、归并排序、快速排序四种排序方式的C++实现,各写成了一个函数,主函数中可以选择调用那一个。初始化数组时用的是随机种子srand((int)time(0))。在宏中定义数组大小。
C++实现希尔、快速、堆排序、归并排序算法,一些中文注释可能成乱码了,但是不影响代码执行。
完整的自然归并排序算法源程序,可自行输入待排元素个数以及数值,输出排好序的序列。
实现归并方法做排序,程序实现方法简单,是可运行,c语言基础功能
使用C++书写的归并排序算法,希望对各位有用。也请大牛指教代码中有何不足的地方!
快速排序、归并排序、改进的归并排序算法的C++代码。(含测试用例,代码逻辑清晰可运行。) (划分子区间,分别对左右子区间进行排序,开始归并已经排好序的low到high之间的数据。改进后的归并排序对数组元素下标...
一个 c c++写的归并排序算法,欢迎各位匹配指正。
使用c++编写的归并排序程序,可以在VC或VS上直接运行。代码调理清楚,并附有详细注释。
本文件是7种常用排序算法的实现(C++),包括冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序以及快速排序。代码详细有注释且有测试用例。
数据结构:快速排序、堆排序、归并排序、希尔排序 c++实现
归并排序的C++代码,是TXT文档形式,希望有用
快速排序、归并排序、基数排序等排序算法比较,比较时间性能,采用C++语言实现。。。