/**
* 归并排序
* 采用分治法，
* 分是将无序列表递归的二分，直到只有一个元素，此时一个元素是有有序的，
* 治是在每一组都只有一个元素后开始对左右元素比较，处理成小的有序列表，直到所有变为有序
* @param {*} arr
*/
/**
* 假设列表为【2,5,4,3】，先分割成只有一个元素的列表[2] [5] [4] [3]
* 此时left = [2], right =[5]，处理成 [2,5]
* 此时left = [4], right=[3]， 处理成[3,4]
* 此时left = [2,5], right = [3,4]， 处理成[2,3,4,5]
*/
function mergeSort(arr) {
var length = arr.length
if (length === 1) {
return arr
}
var mid = Math.floor(length / 2)
var left = arr.slice(0, mid)
var right = arr.slice(mid)
return merge(mergeSort(left), mergeSort(right))
}
function merge(left, right) {
var temp = []
var i = 0,
j = 0
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
temp.push(left[i])
i++
} else {
temp.push(right[j])
j++
}
}
while (i < left.length) {
temp.push(left[i])
i++
}
while (j < right.length) {
temp.push(right[j])
j++
}
console.log(temp)
return temp
}
console.log(mergeSort(arr))
js算法排序-归并排序
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 选择排序 对于任何输入，时间为O(n*n)； 冒泡排序 最优（对于升序的数组，因为加入了一个跳出判断）：O(n)，...
