2ウェイ集計ソート(MERGE_SORT)
2038 ワード
簡単な説明:
私は循環入力テストを使って、Ctrl+zを出力して終わり、ランダム発生数の個数を入力して、それから結果を観察します.
コードは次のとおりです.
2ウェイ-集計ソートコード:
これはただ1つの簡単な実現で、思想に対する応用、参考に供します.
私は循環入力テストを使って、Ctrl+zを出力して終わり、ランダム発生数の個数を入力して、それから結果を観察します.
コードは次のとおりです.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void Merge(int *a,int low,int mid,int high)
{
if(low>=high)
return;
int i,j,k;
int b[105];
i=low;
j=mid+1;
k=0;
while(i<=mid && j<=high)
{
if(a[i]<a[j])
b[k++]=a[i++];
else
b[k++]=a[j++];
}
while(i<=mid)
b[k++]=a[i++];
while(j<=high)
b[k++]=a[j++];
for(i=low;i<=high;i++)
a[i]=b[i-low];
}
void MergeSort(int *a,int low,int high)
{
if(low>=high)
return ;
int mid=(low+high)/2;
Merge(a,low,mid);
Merge(a,mid+1,high);
Merge_Sort(a,low,mid,high);
}
int main()
{
int num[1005];
int n;
int i;
srand(time(0));
while(~scanf("%d",&n))
{
for(i=1;i<=n;i++)
num[i]=rand()%99+1;
for(i=1;i<=n;i++)
printf("%d ",num[i]);
putchar('
');
MergeSort(num,1,n);
for(i=1;i<=n;i++)
printf("%d ",num[i]);
putchar('
');
}
return 0;
}
2ウェイ-集計ソートコード:
</pre><pre name="code" class="cpp"> void Merge(int *a,int low,int mid,int high)
{
if(low>=high)
return;
int i,j,k;
int b[105];
i=low;
j=mid+1;
k=0;
while(i<=mid && j<=high)
{
if(a[i]<a[j])
b[k++]=a[i++];
else
b[k++]=a[j++];
}
while(i<=mid)
b[k++]=a[i++];
while(j<=high)
b[k++]=a[j++];
for(i=low;i<=high;i++)
a[i]=b[i-low];
}
void MergeSort(int *a,int low,int high)
{
if(low>=high)
return ;
int mid=(low+high)/2;
MergeSort(a,low,mid);
MergeSort(a,mid+1,high);
Merge(a,low,mid,high);
}
これはただ1つの簡単な実現で、思想に対する応用、参考に供します.