经典算法之归并排序

算法

字数统计: 686阅读时长: 3 min

 2018/06/07   Share

前言

归并排序是种独立的排序，它通过分治法的思想的排序数组。将数组分治为有序的子序列，最后合并每个子序列，完成排序。
归并排序的时间复杂度同快速排序一致，为O(N*logN)，空间复杂度上归并排序则稳定为O(n)来存储临时数组。

实现

要理解归并排序，需要先理解如何合并两个有序序列。
假设有以下有序序列：

0	1	2	3	4	5
3	34	54	14	23	41

先将序列对半分，分为3，34，54和14，23，41两组有序序列，比较两组序列的第一个数，哪个小就将其放在临时数组中，这里3小于14，便将3放在临时数组中，现在变成了如下序列

接着比较34与14，将14放在临时数组中，以此类推，直到两个序列都放入了临时数组。由此写出代码：

void MemeryArray(int a[], int n, int b[], int m, int c[])  
{  
    int i, j, k;  
  
    i = j = k = 0;  
    while (i < n && j < m)  //将小的数放入临时数组
    {  
        if (a[i] < b[j])  
            c[k++] = a[i++];  
        else  
            c[k++] = b[j++];   
    }  
  
    while (i < n)   //若两个序列长度不同，则比较完成后直接将有序序列的数依次放入临时数组，下同
        c[k++] = a[i++];  
  
    while (j < m)  
        c[k++] = b[j++];  
}

那问题就来了，我们怎么得到两个有序序列来使它们合并呢？我们可以将数组一直二分，直到序列中只有一个数，便可以得到一个数的有序序列。简而言之，先使用递归拆分序列，再合并序列。如此便实现了归并排序。

void MergeArray(int a[],int first,int mid,int last,int temp[])
{
    int i = first, j = mid + 1;  
    int m = mid,   n = last;  
    int k = 0;  
      
    while (i <= m && j <= n)  
    {  
        if (a[i] <= a[j])  
            temp[k++] = a[i++];  
        else  
            temp[k++] = a[j++];  
    }  
      
    while (i <= m)  
        temp[k++] = a[i++];  
      
    while (j <= n)  
        temp[k++] = a[j++];  
      
    for (i = 0; i < k; i++)  
        a[first + i] = temp[i]; 
}

void MergeSort(int a[], int first, int last, int temp[])  
{  
    if (first < last)  
    {  
        int mid = (first + last) / 2;  
        mergesort(a, first, mid, temp);  //递归，使左边序列有序
        mergesort(a, mid + 1, last, temp); //使右边序列有序
        mergearray(a, first, mid, last, temp); //合并两个有序序列
    }  
}

归并排序效率还是比较高的，但速度上快速排序仍比归并排序来的快。笔者在自己电脑上进行测试： 20000个随机数： ![](https://zer0blog.oss-cn-hangzhou.aliyuncs.com/blog_image/mergesort/merge3.png) 50000个随机数： ![](https://zer0blog.oss-cn-hangzhou.aliyuncs.com/blog_image/mergesort/merge5.png) 100000个随机数： ![](https://zer0blog.oss-cn-hangzhou.aliyuncs.com/blog_image/mergesort/merge2.png) 500000个随机数： ![](https://zer0blog.oss-cn-hangzhou.aliyuncs.com/blog_image/mergesort/merge4.png)

原文作者：Zer0e

原文链接：https://re0.top/2018/06/07/mergesort/

发表日期：六月 7日 2018, 8:22:00 晚上

更新日期：November 14th 2018, 5:37:31 pm

Next Post

浅谈CSP内容安全策略
Previous Post

经典算法之快速排序

CATALOG

1. 前言
2. 实现

