陌上寒

陌上寒个人博客

javascript高级排序算法之归并排序

《javascript高级排序算法之归并排序》
上次讨论了javascript的快速排序,
快排:

  1. 选择一个基准元素,将数据列表分成两个子序列;
  2. 对数据列表进行重新排序,将所有小于基准值的元素放在基准值的前面,所有大于基准值的元素放在基准值的后面;
  3. 分别对较小元素的子序列和较大元素的子序列重复步骤1和2。

快速排序是基于“分而治之”思想,还有一种排序算法和快速排序很像,都是基于“分而治之”

归并排序

归并排序是一种分治算法。其思想是将原始数据切分成为较小的数组,直到每一个小数组只有一个位置,这个过程叫做分治。接着将小数组归并成为较大的数组,直到最后只有一个排序完毕的大数组,这个过程是归并。由于是分治法,所以归并排序也是递归的。
归并分两步:

  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观察代码的执行过程
《javascript高级排序算法之归并排序》
看图中的标注

归并排序和快速排序的区别

快速排序和归并排序的原理都是基于“分而治之”思想,即首先把待排序的元素分成两组,然后分别对这两组排序,最后把两组结果合并起来。
它们的区别在于,进行的分组策略不同,后面的合并策略也不同。

归并排序的分组策略:假设待排序的元素存放在数组中,那么其把数组前面一半元素作为一组,后面一半作为另一组。
快速排序的分组策略:根据元素的值来分组,即大于某个值的元素放在一组,而小于的放在另外一组,该值称为基准。所以,对整个排序过程而言,基准值的挑选非常重要,如果选择不合适,太大或太小,那么所有元素都分在一组了。

总的来说,快速和归并排序,如果分组策略越简单,后面的合并策略就越复杂,因为快速排序在分组时,已经根据元素大小来分组了,而合并时,只需要把两个分组合并起来就行了,归并排序则需要对两个有序的数组根据大小合并。

  1. 匿名说道:

    :eek: 挺好的,感谢分享,加油

发表评论

电子邮件地址不会被公开。