JavaScript 数据结构与算法十大经典排序算法-归并排序(五)

86 阅读 0 评论 57 点赞

我是靠谱客的博主端庄世界，这篇文章主要介绍JavaScript 数据结构与算法十大经典排序算法-归并排序(五)，现在分享给大家，希望可以做个参考。

原理

归并排序，是先把数组从中间分成两部分，然后对前后两部分分别排序，再将排序好的连部分合并在一起。

核心思想是将两个有序的数列合并成一个大的有序序列。通过递归，层层合并，即为归并

代码实现

复制代码

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
const mergeSort = arr =>{
	// 采用自上而下的递归方法
	const len = arr.length
	if ( len <2 ) {
		return arr
	}
	let middle = Math.floor ( len/2 ),
		 left = arr.slice ( 0, middle ),
		 right = arr.slice ( middle ) ;
 	return merge ( mergeSort ( left ), mergeSort ( right ) )
}

const merge = (left, right){
	const result = [ ]
	while ( left.length && right.length ){
		// 注意：判断的条件是小于等于，如果只是小于，那么排序不稳定
		if ( left[0] <= right[0] ){
			result.push( left.shift() )
		} else {
			result.push( right[0] )
		}
	}
	while ( left.length ) result.push( left.shift() )
	while ( right.length ) result.push( right.shift() )
	return result;
}