問個 歸並排序的問題
/**设个有序关键字表s1=(18,25,37,42),s2=(20,33,40).同时将s1,s2存储在数组r中
**s1放r,s2放,现要归并到一维数组r2中，只要依次比较这两个有序
**表中相应记录关键字，按取小原则复制到r2中
**/
#include<stdio.h>
#define MAXITEM 100
typedef struct rec
{
int key;
char data;
}elemnode;
void merge(elemnode r,elemnode r1,int l,int m,int h)
{// i,j是r的指示器，i的取值从l到m, j的取值从m+1到h,k是r1的指示器
int i = l,j = m+1,k = l;
while(i<=m && j<=h)
{
if(r.key<=r.key)
{
r1 = r;
i++;
}
else
{
r1 = r;j++;
}
k++;
}
if(i>m)
while(j<=h)
{
r1 = r;
j++;
k++;
}
else
while(i<=m)
{
r1 = r;
i++;
k++;
}
}
void mergepass(elemnode r,elemnode r1,int n,int l)
{
//将r中长度为L的两个部分合并，第一部分从p到期（p+l-1)
//第二部分从 p+1到(p+2*l-1)
int p = 1;
while(n-p+1>2*l)
{
merge(r,r1,p,p+l-1,p+2*l-1);
p+=2*l; //p向后移动2*l,准备下一次合并
}
if(n-p+1>l) //一个长度为l的部分与一个长度小于l的部分合并
merge(r,r1,p,p+l-1,n);
else //只剩下一个长度不大于l的部分，将其复制到r1
for(;p<=n;p++) r1 = r;
}
void mergesort(elemnode r,elemnode r1,int n)
{//对r中数据元素进行归并，结果仍放在r 中
int l = 1;
while(l<n)
{
mergepass(r,r1,n,l);l*=2;
mergepass(r1,r,n,l);l*=2;
}
}
void disp(elemnode r,int n)
{
int i;
for(i=1;i<=n;i++)
printf("%6d",r.key);
printf("\n");
for(i=1;i<=n;i++)
printf("%6s",r.data);
printf("\n");
}
void main()
{
elemnode s = {{0," "},{75,"王华"},{87,"李英"},{68,"张萍"},{92,"陈涛"},{88,"刘丽"},{61,"章强"},
{77,"孙军"},{96,"朱斌"},{80,"许伟"},{72,"曾亚"}};
elemnode s1;
int n = 10;
mergesort(s,s1,n);
disp(s,n);
}
void merge()這個函數基本理解了，但是void mergepass（）這個函數就不怎麼看得懂，應該怎麼理解呢？ 我是这么理解的不知道对不对
void mergepass(elemnode r,elemnode r1,int n,int l)
{
//将r中长度为L的两个部分合并，第一部分从p到期（p+l-1)
//第二部分从 p+1到(p+2*l-1)
int p = 1;
while(n-p+1>2*l)
{
merge(r,r1,p,p+l-1,p+2*l-1);
p+=2*l; //p向后移动2*l,准备下一次合并
}
if(n-p+1>l) //一个长度为l的部分与一个长度小于l的部分合并
merge(r,r1,p,p+l-1,n);
else //只剩下一个长度不大于l的部分，将其复制到r1
for(;p<=n;p++) r1 = r;
}
void mergesort(elemnode r,elemnode r1,int n)
{//对r中数据元素进行归并，结果仍放在r 中
int l = 1;
while(l<n)
{
mergepass(r,r1,n,l);l*=2;
mergepass(r1,r,n,l);l*=2;
}
}
R中比如最大是N，在N里存在很多个L长度，从1开始，取L长度，只要2L个长度不超N，然后取L长度和后L个长度进行比较结果存到R1里，这个参考第一个函数就知道了，做好后P移动到2L长度后的位置，然后其他情况就是只剩一个L的长度和一个未满L的长度，同样再用第一函数合并，或者最后剩下不到一个L的长度直接全部到R1，然后主要看下下面一个函数mergepass(r,r1,n,l);l*=2; mergepass(r1,r,n,l);l*=2; 时，L为1时就是一个元素一个元素比较比如1和2比较好，3和4比较，一直比到最后所有结果进R1，然后L双倍后，在R1里就是两个两个元素进行比较，比如12和34，56和78比好后在回到R里，这样循环 具体设了个R和R1
R ：0 4 6 2 3 1 8第一次L=1时排列
R1 变成：40 26 13 8 随后L变为2 把R1倒回R
R变成：0246 138 这时L变为4用情况2做
R1变成：0123468 L变为8了情况3直接复制回R
所以最后R排好 还没细看，看不懂。。。 引用第4楼august于2008-06-13 14:34发表的:
还没细看，看不懂。。。
这个例子应该看的懂吧
具体设了个R和R1
R ：0 4 6 2 3 1 8第一次L=1时排列
R1 变成：40 26 13 8 随后L变为2 把R1倒回R
R变成：0246 138 这时L变为4用情况2做
R1变成：0123468 L变为8了情况3直接复制回R
所以最后R排好
页:
[1]