习题6-二路归并排序.c

数据结构各章实验源代码； 数据结构实验源代码

#include  "datastru.h"
#include  <stdio.h>

void merge(RECNODE *r, int low, int m, int high)
{/*两相邻的有序表(一个从low到m;另一个从m+1到high)合并为一个有序表(从low到high)*/
 	RECNODE  r1[MAXSIZE];             /*合并时用的缓冲向量*/
	int i, j, k;

	i = low;
	j = m + 1;
	k = 0;
	while(i <= m && j <= high)              /*两相邻的有序表合并*/
	  if(r[i].key <= r[j].key)
	    {r1[k] = r[i];  i++;  k++;}
	  else
	    {r1[k] = r[j];  j++;  k++;}
	while(i <= m)                           /*有序表剩余部分处理*/
	   {r1[k] = r[i];  i++;  k++;}
	while(j <= high)                        /*有序表剩余部分处理*/
	   {r1[k] = r[j];  j++;  k++;}
	for(i = low, k = 0; i <= high; i++, k++)/*缓冲向量r1复制到原来的r中*/
	   r[i] = r1[k];

}

void merge_one(RECNODE *r, int lenth, int n)
{/*二路归并中的"一趟归并"算法*/
	int i = 0;

	while(i + 2 * lenth - 1 < n)
	  {merge(r, i, i + lenth - 1, i + 2 * lenth - 1);/*两子序列长度相等的*/
	   i = i + 2 * lenth;}                           /*情况下调用merge*/
	if(i + lenth - 1 < n - 1)
	   merge(r, i, i + lenth - 1, n - 1);            /*序列中的余留部分处理*/
}

void mergesort(RECNODE *r, int n)
{/*二路归并排序算法*/
	int lenth = 1;                 /*有序子序列长度初始值 = 1*/

	while(lenth < n)
	  {merge_one(r, lenth, n);     /*调用"一趟归并"的算法*/
	   lenth = 2 * lenth;}         /*有序子序列长度加倍*/
}

main( )
{ RECNODE  a[MAXSIZE];
  int  i, j, k, len;

 printf("\n\n输入待排序数据(整数，以空格隔开，0 结束) : "); k = 0; scanf("%d",&j);
 while(j != 0) { k++; a[k-1].key = j; scanf("%d",&j); }
 len = k;
 printf("\n排序前 : ");
 for (i = 0; i < len; i++)   printf("  %d",a[i].key);
 printf("\n");
 mergesort (a,len);
 printf("\n");
 printf("\n\n排序后 : ");
 for (i = 0; i < len; i++)   printf("  %d",a[i].key);
 printf("\n");
}