归并排序

归并排序是一种分治策略的排序算法。它是一种比较特殊的排序算法，通过递归地先使每个子序列有序，再将两个有序的序列进行合并成一个有序的序列。

John_von_Neumann1945EDVAC

一、算法介绍

我们先介绍两个有序的数组合并成一个有序数组的操作。

  1. 先申请一个辅助数组，长度等于两个有序数组长度的和。
  2. 从两个有序数组的第一位开始，比较两个元素，哪个数组的元素更小，那么该元素添加进辅助数组，然后该数组的元素变更为下一位，继续重复这个操作，直至数组没有元素。
  3. 返回辅助数组。

举一个例子：

nn
O(n)n
O(n)n

正是利用这个特点，归并排序先排序较小的数组，再将有序的小数组合并形成更大有序的数组。

归并排序有两种递归做法，一种是自顶向下，一种是自底向上。

1.1. 自顶向下归并排序

从一个大数组开始，不断地往下切分，如图：

从上往下进行递归，直到切分的小数组无法切分了，然后不断地对这些有序数组进行合并。

O(n)T(n)=2T(n/2)+O(n)O(nlogn)
lognO(logn)log(100 0000 0000)=29.89730

1.2. 自底向上归并排序

从小数组开始排序，不断地合并形成更大的有序数组。

O(nlogn)
O(1)

二、算法实现

自顶向下的归并排序递归实现：

输出：

nlogn

自底向上的非递归实现：

输出：

自底向上非递归排序，我们可以看到没有递归那样程序栈的增加，效率比自顶向上的递归版本高

三、算法改进

归并排序归并操作占用了额外的辅助数组，且归并操作是从一个元素的数组开始。

我们可以做两点改进：

  1. 对于小规模数组，使用直接插入排序。
  2. 原地排序，节约掉辅助数组空间的占用。

我们建议使用自底向上非递归排序，不会有程序栈空间损耗。

[9,8,7,1,2,3][1,2,3,9,8,7]
abcde123456751234567abcde

如何翻转呢？

  1. 将前部分逆序
  2. 将后部分逆序
  3. 对整体逆序

示例如下：

归并原地排序利用了手摇算法的特征，不需要额外的辅助数组。

arr[begin,mid-1]，arr[mid,end]i=beginj=midk=endi~jk~j
iarr[i]>arr[j]ibegin~in
jarr[j]>arr[i]
mid~jarr[i]begin~inbegin~i，mid~j
i~midmid,j-1

具体的代码如下：

输出：

blockSize

归并过程中，使用原地归并，用了手摇算法，代码如下：

O(n)O(1)

归并排序是唯一一个有稳定性保证的高级排序算法，某些时候，为了寻求大规模数据下排序前后，相同元素位置不变，可以使用归并排序。

系列文章入口

我是陈星星，欢迎阅读我亲自写的 数据结构和算法(Golang实现)，文章首发于

目录 · 数据结构和算法（Golang实现）​goa.lenggirl.com
  • 数据结构和算法(Golang实现)(1)简单入门Golang-前言
  • 数据结构和算法(Golang实现)(2)简单入门Golang-包、变量和函数
  • 数据结构和算法(Golang实现)(3)简单入门Golang-流程控制语句
  • 数据结构和算法(Golang实现)(4)简单入门Golang-结构体和方法
  • 数据结构和算法(Golang实现)(5)简单入门Golang-接口
  • 数据结构和算法(Golang实现)(6)简单入门Golang-并发、协程和信道
  • 数据结构和算法(Golang实现)(7)简单入门Golang-标准库
  • 数据结构和算法(Golang实现)(8.1)基础知识-前言
  • 数据结构和算法(Golang实现)(8.2)基础知识-分治法和递归
  • 数据结构和算法(Golang实现)(9)基础知识-算法复杂度及渐进符号
  • 数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
  • 数据结构和算法(Golang实现)(11)常见数据结构-前言
  • 数据结构和算法(Golang实现)(12)常见数据结构-链表
  • 数据结构和算法(Golang实现)(13)常见数据结构-可变长数组
  • 数据结构和算法(Golang实现)(14)常见数据结构-栈和队列
  • 数据结构和算法(Golang实现)(15)常见数据结构-列表
  • 数据结构和算法(Golang实现)(16)常见数据结构-字典
  • 数据结构和算法(Golang实现)(17)常见数据结构-树
  • 数据结构和算法(Golang实现)(18)排序算法-前言
  • 数据结构和算法(Golang实现)(19)排序算法-冒泡排序
  • 数据结构和算法(Golang实现)(20)排序算法-选择排序
  • 数据结构和算法(Golang实现)(21)排序算法-插入排序
  • 数据结构和算法(Golang实现)(22)排序算法-希尔排序
  • 数据结构和算法(Golang实现)(23)排序算法-归并排序
  • 数据结构和算法(Golang实现)(24)排序算法-优先队列及堆排序
  • 数据结构和算法(Golang实现)(25)排序算法-快速排序
  • 数据结构和算法(Golang实现)(26)查找算法-哈希表
  • 数据结构和算法(Golang实现)(27)查找算法-二叉查找树
  • 数据结构和算法(Golang实现)(28)查找算法-AVL树
  • 数据结构和算法(Golang实现)(29)查找算法-2-3树和左倾红黑树
  • 数据结构和算法(Golang实现)(30)查找算法-2-3-4树和普通红黑树