归并排序算法介绍

归并排序（Merging Sort）就是利用归并的思想实现排序的放。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并,…..，如此重复，直到得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序。

归并排序算法图解

20180224235827721

归并排序算法代码

其实归并排序思路很好理解，就是将2个有序的序列合并，整个序列都是无序的哪里去找有序的序列？我们可以无限递归，将其划分为1个元素的序列，这时肯定是有序的咯，然后一路归并排序就ok呀。主要是合并代码，仔细看是不是应该这样去合并！

//归并排序的合并数组函数 升序
void Merge_Up(int *arr, int start, int mid, int  end, int *temp)
{
    int i_start = start;
    int i_end = mid;
    int j_start = mid + 1;
    int j_end = end;
    int length = 0;
    while (i_start <= i_end && j_start <= j_end)
    {
        //升序 我小先放我
        if (arr[i_start] < arr[j_start])
        {
            temp[length] = arr[i_start];
            length++;
            i_start++;
        }
        else
        {
            temp[length] = arr[j_start];
            length++;
            j_start++;
        }
    }
    //将剩余没有放完的放置到辅助空间中去
    while (i_start <= i_end)
    {
        temp[length] = arr[i_start];
        length++;
        i_start++;
    }
    while (j_start <= j_end)
    {
        temp[length] = arr[j_start];
        length++;
        j_start++;
    }
    //将辅助空间的值复制到源数组
    for (int i = 0; i < length; i++)
    {
        arr[start + i] = temp[i];
    }
    return;
}
/*
归并排序
    @param arr 归并排序的数组
    @param start 开始下标
    @param end 结束下标
    @param temp 辅助空间
*/
void MergeSort_Up(int *arr,int start,int end,int* temp)
{
    if (start >= end)
    {
        return;
    }
    int mid = (start + end )/ 2;
    //分组
    //左半部分 进行归并排序
    MergeSort_Up(arr, start, mid, temp);
    //右半部分 进行归并排序
    MergeSort_Up(arr, mid + 1, end, temp);
    //合并排序好的2个数组
    Merge_Up(arr, start, mid, end, temp);
}

完整代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/timeb.h>
#define MAXSIZE 1000000
//交换值
void Swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
//打印数组元素
void PrintArr(int* arr, int length)
{
    for (int i = 0; i < length; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return;
}
long GetSysTime()
{
    struct timeb tb;
    ftime(&tb);
    return tb.time * 1000 + tb.millitm;
}
//归并排序的合并数组函数 降序
void Merge_Down(int *arr, int start, int mid, int  end, int *temp)
{
    int i_start = start;
    int i_end = mid;
    int j_start = mid + 1;
    int j_end = end;
    int length = 0;
    //只有 1个元素时肯定是有序的，做为递归函数的出口。
    if (start >= end)
    {
        return;
    }
    while (i_start <= i_end && j_start <= j_end)
    {
        //降序 我大先放我
        if (arr[i_start] > arr[j_start])
        {
            temp[length] = arr[i_start];
            length++;
            i_start++;
        }
        else
        {
            temp[length] = arr[j_start];
            length++;
            j_start++;
        }
    }
    //将辅助空间的值复制到源数组
    for (int i = 0; i < length; i++)
    {
        arr[start + i] = temp[i];
    }
}
//归并排序的合并数组函数 升序
void Merge_Up(int *arr, int start, int mid, int  end, int *temp)
{
    int i_start = start;
    int i_end = mid;
    int j_start = mid + 1;
    int j_end = end;
    int length = 0;
    while (i_start <= i_end && j_start <= j_end)
    {
        //升序 我小先放我
        if (arr[i_start] < arr[j_start])
        {
            temp[length] = arr[i_start];
            length++;
            i_start++;
        }
        else
        {
            temp[length] = arr[j_start];
            length++;
            j_start++;
        }
    }
    //将剩余没有放完的放置到辅助空间中去
    while (i_start <= i_end)
    {
        temp[length] = arr[i_start];
        length++;
        i_start++;
    }
    while (j_start <= j_end)
    {
        temp[length] = arr[j_start];
        length++;
        j_start++;
    }
    //将辅助空间的值复制到源数组
    for (int i = 0; i < length; i++)
    {
        arr[start + i] = temp[i];
    }
    return;
}
/*
归并排序
    @param arr 归并排序的数组
    @param start 开始下标
    @param end 结束下标
    @param temp 辅助空间
*/
void MergeSort_Up(int *arr,int start,int end,int* temp)
{
    if (start >= end)
    {
        return;
    }
    int mid = (start + end )/ 2;
    //分组
    //左半部分 进行归并排序
    MergeSort_Up(arr, start, mid, temp);
    //右半部分 进行归并排序
    MergeSort_Up(arr, mid + 1, end, temp);
    //合并排序好的2个数组
    Merge_Up(arr, start, mid, end, temp);
}
int main(int argc, char *argv[])
{
    srand((size_t)time(NULL));//设置随机种子
    int arr[10] = { 6,8,2,3,9,7,4,1,5,10 };
    int *arr2 = (int*)malloc(sizeof(int)*MAXSIZE);
    //int *arr3 = (int*)malloc(sizeof(int)*MAXSIZE);
    //给每个元素设置一个随机值
    for (int i = 0; i < MAXSIZE; i++)
    {
        int num = rand() % MAXSIZE;
        arr2[i] = num;
        //arr3[i] = num;
    }
    int *temp = (int*)malloc(sizeof(int)*10);
    int *temp1 = (int*)malloc(sizeof(int) * MAXSIZE);
    printf("排序前：\n");
    PrintArr(arr, 10);
    MergeSort_Up(arr, 0, 9, temp);
    printf("归并排序升序：\n");
    PrintArr(arr, 10);
    long start = GetSysTime();
    MergeSort_Up(arr2, 0, MAXSIZE - 1, temp1);
    long end = GetSysTime();
    printf("%d个元素 归并排序耗费%d毫秒\n",MAXSIZE,end-start);
    return 0;
}