排序算法: 归并排序

dbhllnr

2020-02-18

归并排序

1. 算法推导

对一个等待排序的数组A，以及排序函数sort，以及合并两个有序数组的函数merge。则 sort(A) = merge(sort(A1), sort(A2))，上面这个推导公式看起来是满足递归算法的重复条件。举个例子：

function sort(arr) {}
function merge(arr1, arr2) {}

// sort 的终止条件为数组arr长度为1
sort([1, 3, 9, 4]) = merge(sort([1, 3]), sort([9, 4]))
sort([1, 3, 9, 4]) = merge(
  sort(merge(sort([1], sort[2]))),
  sort(merge(sort([9], sort[4]))),
)

2. 代码实现

2.1 递归实现

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="utf-8">
  <title>归并排序</title>
</head>

<body>
  <script>
    /**
     * 将两个排好序的数组合并成一个新数组
     * 时间复杂度 O(n)
     */
    function merge(lArr, rArr) {
      var result = []
      while(lArr.length > 0 && rArr.length > 0) {
        if (lArr[0] < rArr[0]) {
          result.push(lArr.shift())
        } else {
          result.push(rArr.shift());
        }
      }
      // 剩下的也要合并进去
      result = result.concat(lArr).concat(rArr);
      return result;
    }

    function msort(arr) {
      // 递归排序的终止条件是，当前这个数组的长度为1，因为只有一个，那么肯定是排好序的
      if (arr.length === 1) {
        return arr 
      }

      // 当然你可以将终止条件改为数组长度为2, 但是要确保返回的数组是有序的
      // if (arr.length === 2) {
      //   if (arr[0] > arr[1]) {
      //     var t = arr[1]
      //     arr[1] = arr[0]
      //     arr[0] = t;
      //   }
      //   return arr
      // }

      // 分割成两个数组
      var middle = Math.floor(arr.length / 2); 
      var lArr = arr.slice(0, middle);
      var rArr = arr.slice(middle);

      // 这两个数组如何排序, merge也是排序函数
      return merge(msort(lArr), msort(rArr))
    }

    var items = [9, 7, 3, 5]
    var res = msort(items)
    console.log(res)
  </script>
</body>

</html>

2.2 非递归实现

2.2.1 自己实现

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="utf-8">
  <title>归并排序</title>
</head>

<body>
  <script>
    function merge_pass(arr, temp, l, m, r) {
        let lEnd = m - 1;
        let pos = l;
        while(l <= lEnd && m < r) {
            if (arr[l] > arr[m]) {
                temp[pos] = arr[m];
                m++;
                pos++;
            } else {
                temp[pos] = arr[l];
                l++;
                pos++;
            }
        }
        while (l > lEnd && m < r) {
            temp[pos] = arr[m++];
            pos++;
        }
        while (l <= lEnd && m >= r) {
            temp[pos] = arr[l++];
            pos++;
        }
    }

        function merge_sort(arr) {
            let temp = [];
            let N = arr.length;
            let length = 1; // 子序列长度, 默认为1
            let t; // 迭代次数

            for(t = 0; Math.pow(2, t) < N;) {
                // 将当前的分组各自排序
                let l;
                let guard = t % 2 === 0;
                for(l = 0; l < N; l += length * 2) {
                    // l 为左侧数组的起始位置
                    // r 为右侧数组的边际
                    let r = (l + 2 * length) > N ? N : (l + 2 * length);
                    let m = (l + length) > N ? N : (l + length);
                    merge_pass(
                        guard ? arr : temp,
                        guard ? temp : arr,
                        l, m, r
                    );
                }

                // 下一轮比较
                length = 2 * length;
                t++;
            }

            if (t % 2 === 0) {
                return arr
            }
            return temp
        }

    var arr = [9, 7, 3, 5, 4]
    var res = merge_sort(arr)
    console.log(res)
  </script>
</body>

</html>

2.2.4 百度百科实现

<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="utf-8">
  <title>归并排序</title>
</head>

<body>
  <script>
    function mergePass(arr = []) {
      let temp = new Array(arr.length);
      let N = arr.length;
      let length = 1; // 将每个元素看作是相邻的数组长度为1。

      let t; // 迭代深度。
      for (t = 0; Math.pow(2, t) < N; t++ , length *= 2) { // 每次跳过的长度翻倍。
        const even = t % 2 === 0; // 复用 arr 和 temp 来回赋值。
        for (let left = 0; left < N; left += 2 * length) { // 左边数组起始位置 left 从0开始。
          const middle = left + length < N ? left + length : left;
          const right = left + (2 * length) < N ? left + (2 * length) : N; 
          merge(
            even ? arr : temp,
            even ? temp : arr,
            left, middle, right
          ); // 合并每两个相邻的数组
        }
      }
      if (t % 2 === 0) {
        return arr;// 返回arr
      }
      return temp; // 返回 temp 。
    }

    function merge(arr, temp, left, middle, right) {
      debugger;
      // 通过右边数组的起始位置得到左边数组的结束位置。
      const leftEnd = middle - 1;
      while (left <= leftEnd && middle < right) {
        // 如果‘指针’没有越界。
        if (arr[left] > arr[middle]) {
          // 如果左边数组第一个元素比右边数组第一个元素大。
          // 将右边数组最小的放入有序数组 temp（初始值为空)。
          temp[left + (middle - leftEnd - 1)] = arr[middle++];
        } else {
          // 将左边数组最小的放入有序数组 temp（初始值为空)。
          temp[left + (middle - leftEnd - 1)] = arr[left++]; 
        }
      }
      while (left > leftEnd && middle < right) {
        // 如果左边数组放完了，右边数组还有元素。
        temp[left + middle - leftEnd - 1] = arr[middle++];
        // 那么依次将右边数组剩余的元素放入 temp。
      }
      while (left <= leftEnd && middle >= right) {
        // 如果右边数组放完了，左边数组还有元素
        temp[left + middle - leftEnd - 1] = arr[left++];
        // 那么依次将左边数组剩余的元素放入 temp 。
      }
      debugger;
    }

    var items = [9, 7, 3, 5]
    var res = mergePass(items)
    console.log(res)
  </script>
</body>

</html>

sort 归并排序排序算法数组公式