归并排序(非递归)
//归并排序1（迭代的方式）
#include<iostream>#include<algorithm>
using namespace std;
template<class T>
void Merge(T* initList, T*mergeList, int l, int m, int n)//initeList是要归并排序的数组，MergeList是排序好要保存结果的数组，l是前面数组的第一个下标，m数组一份为二前面数组的最后一个元素的下标，n是数组的个数
{
int i1, i2, iResult;//i1,i2分别对两个数组进行循环，iresult对合并以后的数组进行循环
for (i1 = l, i2 = m + 1, iResult = l; i1<=m&&i2<=n; iResult++)//i1从1开始，i2从m+1开始
{
if (initList[i1] < initList[i2])//如果第一个数组中的数小于第二个数组中的数把第一个放进合并数组,指针往前走一步，否则把第二个放进合并数组,指针往前走一步
{
mergeList[iResult] = initList[i1];
i1++;
}
else
{
mergeList[iResult] = initList[i2];
i2++;
}
}
copy(initList + i1, initList + m + 1, mergeList+iResult);//如果第一个数组有剩余，把剩下的直接拷贝到结果数组里面
copy(initList + i2, initList + n + 1, mergeList + iResult);//如果第二个数组有剩余，把剩下的直接拷贝到结果数组里面
}
template<class T>
void MergePass(T* initList, T*resultList, const int n,const int s)//n代表大数组中数据的个数，s代表要进行归并的小数组的长度
{
int i;
for (i = 1;i<=n-2*s+1; i += 2*s)//舍去要排序数组的零位置不用，每次往前跳2S,一直让它跑到倒数第二个小数组的第一个数的位置
Merge(initList, resultList,i,i + s - 1,i+2*s-1);//归并前两个小数组
if (i + s - 1 < n)//i+s-1<n说明这并不是单独剩余的一个数组
Merge(initList, resultList, i, i + s - 1, n);//
else
copy(initList + i, initList + n + 1, resultList+i);//否则说明，没有数组和它归并，直接复制到结果数组的尾端
}
template<class T>
void MergeSort(T*a,const int n)
{
T*tmpList = new int[n + 1];//tmpList[0]不用
for (int s= 1; s < n; s *= 2)
{
//数组a和tmpList交替作为结果数组，最后排序完成的数组是放在tmplist数组中，两个数组直接相互覆盖数据
MergePass(a,tmpList,n,s);//归并一行（a作为要排序的数组s*= 2;//小数组归并后的大小变为原来的两倍
MergePass(tmpList, a,n,l);//再归并一行
}
delete[]tmpList;
}
{
int a[] = { 0,23,47,81,95,7,14,39,55,62,74 };//0是故意写的不用a[0]
int b[11] = { 0 };//归并的数组放在b数组中
Merge(a, b, 1, 4, 10);
for (int i = 1; i < 11; ++i)
{
cout << b[i] << " " << endl;
}
int m[] = { 0,26,5,77,1,61,11,59,15,48,19 };
int n[11] = { 0 };//每一次得到的结果，放在这个数组里
MergePass(m, n, 10, 1);//归并第一次
for (int i = 1; i < 11; i++)
{
cout << n[i] << " " << endl;
}
MergePass(n, m, 10, 2);//归并第二次
for (int i = 1; i < 11; i++)
{
cout << n[i] << " " << endl;
}
MergePass(m, n, 10, 4);//归并第三次
for (int i = 1; i < 11; i++)
{
cout << n[i] << " " << endl;
}
MergePass(n, m, 10, 8);//归并第四次
for (int i = 1; i < 11; i++)
{
cout << n[i] << " " << endl;
}
cout << "上面都是中间结果的测试" << endl;
cout << "下面开始测试MergeSort" << endl;
int x[] = { 0,26,5,77,1,61,11,59,15,48,19 };
MergeSort(x, 10);
for (int i = 0; i < 11; i++)
cout << x[i] << endl;
cout << " ddd" << endl;
return 0;
}