2ウェイ集計ソート(MERGE_SORT)

2038 ワード

簡単な説明:
私は循環入力テストを使って、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つの簡単な実現で、思想に対する応用、参考に供します.