Question

数据结构，题，在线求答案

Answer 1

二路归并排序,从大到小,递归法的过程:

             73 72 23 71 94 15 18 68
              /                   \
       73 72 23 71             94 15 18 68
       /         \             /         \
    73 72       23 71       94 15       18 68
   /     \     /     \     /     \     /     \
  73     72   23     71   94     15   18     68
   \     /     \     /     \     /     \     /
    73 72       71 23       94 15       68 18
       \         /             \         / 
       73 72 71 23             94 68 18 15
              \                   /
             94 73 72 71 68 23 18 15


//C语言测试程序

#include<stdio.h>
#include<stdlib.h>

//合并函数
void mergeArray(int *data,int start,int middle,int end,int *temp)
{
	int index01;
	int index02;
	int count;

	index01=start;		//数组01的指针
	index02=middle+1;	//数组02的指针
	count=0;
	while(index01<=middle && index02<=end)
	{
		if(data[index01]>data[index02]) //从大到小排序
		{
			temp[count++]=data[index01++];
		}
		else
		{
			temp[count++]=data[index02++];
		}
	}
	while(index01<=middle)
	{
		temp[count++]=data[index01++];
	}
	while(index02<=end)
	{
		temp[count++]=data[index02++];
	}
	for(index01=0;index01<count;index01++)
	{
		data[start+index01]=temp[index01];
	}
}
//显示排序过程
void showData(int *data,int start,int end)
{
    int i;
    for(i=start;i<=end;i++)
    {
        printf("%d ",data[i]);
    }
    printf("\n");
}
//分组函数
void mergeFunc(int *data,int start,int end,int *temp)
{
	int middle;
	if(start<end)
	{
		middle=(start+end)/2;
		mergeFunc(data,start,middle,temp);
		mergeFunc(data,middle+1,end,temp);
		mergeArray(data,start,middle,end,temp);//合并
		////////
		showData(data,start,end);
		////////
	}
}
//归并排序
void mergeSort(int *data,int len)
{
	int *ptr=NULL;
	ptr=(int*)malloc(len*sizeof(int)); //用于保存中间数据
	if(!ptr)
	{
		printf("\nOverflow.\n");
		return;
	}
	mergeFunc(data,0,len-1,ptr);
	free(ptr);
}

int main()
{
	//数据
	int data[]={73,72,23,71,94,15,18,68};
	int len;
	int i;
	len=sizeof(data)/sizeof(int);
	//打印数组
	printf("原数组: ");
	for(i=0;i<len;i++)
	{
		printf("%d ",data[i]);
	}
	printf("\n");
	//归并排序
	mergeSort(data,len);
	//打印数组
	printf("排序后: ");
	for(i=0;i<len;i++)
	{
		printf("%d ",data[i]);
	}
	printf("\n");

	return 0;
}