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

原理

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

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

代码实现

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;
}

动画

看了很久才看明白代码，如果代码难理解，可以对照着动画看看排序过程是怎么样的。

最后

以上就是端庄世界为你收集整理的JavaScript 数据结构与算法十大经典排序算法-归并排序(五)的全部内容，希望文章能够帮你解决JavaScript 数据结构与算法十大经典排序算法-归并排序(五)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。