归并排序--C语言

百度百科这样解释：归并排序：（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表。

思想如图所示：1.L1 = 0；

                         2.H1 = L1 + 1;

                         3.L2 = H1 + 1;

                         4.H2 = L2 + width -1；（L2 + width < len）

#include<stdio.h>
#include<stdlib.h>返回
旧版 返回
旧版
#include<assert.h>
#include<malloc.h>
#include<time.h>

/*
采用分治策略
时间复杂度：O(nlogn)，一次归并耗时O(n),总共O(logn)次，
空间复杂度：O(n),重新开辟空间n个空间
稳定性：稳定
*/
#define Length 10

//根据宽度，一次归并
void Merger(int arr[], int len, int width)
{
    //开辟内存空间
    int *brr = (int*)malloc(sizeof(int) * len);
    if (brr == NULL) exit(0);
    //四个标记位
    int low1 = 0;
    int high1 = low1 + width - 1;
    int low2 = high1 + 1;
    int high2 = low2 + width > len ? len - 1 : low2 + width - 1;
    //计数器
    int count = 0;

    while (low2 < len)
    {
        //有两个归并段，都有数据
        while (low1 <= high1 && low2 <= high2)
        {
            if (arr[low1] < arr[low2])
            {
                brr[count++] = arr[low1++];
            }
            else
            {
                brr[count++] = arr[low2++];
            }
        }
        //一个归并段有数据，另一个没有
        while (low1 <= high1)
        {
            brr[count++] = arr[low1++];
        }
        while (low2 <= high2)
        {
            brr[count++] = arr[low2++];
        }

        low1 = high2 + 1;
        high1 = low1 + width > len ? len - 1 : low1 + width - 1;
        low2 = high1 + 1;
        high2 = low2 + width > len ? len - 1 : low2 + width - 1;//防止越界
    }
    //只有一个归并段
    while (low1 < len)
    {
        brr[count++] = arr[low1++];
    }

    for (int i = 0; i < len; i++)
    {
        arr[i] = brr[i];
    }
    free(brr);

}

//归并排序次数

void Merger_Sort(int arr[], int len)
{
    for (int i = 1; i < len; i *= 2)//i表示宽度，所以i从1开始
    {
        Merger(arr, len, i);
    }
}

void Show(int arr[], int len)
{
    for (int i = 0; i < len; i++)
    {
        printf(" %d ", arr[i]);
    }
    printf("\n");
}

int main()
{
    srand((unsigned int)time(NULL));//随机函数
    int arr[Length] = { 0 };
    int i = 0;
    for (i = 0; i < Length; i++)
    {
        arr[i] = rand() % 100;
    }

    Show(arr, Length);
    Merger_Sort(arr, Length);
    Show(arr, Length);

    return 0;
}