数据结构与算法之分治归并排序

有一组数[10, 4, 6, 3, 8, 2, 5, 7], 对其进行排序, 结果为[2, 3, 4, 5, 6, 7, 8, 10]

示例

输入: [10, 4, 6, 3, 8, 2, 5, 7]
输出: [2, 3, 4, 5, 6, 7, 8, 10]

输入: [-3, 0, 15, 2, -16, 5, 7]
输出: [-16, -3, 0, 2, 5, 7, 15]

分析

归并排序的思想是:先使得每个子序列有序,然后再将子序列合并成有序的列表

代码

Python3

def mergrSort(self, nums):
  if len(nums) <= 1:
    return nums

  # 取中位数
  mid = len(nums) // 2

  # 分解: 不断递归将原始序列分解成n个小序列
  left = self.mergeSort(nums[:mid])
  right = self.mergeSort(nums[mid:])

  # 排序合并
  return merge(left, right)

def merge(left, right):
  i, j = 0, 0
  result = []

  # 子序列排序
  while i < len(left) and j < len(right):
    if left[i] <= right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1

  # 合并
  result.extend(left[i:])
  result.extend(right[j:])
  return result

JavaScript

function mergeSort(nums){
  let len = nums.length
  if (len <= 1) return nums

  let mid = len / 2

  let left = mergeSort(nums.slice(0, mid))
  let right = mergeSort(nums.slice(mid, len))
  return merge(left, right)
}

function merge(left, right) {
  let result = []

  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left[0])
      left.splice(0, 1)
    } else {
      result.push(right[0])
      right.splice(0, 1)
    }
  }
  return result.concat(left).cancat(right)
}