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数据结构与算法-归并排序