JavaScript经典排序算法——归并排序

柔情只为你懂 2022-05-26 12:10 239阅读 0赞

“归并”的意思是将两个或两个以上的有序表组合成一个新的有序表。假如初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到\[n/2\]（向上取整）个长度为2或1的有序子序列；再两两归并，……，如此重复，直到得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。

#  #

# 步骤解析： #

1、把长度为n的输入序列分成两个长度为n/2的子序列；

2、对这两个子序列继续分为m/2的子序列，一直分下去，直为1个元素；

3、将两个排序好的子序列合并成一个最终的排序序列。

# 特点： #

速度仅次于快速排序，为稳定排序算法，一般用于总体无序，但是各子项相对有序的数列，属于分治思想，递归归并。

# 动图演示： #

![20180502102359525][]

# **JavsScript代码实现：** #

//归并排序
    function mergeSort(arr){
      var len = arr.length;
      if(len < 2){
        return arr;
      }
      //首先将无序数组划分为两个数组
      var mid = Math.floor(len / 2);
      var left = arr.slice(0,mid);
      var right = arr.slice(mid,len);
      return merge(mergeSort(left),mergeSort(right));//递归分别对左右两部分数组进行排序合并
    }
    //合并
    function merge(left,right){
      var result = [];
      while(left.length>0 && right.length>0){
        if(left[0]<=right[0]){
          //如果左边的数据小于右边的数据，将左边数据取出，放在新数组中
           result.push(left.shift());
        }else{
           result.push(right.shift());
        }
      }
      while(left.length){
         result.push(left.shift());
      }
      while(right.length){
         result.push(right.shift());
      }
      return result;
    }
    var arr = [3,44,38,5,47,15,36,26];
    console.log(mergeSort(arr));//3,5,15,26,36,38,44,47

[20180502102359525]: /images/20220526/1a7a0a8ec09f40cc800001ac52b88ec0.png