归并排序(递归和非递归)-向日葵屋

归并排序(递归和非递归)

归并排序

一.递归
二.非递归
- 1.基础
- 2.改进

一.递归

归并实际上就是把一个数组每次二分，分别排序每个子数组再将有序的子数组进行合并。（归并排序需要一个额外的数组来存放每个子数组，并在排序结束后将其拷贝到原数组）。

在这里插入图片描述

#include<stdio.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
void _MergeSort(int* a, int begin, int end, int* tmp)
{
    if (begin >= end)
        return;
    int mid = (begin+end) / 2;
    _MergeSort(a, begin, mid,tmp);
    _MergeSort(a, mid + 1, end,tmp);
    int begin1 = begin, begin2 = mid + 1;
    int end1 = mid, end2 = end;
    int i = begin;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[i++] = a[begin1++];
        }
        else
        {
            tmp[i++] = a[begin2++];
        }
    }
    while (begin1 <= end1)
    {
        tmp[i++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[i++] = a[begin2++];
    }
    memcpy(a+begin, tmp+begin, sizeof(int)*(end - begin + 1));
}
void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc fail");
        return;
    }
    _MergeSort(a,0,n-1,tmp);
    free(tmp);
}
int main()
{
    int a[20000];
    srand((unsigned int)time(NULL));
    for (int i = 0; i < 20000; i++)
    {
        a[i] = rand() % 1000;
    }
    MergeSort(a,20000);
    int st = 0;
    for (int i = 0; i < 19998; i++)
    {
        if (a[i] > a[i + 1])
        {
            printf("%d->%d,%d\n", a[i], a[i + 1], i);
            st = 1;
            break;
        }
    }
    if (st)
    {
        printf("out of order");
    }
    else
    {
        printf("order");
    }
    return 0;
}

二.非递归

1.基础

归并是不断划分数组，直到每个数组里只有一个元素，那么我们就可以根据这个特性来进行非递归改造。

我们两个小组合并为一个大组进行循环每组里的元素个数为2*gap，例如我们从gap=1开始（模拟归并最后一层），那么下标为0和下标为1的就为一个大组，将这组里的两个元素归并（排序），赋值到tmp数组里，再将tmp拷贝到数组a里。

在这里插入图片描述

当然这只能对2，4，8…这些特殊2的指数倍个数的数组起作用（不然会发生越界），接下来就是处理边界问题。

2.改进

begin1是一大组里前面那个小组的开始位置，end1是该小组的结束位置。同理begin2是一大组里后面那个小组的开始位置，end2是该小组的结束位置。

在这里插入图片描述

#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#include<string.h>
void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc fail\n");
        return;
    }
    int gap = 1;
    while (gap < n)
    {
        for (int i = 0; i < n; i += 2 * gap)
        {
            int begin1 = i, end1 = begin1 + gap-1;
            int begin2 = i+gap, end2 = begin2 + gap-1;
            int j = begin1;
            //修正
            //第一二种情况(ps:因为begin=i，所以不可能越界)
            if (end1 >= n || begin2 >= n)
            {
                break;//如果是这种情况就说明第二个小组完全越界，没必要进行归并了，直接跳出
            }
            if (end2 >= n)//第三种情况
            {
                end2 = n - 1;
                //这说明第二组有一部分没越界，那么我们只需要拷贝这一部分
            }
            while (begin1 <= end1 && begin2 <= end2)
            {
                if (a[begin1] < a[begin2])
                    tmp[j++] = a[begin1++];
                else
                    tmp[j++] = a[begin2++];
            }
            while (begin1 <= end1) tmp[j++] = a[begin1++];
            while (begin2 <= end2) tmp[j++] = a[begin2++];
            memcpy(a + i, tmp + i, sizeof(int) *(end2-i+1));//因为如果是第三种情况，那么第二组只能拷贝一部分
        }
        gap *= 2;
    }
}
int main()
{
    int a[20000];
    srand((unsigned int)time(NULL));
    for (int i = 0; i < 20000; i++)
    {
        a[i] = rand() % 1000;
    }
    MergeSort(a, 20000);
    /*for (int i = 0; i < 4; i++)
        printf("%d ", a[i]);*/
    int st = 0;
    for (int i = 0; i < 19998; i++)
    {
        if (a[i] > a[i + 1])
        {
            printf("%d->%d,%d\n", a[i], a[i + 1], i);
            st = 1;
            break;
        }
    }
    if (st)
    {
        printf("out of order");
    }
    else
    {
        printf("order");
    }
    return 0;
}