算法基础–递纳入门の归并排序

本文只是自己的笔记,并不具有过多的指导意义。
代码的初衷是便于了解,网上大神优化过的代码很多,也不建议在项目中copy本文代码。
目录
- 归并排序
- 如何合并两个有序数组
- 使两端分别有序
- 最外侧还有一个入口方法
- 图解排序过程
- 递归时间复杂度的估算
- master公式
归并排序
众所周知,分治策略中使用递归来求解问题分为三步走,分别为分解、处理和合并。
所以归并排序中心思想是通过二分的方式,将一个段数组拆分成左右两端,而后进行合并
如何合并两个有序数组
通过将最小值依次外排的方式,进行合并
- 两个指针
p1,p2指向两个数组的首位置,每次将较小的值外排进辅助数组并且右移指针。 - 当一个
指针越界后,将另一个剩余的元素放入辅助数组。 - 最后的
辅助数组将是一个有序数组。
/// 对一个数组的两个有序分段进行整合排序////// - Parameters:/// - arr: 数组/// - left: 左侧起点/// - mid: 中心点,左侧末尾/// - right: 右侧末尾func merge(arr: inout [Int] ,left: Int ,mid: Int ,right:Int) { var help : [Int] = [Int](repeating: 0, count: right-left+1) //辅助数组 var p1 = left//左侧指针 var p2 = mid+1 //右侧指针 var i = 0 //容器指针位置 while p1<=mid && p2<=right { if arr[p1] <= arr[p2] {//左侧指针位置小于等于右侧指针位置 help[i] = arr[p1] //将左侧指针位置放入辅助数组 p1 = p1+1 //左侧指针右移 }else {//右侧指针大于左侧指针位置 help[i] = arr[p2] //将右侧指针位置放入辅助数组 p2 = p2+1 //左侧指针右移 } i = i+1 //容器指针右移 } //到这里,p1,p2之中已经有一个指针越界了 //没有越界的那个,重复上面的操作写入辅助数组 while p1<=mid { help[i] = arr[p1] p1 = p1+1 i = i+1 } while p2<=right { help[i] = arr[p2] p2 = p2+1 i = i+1 } //写入完毕,用辅助数组替换进原数组 i = 0 for index in left...right { //left,left+1...right-1,right arr[index] = help[i] i = i+1 }}之所以先说这个,是由于这个方法是核心方法,并且写完滞后直接将可以测试。
测试通过之后,再去测试下面的递归方法可以更加精确确实定问题所在。
使两端分别有序
通过递归的方式,将长数组最终分解成有序的数组进行排序解决。
比方[4,2,6,1,9,7]
/// 在一个数组的某一段上进行排序////// - Parameters:/// - arr: 数组/// - left: 左侧/// - right: 右侧func mergeProcess(arr: inout [Int] ,left: Int ,right:Int) { if left==right { //左右相等,说明这次要调整的只有一个数 return } let mid = (left+right)/2 //获得中心点位置 mergeProcess(arr: &arr, left: left, right: mid)//对左半边进行排序 mergeProcess(arr: &arr, left: mid+1, right: right)//对右半边进行排序 //此时左右两侧都已经排序完成 merge(arr: &arr, left: left, mid: mid, right: right)//对左右两侧进行合并排序}最外侧还有一个入口方法
/// 归并排序////// - Parameter arr: 数组func mergeSort(arr: inout [Int]) { if arr.count<2 { return } mergeProcess(arr: &arr, left: 0, right: arr.count-1)}时间复杂度O(N * logN),额外空间复杂度O(N)。
图解排序过程

网上还看到一个动图,结合上面的应该更容易了解了。

这个过程中,不论数组多长,最后都将被划分成2个单位长度的数组进行排序。
而后向上依次合并并且排序。
这也很好的表现出了分治或者者递归的思想所在,将大样本划分成小样本并依次处理。
递归时间复杂度的估算
只说一种普遍的通用情况
master公式
T(N) = A*T(N/B) + O(N^D)当量本量为N的情况下,整个样本被划分成B样本量,共执行A次。
出去调用递归过程之外,剩下的部分的时间复杂度O(N^D)
1) log(b,a) > d -> 复杂度为O(N^log(b,a)) 2) log(b,a) = d -> 复杂度为O(N^d * logN) 3) log(b,a) < d -> 复杂度为O(N^d)以归并排序为例:
func mergeProcess(arr: inout [Int] ,left: Int ,right:Int) { if left==right { //左右相等,说明这次要调整的只有一个数 return } let mid = (left+right)/2 //获得中心点位置 mergeProcess(arr: &arr, left: left, right: mid)//T(N/2) mergeProcess(arr: &arr, left: mid+1, right: right)//T(N/2) merge(arr: &arr, left: left, mid: mid, right: right)//O(N)}有T(N) = T(N/2) + T(N/2) + O(N) = 2T(N/2) + O(N)
中A = 2,B=2,D=1
带入master公式log(b,a) = 1,与d值相等。
于是归并排序的时间复杂度为O(N * logN)。
参考资料
【图解数据结构】 一组动画演示归并排序
左神牛课网算法课
说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 算法基础–递纳入门の归并排序
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 算法基础–递纳入门の归并排序