记录刚学习的非递归实现归并排序
由于初学，把自已一些对编码的理解记录下来
不足的地方欢迎大家指正
非递归实现归并的基本原理：
对于一个数组{26，5，77，1，61，11，59，15，48，19}
如上图所示，我们所要实现上图的模型：
一是要比较每两个数组所含值的大小关系，从而排序成一个有序的且含那两个数组的大数组
（{26}，{5}->{5,26} {5,26},{1,77}->{1,5,26,77})
二是如何将两个小数组归并为一个大数组
对于第一个问题：
存在两个数组{1,5,26,77}与{11，15，59，61}和一个临时数组num[ ]
用i来代替第一个数组的元素1
用j来代替第二个数组的元素11
用k来代表num中的第一个元素
先来比较两个数组的第一个元素，
如果i<j,则i++，k++
如果j<i,则j++，k++
直至一个数组中的元素全部赋到num[ ]中，则把另一数组的元素依次赋到num[ ]中
同理，在一个数组中，我们用3个变量将一个数组分割
{26，5，77，1，61，11，59，15，48，19}
left=26，mid=61，right=19
此时left->mid代表{26，5，77，1，61}
mid+1->right代表{11，59，15，48，19}
void merge(int SR[],int QR[],int left,int mid,int right)
{
int i,j,k,L;/*SR[]是传递下来的原数组，QR是归并后的新数组*/
/*i记录从left->mid*/
/*j记录从mid+1->right*/
/*k记录两个数组归并后的数组*/
/*L用用于把剩余的一个数组的值依次补录入新数组中*/
for(i=left,j=mid+1,k=left;i<=mid&&j<=right;k++)
{
if(SR[i]<SR[j])
QR[k]=SR[i++];
else
QR[k]=SR[j++];
}
if(i<=mid)
{
for(L=0;L<=mid-i;L++)
QR[k+L]=SR[i+L];
}else
{
for(L=0;L<=right-j;L++)
QR[k+L]=SR[j+L];
}对于第二个问题：
（1） 可以通过循环来表示所分块的大小
for(s=1;s<max;s*=2) /*max代表数组的最大范围*/
{
}所以第一次循环，s=1，即每个元素都作为一个数组
第二次循环，s=s*2=2，即两个元素作为一个数组
……
（2）找到每个数组开始的元素下表与结束下标
① 用i来代表原数组的第一个元素下标(i=0)，当s=1时 （每个元素内涵一个值）
left=i=0 mid=i+s-1=0 mid+1=1 right=i+2*s-1=1 此时表示第一个和第二个元素
i=i+2*s= 2
left=i=2 mid=i+s-1=2 mid+1=3 right=i+2*s-1=3 此时表示第三个与第四个元素
i=i+2*s=4
left=i=4 mid=i*s-1=4 mid+1=5 right=i+2*s-1=5 此时表示第五个与第六个元素
…………
② 当s=2时(此时i又重置为0）
left=i=0 mid=i+s-1=1 mid+1=2 right=i+2*s-1=3
此时表示第一个元素与第二个元素（每个元素内涵2个值）
…………
当s>=max时（max为数组所含元素的个数）结束
#include <stdlib.h>
void merge(int SR[],int QR[],int left,int mid,int right);
int main()
{
int s,i,j;
int *TR=(int*)malloc(10*sizeof(int));/*创建一个临时储存空间*/
int num[10]={8,6,1,7,5,9,3,4,5,2};
int n=9/*n为数组最后一个元素的下标*/
for(s=1;s<10;s*=2)
{
i=0;
while(i<n-2*s+1) /*----------①*/
{
merge(num,TR,i,i+s-1,i+2*s-1);
i=i+2*s;
}
if(i<n-s+1) /*--------②*/
merge(num,TR,i,i+s-1,n);
else
for(j=i;j<=n;j++)/*----------③*/
TR[j]=num[j];
for(i=0;i<10;i++) /*----------④*/
num[i]=TR[i];
}①是对不同层数组末尾的判断，其实是 (right<n) == (i+2*s-1<n) == (i<n-2*s+1)
②是对所剩元素为双的判断，其实是 （mid<n)
③是为所剩元素为单的判断，并将所剩元素插入新数组中
④是记录每一次循环所产生的新的数组TR，并将值赋予num，然后num继续被merge函数调用
否则一直调用的是原本的未排序的num！！！
下面是两部分之和
#include <stdlib.h>
void merge(int SR[],int QR[],int left,int mid,int right);
int main()
{
int s,i,j;
int *TR=(int*)malloc(10*sizeof(int));
int n=9;
int num[10]={8,6,1,7,5,9,3,4,5,2};
for(s=1;s<10;s*=2)
{
i=0;
while(i<n-2*s+1)
{
merge(num,TR,i,i+s-1,i+2*s-1);
i=i+2*s;
}
if(i<n-s+1)
merge(num,TR,i,i+s-1,n);
else
for(j=i;j<=n;j++)
TR[j]=num[j];
for(i=0;i<10;i++)
num[i]=TR[i];
}
for(i=0;i<10;i++)
{
printf("%d",num[i]); /*加入printf用来输出*/
}
return 0;
}
void merge(int SR[],int QR[],int left,int mid,int right)
{
int i,j,k,L;
for(i=left,j=mid+1,k=left;i<=mid&&j<=right;k++)
{
if(SR[i]<SR[j])
QR[k]=SR[i++];
else
QR[k]=SR[j++];
}
if(i<=mid)
{
for(L=0;L<=mid-i;L++)
QR[k+L]=SR[i+L];
}else
{
for(L=0;L<=right-j;L++)
QR[k+L]=SR[j+L];
}
}