数据结构和算法(Golang实现)(23)排序算法-归并排序
2021-02-13 15:22
标签：UNC 物理 空间复杂度 数据结构 -- 赋值 语句 lan 基础知识 归并排序是一种分治策略的排序算法。它是一种比较特殊的排序算法，通过递归地先使每个子序列有序，再将两个有序的序列进行合并成一个有序的序列。 归并排序首先由著名的现代计算机之父 我们先介绍两个有序的数组合并成一个有序数组的操作。 举一个例子： 将两个有序数组进行合并，最多进行 归并操作最坏的时间复杂度为： 归并操作最好的时间复杂度为： 正是利用这个特点，归并排序先排序较小的数组，再将有序的小数组合并形成更大有序的数组。 归并排序有两种递归做法，一种是自顶向下，一种是自底向上。 从一个大数组开始，不断地往下切分，如图： 从上往下进行递归，直到切分的小数组无法切分了，然后不断地对这些有序数组进行合并。 每次都是一分为二，特别均匀，所以最差和最坏时间复杂度都一样。归并操作的时间复杂度为： 因为不断地递归，程序栈层数会有 从小数组开始排序，不断地合并形成更大的有序数组。 时间复杂度和自顶向上归并排序一样，也都是 因为不需要使用递归，没有程序栈占用，因此递归栈的空间复杂度为： 自顶向下的归并排序递归实现： 输出： 自顶向下递归排序，我们可以看到每次合并都要申请一个辅助数组，然后合并完再赋值回原数组，这样每次合并后辅助数组的内存就可以释放掉，存储空间占用 自底向上的非递归实现： 输出： 自底向上非递归排序，我们可以看到没有递归那样程序栈的增加，效率比自顶向上的递归版本高 归并排序归并操作占用了额外的辅助数组，且归并操作是从一个元素的数组开始。 我们可以做两点改进： 我们建议使用自底向上非递归排序，不会有程序栈空间损耗。 我们先来介绍一种翻转算法，也叫手摇算法，主要用来对数组两部分进行位置互换，比如数组： 再比如，将字符串 如何翻转呢？ 示例如下： 归并原地排序利用了手摇算法的特征，不需要额外的辅助数组。 首先，两个有序的数组，分别是 将 然后将 这个时候， 我们只需进行翻转，将 具体的代码如下： 输出： 我们自底开始，将元素按照数量为 归并过程中，使用原地归并，用了手摇算法，代码如下： 因为手摇只多了逆序翻转的操作，时间复杂度是 归并排序是唯一一个有稳定性保证的高级排序算法，某些时候，为了寻求大规模数据下排序前后，相同元素位置不变，可以使用归并排序。 我是陈星星，欢迎阅读我亲自写的 数据结构和算法(Golang实现)，文章首发于 阅读更友好的GitBook。 数据结构和算法(Golang实现)(23)排序算法-归并排序 标签：UNC 物理 空间复杂度 数据结构 -- 赋值 语句 lan 基础知识 原文地址：https://www.cnblogs.com/nima/p/12724860.html归并排序
John_von_Neumann在1945年发明，被用在了EDVAC(一台美国早期电子计算机)，足足用墨水写了 23 页的排序程序。注：冯·诺依曼（John von Neumann，1903年12月28日-1957年2月8日），美籍匈牙利数学家、计算机科学家、物理学家，是20世纪最重要的数学家之一。一、算法介绍
有序数组A：[3 8 9 11 13]
有序数组B：[1 5 8 10 17 19 20 23]
[] 表示比较的范围。
因为 1 n次比较就可以生成一个新的有序数组，n是两个数组长度较大的那个。O(n)，其中n是较长数组的长度。O(n)，其中n是较短数组的长度。1.1. 自顶向下归并排序
O(n)，因此总的时间复杂度为：T(n)=2T(n/2)+O(n)，根据主定理公式可以知道时间复杂度为：O(nlogn)。我们可以自己计算一下：归并排序，每次归并操作比较的次数为两个有序数组的长度： n/2
T(n) = 2*T(n/2) + n/2
T(n/2) = 2*T(n/4) + n/4
T(n/4) = 2*T(n/8) + n/8
T(n/8) = 2*T(n/16) + n/16
...
T(4) = 2*T(2) + 4
T(2) = 2*T(1) + 2
T(1) = 1
进行合并也就是：
T(n) = 2*T(n/2) + n/2
= 2^2*T(n/4)+ n/2 + n/2
= 2^3*T(n/8) + n/2 + n/2 + n/2
= 2^4*T(n/16) + n/2 + n/2 + n/2 + n/2
= ...
= 2^logn*T(1) + logn * n/2
= 2^logn + 1/2*nlogn
= n + 1/2*nlogn
因为当问题规模 n 趋于无穷大时 nlogn 比 n 大，所以 T(n) = O(nlogn)。
因此时间复杂度为：O(nlogn)。
logn层，所以递归栈的空间复杂度为：O(logn)，对于排序十亿个整数，也只要：log(100 0000 0000)=29.897，占用的堆栈层数最多30层忧。1.2. 自底向上归并排序
O(nlogn)。O(1)。二、算法实现
package main
import "fmt"
// 自顶向下归并排序，排序范围在 [begin,end) 的数组
func MergeSort(array []int, begin int, end int) {
// 元素数量大于1时才进入递归
if end-begin > 1 {
// 将数组一分为二，分为 array[begin,mid) 和 array[mid,high)
mid := begin + (end-begin+1)/2
// 先将左边排序好
MergeSort(array, begin, mid)
// 再将右边排序好
MergeSort(array, mid, end)
// 两个有序数组进行合并
merge(array, begin, mid, end)
}
}
// 归并操作
func merge(array []int, begin int, mid int, end int) {
// 申请额外的空间来合并两个有序数组，这两个数组是 array[begin,mid),array[mid,end)
leftSize := mid - begin // 左边数组的长度
rightSize := end - mid // 右边数组的长度
newSize := leftSize + rightSize // 辅助数组的长度
result := make([]int, 0, newSize)
l, r := 0, 0
for l [5]
[5 9]
[1 3 4 5 6 6 6 8 9 14 25 49]
n，而程序递归栈依旧是logn层。package main
import "fmt"
// 自底向上归并排序
func MergeSort2(array []int, begin, end int) {
// 步数为1开始，step长度的数组表示一个有序的数组
step := 1
// 范围大于 step 的数组才可以进入归并
for end-begin > step {
// 从头到尾对数组进行归并操作
// step end {
return
}
// 第二个数组长度不够
if hi > end {
hi = end
}
// 两个有序数组进行合并
merge(array, lo, mid, hi)
}
// 上面的 step 长度的两个数组都归并成一个数组了，现在步长翻倍
step [5]
[5 9]
[1 3 4 5 6 6 6 8 9 14 25 49]
三、算法改进
[9,8,7,1,2,3]，将前三个元素与后面的三个元素交换位置，变成[1,2,3,9,8,7]。abcde1234567的前5个字符与后面的字符交换位置，那么手摇后变成：1234567abcde。
翻转 [1234567abcde] 的前5个字符。
1. 分成两部分：[abcde][1234567]
2. 分别逆序变成：[edcba][7654321]
3. 整体逆序：[1234567abcde]
arr[begin,mid-1]，arr[mid,end]，此时初始化i=begin，j=mid，k=end，从i~j为左有序的数组，k~j为右有序的数组，如图：
i向后移动，找到第一个arr[i]>arr[j]的索引，这个时候，i前面的部分已经排好序了，begin~i这些元素已经是两个有序数组的前n小个元素。如图：
j向后移动，找到第一个arr[j]>arr[i]的索引，如图：
mid~j中的元素都小于arr[i]，前面已经知道从begin~i已经是前n小了，所以这两部分begin~i，mid~j也是有序的了，我们要想办法将这两部分连接在一起。i~mid和mid,j-1部分进行位置互换即可，我们可以用手摇算法。package main
import "fmt"
func InsertSort(list []int) {
n := len(list)
// 进行 N-1 轮迭代
for i := 1; i = 0 && deal 0 && k-j >= 0 {
step := 0
// 从 i 向右移动，找到第一个 array[i]>array[j]的索引
for j-i > 0 && array[i] array[i]的索引
for k-j >= 0 && array[j] [5]
[5 9]
[1 3 4 5 6 6 6 8 9 14 25 49]
[1 1 2 2 2 3 4 4 4 5 5 6 6 6 7 8 9 9 14 21 24 24 25 34 45 49 56 56 67]
blockSize进行小数组排序，使用直接插入排序，然后我们对这些有序的数组向上进行归并操作。func rotation(array []int, l, mid, r int) {
reverse(array, l, mid-1)
reverse(array, mid, r)
reverse(array, l, r)
}
O(n)，虽然时间复杂度稍稍多了一点，但存储空间复杂度降为了O(1)。系列文章入口
上一篇：Python-爬取斗图啦网站
文章标题：数据结构和算法(Golang实现)(23)排序算法-归并排序
文章链接：http://soscw.com/essay/54900.html