JavaScript实现归并排序算法详解说明

归并排序（Merge Sort）算法，也叫合并排序，是创建在归并操作上的一种有效的排序算法。算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列。

归并排序和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。

归并排序是用分治思想，分治模式在每一层递归上有三个步骤：

分解（Divide）：将n个元素分成个含n/2个元素的子序列。 解决（Conquer）：用合并排序法对两个子序列递归的排序。 合并（Combine）：合并两个已排序的子序列已得到排序结果。

实现过程

  1. 将所有数组项无限细分，得到1个个独立的单元，也就是不断分解。
  2. 将相近的两两进行比较，按照已排序数组合并，形成（n/2）个序列，每个序列包含2个数字。
  3. 将上述两个序列递归合并，按照已排序数组合并，形成（n/4）个序列，每个序列包含4个数字。
  4. 重复步骤2，直到所有元素合并排序完毕。

示意图

性能分析

平均时间复杂度：O(nlogn) 最佳时间复杂度：O(n) 最差时间复杂度：O(nlogn) 空间复杂度：O(n) 排序方式：In-place 稳定性：稳定

JS第1种写法，标准双指针移动比较js

/** * 归并排序 ，采用分而治之(divide - conquer)的步骤 * 1. 分解（Divide），把待排序元素的序列分解为两个子序列，以中间2分, 每个子序列包括一半成员。 * 2. 解决（Conquer），对每个子序列分别调用归并操作, 进行递归或非递归循环操作，完成内部排序。 * 3. 合并（Combine），合并两个排好序的子序列，生成排序结果。 归并排序的最坏时间复杂度和平均时间复杂度均为O(nlogn) */(function () {  // 将两个有序数组合并为一个新的有序数组  function merge (arr, left, mid, right) {    // 先建立一个长度等于原数组的临时数组    const temp = []    // 左侧指针    let i = left    // 右侧指针    let j = mid + 1    // 临时数组指针    let k = 0    // 当左指针小于中间，且右指针不大于最右侧时    while (i <= mid && j <= right) {      // 如果左侧小于右侧，将数移到临时数组中左侧      if (arr[i] <= arr[j]) {        temp[k++] = arr[i++]        // 否则移动到临时数组右侧      } else {        temp[k++] = arr[j++]      }    }    // 如果左边数组还有数据，就把左侧剩余都放入到原数组后面    while (i <= mid) {      temp[k++] = arr[i++]    }    // 如果右侧数组还有数据，把剩下的数据放入到原数组后面    while (j <= right) {      temp[k++] = arr[j++]    }    // 将排序后的元素全部移动到原数组中    let x = 0    while (left <= right) {      arr[left++] = temp[x++]    }    console.log('arr:', arr)  }  function mergeSort (arr, left, right) {    // 得到中间值    const mid = Math.floor((left + right) / 2)    // 如果左侧小于右侧则执行合并排序    if (left < right) {      // 递归合并左侧      mergeSort(arr, left, mid)      // 递归合并右侧      mergeSort(arr, mid + 1, right)      // 合并左右结果      merge(arr, left, mid, right)    }    return arr  }  // test  const arr = [7, 11, 9, 10, 12, 13, 8, -2, 0, 8]  console.time('sort')  console.log('origin:', arr)  console.log('\r\nsorted:', mergeSort(arr, 0, arr.length - 1))  console.timeEnd('sort')})();

js

// JS第2种写法，双指针移动结合数组特性(function () {  function mergeSort (arr) {    const len = arr.length    if (len < 2) {      return arr    }    // 取得当前数组的中间位置    const mid = Math.floor(len / 2)    const left = arr.slice(0, mid)    const right = arr.slice(mid)    console.log('mergeSort arr:', arr, left, right)    // 递归调用，不断重复直到当前数组拆分剩1项    return merge(mergeSort(left), mergeSort(right))  }  // 将两个有序数组进行合并为一个新的有序数组  function merge (left, right) {    // 建立一个空数组，用来存放排序结果    const result = []    // 左右数组的长度都不为空时，则将两个数组的第一个进行比较    // 如左侧小于右，则移除左侧的内容到结果数据，反之移动右侧成员    while (left.length && right.length) {      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  }})()

链接

归并排序算法源码：https://github.com/microwind/algorithms/tree/master/sorts/mergesort

其他排序算法源码：https://github.com/microwind/algorithms