归并排序

算法参考：

算法思路

归并排序主要步骤有：

拆分：将数列按照二分法进行拆分成两个序列 L, R ，并逐步对 L 和 R 再次进行拆分，对于序列L和R，直到其序列长度为1，不再拆分该序列，其他序列继续执行次步骤
合并：对于两个序列 L 和 R, 我们认为 L 和 R 都是有序的，然后我们将 L 和 R 进行合并操作，得到一个新的有序序列 LR, 那么对于 L + R 这段序列来说，已经排序完毕

上面的拆分直到序列长度为1，不再拆分，此时对于该子序列已经有序了

长度为 1 的序列，两两合并，得到一系列长度 <= 2 的有序序列

长度为 2 的有序序列，两两合并，得到一些列长度 <= 4 的有序序列

依次合并执行......

复杂度分析

时间复杂度： $O (n l o g n)$
空间复杂度： $O (n)$

算法实现

JS 实现：

Array.prototype.mergeSort = function () {
	var arr = this.slice(0);

	function merge(left, right) {
		let result = [];
		while (left.length && right.length) {
			if (left[0] <= right[0]) {
				result.push(left.shift());
			} else {
				result.push(right.shift());
			}
		}

		if (left.length) result = result.concat(left);
		if (right.length) result = result.concat(right);
		return result;
	}

	function mergeSort(arr) {
		if (arr.length <= 1) return arr;

		let middle = Math.floor(arr.length / 2);
		let left = arr.slice(0, middle);
		let right = arr.slice(middle);

		return merge(mergeSort(left), mergeSort(right));
	}

	return mergeSort(arr);
};

var a = [
	3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7,
	4, 0, 2, 6,
];

// var a = [5, 3];
console.log(a.mergeSort());

Python 实现

def merge(self, left, right):
    result = []

    i = 0
    j = 0

    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 += left[i:]
    result += right[j:]

    return result

  def mergeSort(self, nums):
    length = len(nums)

    if length <= 1:
      return nums

    mid = length // 2

    left = self.mergeSort(nums[:mid])
    right = self.mergeSort(nums[mid:])

    return self.merge(left, right)

归并排序 ​

算法思路 ​

算法实现 ​

归并排序

算法思路

算法实现