main.cpp

首先通过递归调用

/*
基本算法思想：
   首先通过递归调用，将原数组不断的分小，最终将数组分成N份。
   然后将有序的两组合并成一个有序数组，每合并一次数组的规模
   就会翻倍，最终会将原来无序的数组变成一个有序的数组。
*/
#include<iostream>
using namespace std;
int n = 0;
void mergesort(int p[20], int start, int end);
void smerge(int p[20], int start, int mid, int end);
void main()
{
	int sorts[20];
	int m;
	cout << "请输入要排序的元素数目：" ;
	cin >> m;
	cout << "请输入排序的" << m << "元素序列：" << endl;
	for(int i=0; i<m; i++)
		cin >> sorts[i];
	mergesort(sorts, 0, m-1);
	for(i=0; i<m; i++)
		cout << sorts[i] << " ";
	cout << endl;
	cout << "s算法执行的赋值次数：";
	cout << n << endl;
}
/*

 p[20] 要排序元素所在的数组
 start 要排序元素第一个元素的位置
 end   要排序元素最后一个元素的位置
*/
void mergesort(int p[20], int start, int end)
{
	int mid;
	if(start < end)
	{
		mid = (start+end)/2;
		mergesort(p, start, mid);//排序 递归调用
		mergesort(p, mid+1, end);//排序 递归调用
		smerge(p, start, mid, end);//合并
	}
}
//合并函数
void smerge(int p[20], int start, int mid, int end)
{
	int b[20];
	int i = 0;
	int index1 = start;
	int index2 = mid + 1;
	while(index1<mid+1&&index2<end+1)//两数组都没有用光
	{
		if(p[index1] < p[index2])
		{
			n++;
			b[i] = p[index1];
			i++;
			index1++;
		}
		else
		{
			n++;
			b[i] = p[index2];
			i++;
			index2++;
		}
	}
	if(index1 < mid+1)//第二个序列已经用完，而第一个没有用完
	{
		while(index1 < mid+1)
		{
			b[i] = p[index1];
			i++;
			index1++;
			n++;
		}
	}
	else
	{
		while(index2 < end+1)//第一个序列已经用完，而第二个没有用完
		{
			b[i] = p[index2];
			i++;
			index2++;
			n++;
		}
	}
	i = 0;
	for(int k=start; k<end+1; k++)//将有序的数赋回原数组，不能改变起始位置
	{
		p[k] = b[i];
		i++;
		n++;
	}
}