1 前言
写 js数据结构与算法 系列用的语言是javascript , 初衷在于入门数据结构与算法和方便以后复习。
这篇文章主要讲述归并排序的一些例子、复杂度分析、动画、还有算法可视化工具。
2 归并排序思想介绍
2.1 原理:
排序一个数组,先将数组均分成两份的方式拆分为最小份,每份剩一个值,再将份进行比较,按照大小合并至一个数组。
2.2 运行过程分为两步:
- 自上而下的递归
- 自下而上的迭代
2.3 递归拆分数组:
2.4 迭代法将数组合并:
举个小例子:迭代法将数组合并时的比较,相当于两队人马的擂台比武,两队分别为A队和B队,A队和B队各上场一人比武,A队的输了,换A队的下一个人上场再和B队的这个人的比,就这样一直比,就会排出每个人的名次。
3 javascript实现归并排序:
3.1 第一步:递归来实现拆分元素
function mergingSort(arr) { let len = arr.length; if (len < 2) return arr; let mid = len >> 1; // len>>1,相当于Math.floor(len/2); let arr1 = arr.slice(0, mid); let arr2 = arr.slice(mid); return merge(mergingSort(arr1), mergingSort(arr2)) } let tag = 1; function merge(arr1, arr2) { console.log("tag" + tag + "=", arr1, arr2); tag++; }
执行结果:
拆分成功,这个方法将数组拆分成单个数组
3.2 第二步:迭代方法排序数组并合并
function mergingSort(arr) { let len = arr.length; if (len < 2) return arr; let mid = len >> 1; // len>>1,相当于Math.floor(len/2); let arr1 = arr.slice(0, mid); let arr2 = arr.slice(mid); console.log("mid-------", mid, arr1, arr2) return merge(mergingSort(arr1), mergingSort(arr2)) } let tag = 1; function merge(arr1, arr2) { console.log("tag" + tag + "=", arr1, arr2); tag++; let result = []; while (arr1.length && arr2.length) { //选取两个序列中的较小值放入新数组 if (arr1[0] <= arr2[0]) { result.push(arr1.shift()) } else { result.push(arr2.shift()) } } while (arr1.length > 0) { //序列1中多余的元素移入新数组 result.push(arr1.shift()) } while (arr2.length) { //序列2中多余的元素移入新数组 result.push(arr2.shift()) } console.log("return merge----------", result) return result; } mergingSort([3, 2, 4, 5, 1]);
执行结果及执行过程:
解:拦截了middle截取值的结果,merge方法传入值tag和每次merge方法运行返回值return merge,运行规律总结为:
- 先拆分2份,将第一份拆解完成,再拆解第二份,以此类推
- 拆到只剩一个值时运行merge函数根据大小合并
- 两两合并完再合并4个,直到全部合并完
3.3 动画效果描述过程:
4 归并排序时间复杂度、空间复杂度、稳定性
复杂度分析是整个算法学习的精髓。
- 时间复杂度: 一个算法执行所耗费的时间。
- 空间复杂度: 运行完一个程序所需内存的大小。
我们除了学习算法原理和实现之外,更重要的是学会如何评价、分析一个排序算法。
4.1 执行效率
从效率上看,归并排序可算是排序算法中的佼佼者
。假设数组长度为 n,那么拆分数组共需 logn 步,又每步都是一个普通的合并子数组的过程,时间复杂度为 O(n),故其综合时间复杂度为 O(n log n)。
最佳情况:T(n) = O(n log n)。
最差情况:T(n) = O(n log n)。
平均情况:T(n) = O(n log n)。
4.2 内存消耗
这是因为归并排序的合并函数,在合并两个有序数组为一个有序数组时,需要借助额外的存储空间。
实际上,尽管每次合并操作都需要申请额外的内存空间,但在合并完成之后,临时开辟的内存空间就被释放掉了。在任意时刻,CPU 只会有一个函数在执行,也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小,所以空间复杂度是 O(n)。
所以,归并排序不是
原地排序算法。
4.3 稳定性
merge 方法里面的 left[0] <= right[0] ,保证了值相同的元素,在合并前后的先后顺序不变。归并排序是稳定
的排序方法。
转载请注明:流年似水 » js数据结构与算法-归并排序
Warning: copy(https://cn.gravatar.com/avatar/92de644add16aea9a83dd15bea501268?s=54&d=%2Fwp-content%2Fthemes%2Fyusi1.0%2Fimg%2Fdefault.png&r=g): failed to open stream: HTTP request failed! HTTP/1.1 400 Bad Request in /usr/share/nginx/html/timewentby/wp-content/themes/yusi1.0/functions.php on line 239