集計ソートの再帰アルゴリズム
再帰アルゴリズムには再帰終了の条件がある.コードは次のとおりです.
//bugs:アルゴリズムに小さなバグがあります.(n+1)/2の場合、n+1が奇数であることを考慮していません.
関連記事:集計ソートの非再帰アルゴリズムスタックソート
//bugs:アルゴリズムに小さなバグがあります.(n+1)/2の場合、n+1が奇数であることを考慮していません.
#include <stdio.h>
#include <conio.h>
#define MAX 1000
//
void swap(int *a,int *b);
void sort_parallel(int target[],int start1,int start2,int num,int n);
void merge_sort_recurrence(int target_array[],int n);
int main()
{
int test[]={3,1,2,6,4,11,5,8,7,10};
merge_sort_recurrence(test,10);
for(int i=0;i<10;i++)
printf("%d ",test[i]);
getch();
}
// ( )
void merge_sort_recurrence(int target_array[],int n)
{
if(n==1)
return ;
if(n==2)
{
if(target_array[0]>target_array[1])
swap(&target_array[0],&target_array[1]);
}
merge_sort_recurrence(target_array,(n+1)/2);
merge_sort_recurrence(target_array+(n+1)/2,n/2);
sort_parallel(target_array,0,(n+1)/2,(n+1)/2,n);
}
//
void sort_parallel(int target[],int start1,int start2,int num,int n)
{
int flag=0;
int temp_array[MAX]={0};
int i=0,j=0;
while(i<num && j<num && start1+i<n && start2+j<n )
{
if(target[start1+i]<target[start2+j])
{
temp_array[flag++]=target[start1+i];
i++;
}
else if(target[start1+i]==target[start2+j])
{
temp_array[flag++]=target[start1+i];
i++; j++;
}
else
{
temp_array[flag++]=target[start2+j];
j++;
}
}
while(i<num && start1+i<n)
temp_array[flag++]=target[start1+i++];
while(j<num && start2+j<n)
temp_array[flag++]=target[start2+j++];
//
for(i=start1,j=0;i<n && i<start1+2*num;i++,j++)
target[i]=temp_array[j];
}
//
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
まとめ:再帰の書き方は非再帰より簡単ですが、オーバーヘッドが大きいです.関連記事:集計ソートの非再帰アルゴリズムスタックソート