每天一个排序算法 ---归并排序

归并排序是第一个可以实际使用的排序算法。（冒泡、插入、选择）三个排序算法性能不好，但归并排序性能不错，其复杂度为 O(nlog(n))。

JavaScript 的 Array 类定义了一个 sort 函数（Array.prototype.sort）用以排序 JavaScript 数组（我们不必自己实现这个算法）。ECMAScript 没有定义用哪个排序算法，所以浏览器厂商可以自行去实现算法。例如，Mozilla Firefox 使用归并排序作为 Array.prototype.sort 的实现，而 Chrome（V8 引擎）使用了一个快速排序的变体。

归并排序是一种分而治之算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

由于是分治法，归并排序也是递归的。我们要将算法分为两个函数：

第一个负责将一个大数组分为多个小数组并调用用来排序的辅助函数。
第二个负责合并和排序小数组来产生大数组，直到回到原始数组并已排序完成。

分而治之

分而治之是算法设计中的一种方法。它将一个问题分成多个和原问题相似的小问题，递归解决小问题，

再将解决方式合并以解决原来的问题。

分而治之算法可以分成三个部分。

分解原问题为多个子问题（原问题的多个小实例）。
解决子问题，用返回解决子问题的方式的递归算法。递归算法的基本情形可以用来解决子问题。
组合这些子问题的解决方式，得到原问题的解。

可以看出这个方法将会花很多时间在最初的思考上，是个非常抽象的方法，在递归时一定需要一个终止条件，不然递归栈会溢出。

思路

分解问题

一个长度为n的数组，最简单就是分成两个数组，每个数组只有一项比较，那么可以将一个长数组拆分成log2n个数组比较

解决子问题
在两个数组比较时，分为左数组和右数组，比较完后一定要保证小的数在前面，大的数在后面，利用空间换时间可以只需比较此次数组的长度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


// 递归主体
function mergeSort(array){
	let result = array
	if(array.length > 1){	//递归终止条件
  	const {length}	= array		//解构赋值
    const middle = Math.floor(length / 2)
    const left = mergeSort(array.slice(0, middle))	// 递归得出左数组
    const right = mergeSort(array.slice(middle))	// 递归得出右数组
    result = merge(left, right)	// 在每次递归后，排好序
  }
  return result
}

// 将两个有序数组排序成一个有序数组
// 因为是从一个值的时候开始排的，所以每次递归过程中的值都是有序的
function merge(left, right){
  let i = 0
  let j = 0
  const result = []
  // 逻辑与，每次循环必然会有一个数组可以遍历完
  while(i < left.length && j < right.length){
  	result.push(left[i] < right[j]? left[i++] : right[j++] )
  }
  // 经过上面循环后需要将没有压入result中的数组连接上
  return result.concat(i < left.length ? left.slice(i) : right.slice(j))
}
let array = [5, 6, 1, 1, 2, 7, 3]
mergeSort(array)

递归方法很抽象，需要仔细思考才能得出一个正确的解，但是一旦得到解了，代码量就很少。

分而治之#

分而治之