归并排序

[bosthhe1]

void Print(int *a, int size)
{
    for (int i = 0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
}
void Mereysort(int *a,int left,int right,int *tmp)
{
    if (left >= right)
        return;
    int left1 = left;
    int right1 = right;
    int mid = (left1 + right1) / 2;
    Mereysort(a, left1, mid, tmp);//先将数组划分为不可分割的子数组
    Mereysort(a, mid+1, right1, tmp);//分治
    int begin1 = left; int end1 = mid;
    int begin2 = mid + 1; int end2 = right1;
    int index = left;
    while (end1 >= begin1&&end2>=begin2)
        //这一这里的合并排序，是将不同的数组合并排序，小的再前面，大的在后面
    {//这里是将分开的两个数组进行比较排序，小的排前面，很定有一个数组先排完，剩下另一个数组再倒过去。
        if (a[begin1] > a[begin2])
        {
            tmp[index] = a[begin2];
            index++; begin2++;
        }
        else
        {
            tmp[index] = a[begin1];
            index++; begin1++;
        }
    }
//将剩下没拷贝完的数组，再倒过去
    while(begin1 <= end1)
    {
        tmp[index] = a[begin1];
        index++; begin1++;
    }
    while (begin2 <= end2)
    {
        tmp[index] = a[begin2];
        index++; begin2++;
    }
    for (int i = left; i <= right; i++)
    {
        a[i] = tmp[i];
    }
}

void Testmerey()
{
    int a[8] = { 1, 7, 8, 3, 4, 2, 6, 9 };
    int *tmp = (int *)malloc(sizeof(int));
    int size = sizeof(a)/sizeof(a[0]);
    Mereysort(a,0,size-1,tmp);
    Print(a,size);
}

int main()
{
    Testmerey();
    system("pause");
    return 0;
}