数据结构笔记(十三)排序算法之归并排序

发布于 / 程序猿 / 0 条评论

归并排序(英文:mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(nlog n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

基础知识

归并介绍

归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

void _merge(int a[], int b[], int na, int nb, int c[]) // 两个有序数组合并
{
    int ia = 0, ib = 0, ic = 0;
    while (ia < na && ib < nb)
        a[ic++] = (a[ia] <= a[ib]) ? a[ia++] : a[ib++];
    while (ia < na)
        c[ic++] = a[ia++];
    while (ib < nb)
        c[ic++] = b[ib++];
}

排序原理

归并排序的基本思路就是将数组分成A、B两组,如果这两组组内的数据都是有序的,那么就可以很方便的将这两组数据进行排序。

如何让这两组组内数据有序?

可以将A,B组各自再分成两组。依次类推,当分出来的小组只有一个数据时,可以认为这个小组组内已经达到了有序,然后再合并相邻的两组小组就可以了。这样通过先递归的分解数列再合并数列就完成了归并排序。

其实就是三个步骤:

  • 分解:将当前区间一分为二,即求分裂点mid = (low + high)/2;
  • 求解:递归地对两个子区间a[low...mid]a[mid+1...high]进行归并排序。递归的终结条件是子区间长度为1。
  • 合并:将已排序的两个子区间a[low...mid]a[mid+1...high]归并为一个有序的区间a[low...high]

图文演示

对序列3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19进行归并排序。

  • 第一趟归并,3, 44, 38, 5归并后为3, 5, 38, 44

  • 第二趟归并,47, 15, 36归并后为15, 36, 47

  • 第三趟归并,3, 5, 38, 44, 15, 36, 47归并后为3, 5, 15, 36, 38, 44, 47

  • 第四趟归并,26, 27, 2归并后为2, 26, 27

  • 第五趟归并,46, 4, 19归并后为4, 19, 46

  • 第六趟归并,26, 27, 2, 46, 4, 19归并后为2, 4, 19, 26, 27, 46

  • 第七趟归并,3, 5, 38, 44, 15, 36, 47, 26, 27, 2, 46, 4, 19归并后为2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47

  • 维基百科图示

算法实现

  • 从上到下进行递归
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
const int maxn = 100000000;
const int Max = 30000;
int a[maxn];
int b[maxn];

void display(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << a[i] << "  ";
        if ((i+1) % 10 == 0)
            cout << endl;
    }
}

void _merge(int *a, int l, int m, int r, int tmp[]) // 合并
{
    int p = l, q = m+1;
    int k = 0;
    while (p <= m && q <= r)
        tmp[k++] = (a[p] <= a[q]) ? a[p++] : a[q++];
    while (p <= m)
        tmp[k++] = a[p++];
    while (q <= r)
        tmp[k++] = a[q++];
    for (int i = 0; i < k; ++i) // 重新赋值到原数组
        a[l+i] = tmp[i];
}

void merge_sort(int a[], int low, int high, int tmp[])
{
    if (low >= high)
        return ;
    int mid = (low + high) >> 1;
    merge_sort(a, low, mid, tmp); // 左递归
    merge_sort(a, mid+1, high, tmp); // 右递归
    _merge(a, low, mid, high, tmp); // 合并 
}

void getTime(void f(int [], int, int, int []), int a[], int low, int high, int tmp[])
{
    clock_t _start, _end;
    _start = clock();
    f(a, low, high, tmp);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;
}

int main()
{
    srand((unsigned)time(NULL)); // 设置随机数种子
    for (int i = 0; i < maxn; ++i)
        a[i] = rand() % Max;
    // display(a, maxn);
    int *tmp = new int [maxn];
    getTime(merge_sort, a, 0, maxn-1, tmp);
    // display(a, maxn);
    delete[] tmp;
    return 0;
}
  • 实测不同规模序列程序运行时间。
对于30000以内的数
当 maxn = 10000     时,时间为 0s
当 maxn = 100000    时,时间为 0.031s
当 maxn = 1000000   时,时间为 0.25s
当 maxn = 10000000  时,时间为 2.245s
当 maxn = 100000000 时,时间为 24.975s

算法分析

  • 时间复杂度

归并排序的时间复杂度是O(N*logN)
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N),总共需要遍历logN次。归并排序的形式就是一棵二叉树,它需要遍历的次数就是二叉树的深度,所以出它的时间复杂度是O(N*logN)

  • 稳定性

归并排序是一种稳定的排序。

注意归并排序的时间复杂度无论是在最好情况下还是在最坏情况下均是O(N*logN)

  • 空间复杂度

归并排序需要一个辅助空间来暂存两有序序列归并的结果,故其辅助空间复杂度为O(n)它不是就地排序


说明

文中基础知识和理论分析部分来源于skywang12345大牛的归并排序,和MoreWindows大牛的白话经典算法系列之五 归并排序的实现,强烈推荐。

The end.
2017-12-30 星期六

转载原创文章请注明,转载自: 太傅亭 » 数据结构笔记(十三)排序算法之归并排序
Not Comment Found