问题描述

这是一个排序算法，但结果总是不争取，求大神指出错在哪？

 #include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#define  MAX 100
int b;
    int arr[MAX],tearr[MAX];

void merge(int a[],int t[],int lhead, int rtail)
{
    int lt, k, mid, rt;
    mid = (lhead+rtail)/2;
    lt = k = lhead;
    rt = mid+1;
    if (rtail-lhead <= 0)
    {
        goto tailsort;
    }

    merge(a,t, lhead,mid);
    merge(a,t, mid+1,rtail);

        while (lt<=mid && rt<=rtail)
        {
            t[k++] = (a[lt]<=a[rt])?a[lt++]:a[rt++];
        }

        while (lt<=mid)
        {
            t[k++] = a[lt++];
        }
        while (rt<=rtail)
        {
            t[k++] = a[rt++];
        }

    for (b=0; b<MAX;b++)
    {
        a[b] = t[b];
    }

tailsort:    ;
}

void main()
{
    int head,tail,i;

    for (i=0; i<MAX;i++)
    {
        arr[i] = rand();
    }

    for(i=0; i<MAX; i++) printf("%d  ",arr[i]);
    system("pause");

    head = 0; tail = MAX;

    merge(arr,tearr, head, MAX-1);

    for (i=0; i<MAX;i++)
    {
        arr[i] = tearr[i];
    }

    for (i=0; i<MAX;i++)
    {
        printf(" %d",arr[i]);
    }
    system("pause");
}

解决方案

楼主我照抄了您的代码运行后，发现好多数据都清零了，对着您的代码我思考实验了半天，最终终于找到问题所在，以下是代码【在您的代码基础上稍有更改，经我测验没有问题，请验证】

#include
#include
#include
#define MAX 100
int b;
int arr[MAX],tearr[MAX];

void merge(int a[],int t[],int lhead, int rtail)
{
int lt, k, mid, rt;
mid = (lhead+rtail)/2;
lt = k = lhead;
rt = mid+1;
if (rtail-lhead <= 0)
{
goto tailsort;
}

merge(a,t, lhead,mid);
merge(a,t, mid+1,rtail);

    while (lt<=mid && rt<=rtail)
    {
        t[k++] = (a[lt]<=a[rt])?a[lt++]:a[rt++];
    }

    while (lt<=mid)
    {
        t[k++] = a[lt++];
    }
    while (rt<=rtail)
    {
        t[k++] = a[rt++];
    }

for (b=0; b<MAX;b++)
{
    a[b] = t[b];
}

tailsort: ;
}

void main()
{
int i;

for (i=0; i<MAX;i++)
{
    arr[i] = rand();
}

for(i=0; i<MAX; i++) printf("%d  ",arr[i]);
system("pause");

/*****问题出在这里******/
for (i=0; i<MAX;i++)
{
    tearr[i] = arr[i];
}
/*****加上这个循环即可，至于为什么，楼主请自行考虑！******/

merge(arr,tearr, 0, MAX-1);

for (i=0; i<MAX;i++)
{
    printf(" %d",arr[i]);
}
system("pause");

}

解决方案二：

http://jingyan.baidu.com/article/fa4125acb2988d28ac7092a8.html
http://www.cnblogs.com/kaituorensheng/archive/2013/02/21/2919934.html
这里有完整的代码

解决方案三：

 #include<iostream>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#define MAX 10
using namespace std;
int b;
int arr[2][MAX];

void merge(int a[],int t[],int lhead, int rtail, int ifor)
{
    int lt, rt , k, mid, rduan;
    k = lhead;
//    if (rtail-lhead <= 0)
//    {
//        goto tailsort;
//    }
//    merge(a,t, lhead,mid);
//    merge(a,t, mid+1,rtail);
    for (int i=lhead; i+ifor <= rtail; i += ifor*2 )
    {
        lt = i;
        rt = i + ifor;
        mid = rt - 1;
        rduan = rt+ifor-1;
        if (rduan > rtail) rduan = rtail;
        while (lt<=mid && rt<=rduan)
        {
            t[k++] = (a[lt]<=a[rt])?a[lt++]:a[rt++];
        }
        while (lt<=mid)
        {
            t[k++] = a[lt++];
        }
        while (rt<=rduan)
        {
            t[k++] = a[rt++];
        }
    }

//    for (b=0; b<MAX;b++)
//    {
//        a[b] = t[b];
//    }
//    tailsort: ;
}

int main()
{
    int head,tail,i;
    srand((unsigned)time(NULL));//用时间来做随机种子,使得每次运行得到的数列不同
    for (i=0; i<MAX;i++)
    {
        arr[0][i] = rand()%(50-10+1)+10; //可以改用rand()%(Y-X+1)+X，表示在[X,Y]中随机一个数
    }

    for(i=0; i<MAX; i++) printf("%d ",arr[0][i]);
    system("pause");

    head = 0; tail = MAX - 1;
    int next = 1;
    int ifor = 1;
    while (ifor < MAX - 1)
    {
        merge(arr[1-next],arr[next], head, tail, ifor);
        next = 1 - next;
        ifor *= 2;
    }

//    for (i=0; i<MAX;i++)
//    {
//        arr[i] = tearr[i];
//    }

    for (i=0; i<MAX;i++)
    {
        printf(" %d",arr[1-next][i]);
    }
    system("pause");
    return 0;
}

解决方案四：

1、while (lt<=mid && rt<=rtail)
{
t[k++] = (a[lt]<=a[rt])?a[lt++]:a[rt++];
}

2、 while (lt<=mid)
{
t[k++] = a[lt++];
}
3、 while (rt<=rtail)
{
t[k++] = a[rt++];
}
假如一个数满足第一个条件，那他就满足2，或3的其中一个条件你这t[k++]同一个数执行了两次？