- 选择一个基准元素,将数据列表分成两个子序列;
- 对数据列表进行重新排序,将所有小于基准值的元素放在基准值的前面,所有大于基准值的元素放在基准值的后面;
- 分别对较小元素的子序列和较大元素的子序列重复步骤1和2。
快速排序是基于“分而治之”思想,还有一种排序算法和快速排序很像,都是基于“分而治之”
归并排序
归并排序是一种分治算法。其思想是将原始数据切分成为较小的数组,直到每一个小数组只有一个位置,这个过程叫做分治。接着将小数组归并成为较大的数组,直到最后只有一个排序完毕的大数组,这个过程是归并。由于是分治法,所以归并排序也是递归的。
归并分两步:
- 分(分治,拆分)
- 并(归并)
所以我们应该写一个分治的函数,再写一个归并的函数。在分治的函数中返回归并的函数时不断递归调用自身,完成分割,在返回至归并,直至数组排序完成。
function mergeSortSplit(array) {
// 如果长度为1就不用拆分了(递归函数的停止条件)
if (array.length == 1) {
return array;
}
//选择中间值
const mid = Math.floor(array.length / 2);
// 提取下标0到mid-1的元素到左数组
const left = array.slice(0, mid);
// 提取下标mid到length-1的元素到右数组
const right = array.slice(mid, array.length)
// 调用归并方法,并递归拆分
return merge(mergeSortSplit(left), mergeSortSplit(right))
}
归并方法
//归并
/*
merge是接收两个数组,并从每个数组的首项开始进行比较,小的元素放到左边,大的元素放到右边。
*/
function merge(left, right) {
// result是存放归并后的数组的数组
const result = [];
// il是左边数组的下标,ir是右边数组的下标,它们都从0开始
let il = 0;
let ir = 0;
// 循环比较
while (il < left.length && ir < right.length) {
/*
如果左边的元素比右边的元素小,就将他放到result中,反之把右边 的放进result。直至有一个数组到头了,就会结束循环,将另一个数组添加到result 的后面。
*/
if (left[il] < right[ir]) {
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
while (il < left.length) {
result.push(left[il++]);
}
while (ir < right.length) {
result.push(right[ir++]);
}
// 这个函数返回的是一个归并好的一个数组
return result;
}
最后对两个方法进行封装
arr = [5, 7, 6, 1, 4, 3, 2, 9, 10, 8]
function mergeSort(myArr) {
//归并
const merge = (left, right) => {
const result = [];
let il = 0;
let ir = 0;
while (il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
while (il < left.length) {
result.push(left[il++]);
}
while (ir < right.length) {
result.push(right[ir++]);
}
console.log('result', result);
return result;
}
//拆分
const mergeSortSplit = (array) => {
if (array.length == 1) {
return array;
}
const mid = Math.floor(array.length / 2);
const left = array.slice(0, mid);
const right = array.slice(mid, array.length)
console.log('left', left);
console.log('right', right);
return merge(mergeSortSplit(left), mergeSortSplit(right))
}
return mergeSortSplit(myArr);
}
console.log(arr);
console.log(mergeSort(arr));
我们看下输出,通过console观察代码的执行过程
看图中的标注
归并排序和快速排序的区别
快速排序和归并排序的原理都是基于“分而治之”思想,即首先把待排序的元素分成两组,然后分别对这两组排序,最后把两组结果合并起来。
它们的区别在于,进行的分组策略不同,后面的合并策略也不同。
归并排序的分组策略:假设待排序的元素存放在数组中,那么其把数组前面一半元素作为一组,后面一半作为另一组。
快速排序的分组策略:根据元素的值来分组,即大于某个值的元素放在一组,而小于的放在另外一组,该值称为基准。所以,对整个排序过程而言,基准值的挑选非常重要,如果选择不合适,太大或太小,那么所有元素都分在一组了。
总的来说,快速和归并排序,如果分组策略越简单,后面的合并策略就越复杂,因为快速排序在分组时,已经根据元素大小来分组了,而合并时,只需要把两个分组合并起来就行了,归并排序则需要对两个有序的数组根据大小合并。
😮 挺好的,感谢分享,加油
路过
路过
真心希望评论的内容来自于阅读文章后的感悟