阅读以下说明和C代码,填补C代码中的空缺,将解答写在答题纸的对应栏内。
【说明】
实现二路归并排序的一种方法是先递归地划分出子序列(当子序列仅包含0个或1个元素时得到初始的有序子序列),然后两两合并后得到更长的有序子序列,最后完成排序处理。
函数mergesort(int a[],int n)对数组a的前n个元素进行排序。
函数m _sort(int a[], int left, int right, int tp[])对序列进行划分,对以(left+right)/2为界的两个子序列排序后,调用merge()对两个有序子序列进行合并。
函数merge(int a[],int left,int m,int right,int *tp)对数组下标范围[left, m-1]和[m,right-1]所表示的两个有序子序列进行合并。
将非递减有序子序列a[left]~a[m-1]和 a[m]~a[right-1]合并为一个非递减有序序列的过程是:分别用i、j表示两个有序子序列的元素下标,比较a[i]和 a[j],若a[i]较小,则输出 a[i]且i递增,否则输出 a[j]且j递增,再次比较a[i]和 a[j]并重复以上过程,直到其中任一子序列到达结尾,然后输出另一序列的剩余元素。合并过程中所输出的元素暂存在空间足够大的辅助数组 tp[]中,最后再复制到数组a[]。
【C代码】
#include <stdio.h>
#include <stdlib.h>
//将非递减有序子序列a [left] ~a[m-1]和 a[m]~a[right-1]合并为有序序列
a [ left] ~a [right-1]
void merge(int a[ ] ,int left,int m,int right, int *tp){
int i,j,k =0;
for(i = left,j = m; i < m &&j < right; )
if (a[i] < a[j]) tp [k++] = a[i++] ;
else tp [ k++] = a[j++];
while( (1) ) //复制未结尾序列的剩余元素到辅助数组
tp [k++]= a [ i++];
while( (2) ) //复制未结尾序列的剩余元素到辅助数组
tp [k++] = a[j++];
for (k = 0,i = left; i < right; ++i,++k)
//合并所得序列的元素复制回数组a[ ]
a [ i] = (3) ;
}
void m_sort (int a[], int left, int right,int tp[]){
if( right-left<2 ) return ;
int mid = (left + right) / 2; //设置待排序序列的划分点
m_sort(a, left, mid,tp) ; //对划分出的第1个子序列进行归并排序
m_sort ( a, (4) , tp); //对划分出的第2个子序列进行归并排序
merge (a, (5) , tp); //合并已有序的第1、2个子序列
void mergesort (int a[], int n) {
int *tp = (int * ) malloc (n*sizeof (int) );
//申请归并过程中需要使用的辅助空间
if ( ! tp) return;
m_sort(a,0 , n,tp) ; //调用m_sort对a [ 0] ~a [n-1]进行归并排序
free (tp) ;
}
int main (){
int a [10]= { 15,3,26,8,4,1,9,7,3,11};
int i, n = 10;
for (i=0 ; i<n;i++)
printf ( "%d \t" , a [i]);
printf ( "\n") ;
mergesort (a,n) ;
printf ( "after sorting\n" ) ;
for (i=0 ; i<n ;i++)
printf ( "%d \t" , a [ i] );
printf ( "\n" ) ;
return 0;
}