|
|
今天复习另外两种排序算法：Shell排序＆归并排序。 Shell排序是插入排序的一种。昨天已经复习了两种插入排序算法——直接插入排序＆折半插入排序，Shell排序属于的三种插入排序算法。 Shell排序的基本思路是将记录按照一定的间隔进行插入式排序，然后逐渐缩小间隔到1。当间隔缩小到1时，Shell排序相当于直接插入排序。但是因为前面的排序过程基本上已经定下了记录的大概位置，所以并不需要比较和移动很多记录。因此算法的效率要比直接插入排序好。 Shell排序：
 void ShellSort(RcdType r[],int n)
   {
 int i,j,d;
d=n/2;
  while(d>0){
for(i=1+d;i<=n;i++){
r[0]=r[i];
j=i-d;
while(j>0 && r[j].key>r[0].key){
r[j+d]=r[j];
j-=d;
 }
r[j+d]=r[0];
}
d/=2;
}
 } 今天复习的另外一种排序算法是归并排序。归并排序的基本思想是将两个有序记录集归并为一个有序的记录集。具体实现起来有两种方法，即所谓的自顶向下法和自底向上法。我个人认为自顶向下法更为简单。 自顶向下的归并排序(运用递归)：
void Merge(RcdType r[],int l,int m,int h)
{
int i,j,k,*r2;
i=l;
j=m+1;
k=0;
r2=(int *) malloc(sizeof(int)*(h-l+1));
while(i<=m && j<==h){
if(r[i].key<r[j].key) r2[k++]=r[i++];
else r2[k++]=r[j++];
}
while(i<=m) r2[k++]=r[i++];
while(j<=h) r2[k++]=r[j++];
for(k=0,i=l;i<=h;)
r[i++]=r2[k++];
free(r2);
}
void MergeSort(RcdType r[],int s,int e)
{
int m;
if(s!=e){
m=(s+e)/2;
MergeSort(r,s,m);
MergeSort(r,m+1,e);
Merge(r,s,m,e);
}
} 自底向上的归并排序：
void Merge(RcdType r[],int l,int m,int h)
{
int i,j,k,*r2;
i=l;
j=m+1;
k=0;
r2=(int *) malloc(sizeof(int)*(h-l+1));
while(i<=m && j<==h){
if(r[i].key<r[j].key) r2[k++]=r[i++];
else r2[k++]=r[j++];
}
while(i<=m) r2[k++]=r[i++];
while(j<=h) r2[k++]=r[j++];
for(k=0,i=l;i<=h;)
r[i++]=r2[k++];
free(r2);
}
void MergePass(RcdType r[],int length,int n)
{
int i;
for(i=1;i+length*2-1<=n;i=i+length*2){
Merge(r,i,i+length-1,i+2*length-1);
}
if(i+length-1<n) Merge(r,i,i+length-1,n);
}
void MergeSort(RcdType r[],int n)
{
int length;
for(length=1;length<n;length*=2){
MergePass(r,length,n);
}
}
|