归并排序

目录

一、 一趟归并

二、 归并排序

三、 复杂度分析

四、 运行结果

---

一、 一趟归并

    int b1 = 0;
    int e1 = b1 + gap - 1;    //前一个区间一定能完整
    int b2 = e1 + 1;
    int e2 = b2 + gap - 1 > n-1 ? n-1 : b2 + gap-1;    //后一个区间可能只有一部分

完整代码：

#include<stdio.h>   //printf()
#include<malloc.h>  //malloc()
#include<assert.h>  //assert()

void OnePassMerge(int *arr, int n, int gap)    //二路一趟归并
{
    int b1 = 0;
    int e1 = b1 + gap - 1;    //前一个区间一定能完整
    int b2 = e1 + 1;
    int e2 = b2 + gap - 1 > n-1 ? n-1 : b2 + gap-1;    //后一个区间可能只有一部分

    int *temp = (int*)calloc(2*gap, sizeof(int));
    assert(NULL != temp);
    while(b1 < n)
    {
        int k = b1;    //记下起始位置
        int cnt = 0;
        while(b1 <= e1 && b2 <= e2)
        {
            if(arr[b1] < arr[b2])
            {
                temp[cnt++] = arr[b1++];
            }
            else
            {
                temp[cnt++] = arr[b2++];
            }
        }

        while(b1 <= e1)    //前一个区间剩下的添上
        {
            temp[cnt++] = arr[b1++];
        }
        while(b2 <= e2)    //后一个区间剩下的添上
        {
            temp[cnt++] = arr[b2++];
        }

        for(int i = 0; i < cnt; ++i)    //将临时数组中排序好的值放回原数组中
        {
            arr[k + i] = temp[i];
        }

        //下一对需要进行归并的子数组
        b1 = e2 + 1;
        e1 = b1 + gap-1 > n-1 ? n-1 : b1 + gap-1;
        b2 = e1 + 1;
        e2 = b2 + gap-1 > n-1 ? n-1 : b2 + gap-1;
    }
    free(temp);        //一趟归并完成，释放临时申请的空间
}

---

二、 归并排序

void MergeSort(int *arr, int n)
{
    assert(NULL != arr);
    for(int i = 1; i < n; i *= 2)
    {
        OnePassMerge(arr, n, i);
    }
}

---

三、 复杂度分析

---

四、 运行结果

void print(int *arr, int n)
{
    assert(NULL != arr);
    for(int i = 0; i < n; ++i)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main()
{
    int arr[] = {90, 80, 70, 60, 50, 40, 30, 20, 10, 9, 8};
    int n = sizeof(arr)/sizeof(arr[0]);
    MergeSort(arr, n);
    print(arr, n);
    return 0;
}