手记

排序算法 Quick Sort

前言

前端小菜鸡一枚,分享的文章纯属个人见解,若有不正确或可待讨论点可随意评论,与各位同学一起学习~

排序算法 Quick Sort

原理

  • 快速排序在每一轮挑选一个基准元素,并让其他比基准元素大的元素移到数列的一遍,比基准元素小的元素移动数列的另一边,从而把数列拆解成两部分。
  • 时间复杂度为:O(n log n)
  • 每一轮的比较和交换,需要把数组的全部元素都遍历一遍,时间复杂度为 O(n),这样的遍历需要多少轮呢?假如元素个数为 n,那么平均情况下需要 log n 轮。

基准元素的选择

  • 基准元素: pivot,在分治过程中,以基准元素为中心,把他的元素移动到他的左右两边。
  • 可使用随机选择一个元素作为基准元素,让基准元素和数列首元素交换位置。这样可以有效地将数列分成两个部分,但是也有极小的几率会选择数列的最大值和最小值,会影响分治的效果。
  • 时间复杂度为:O(n log n),最坏情况为:O(n²)

元素的交换

  • 选定好基准元素后,后面就是把小于基准元素的交换到基准元素的一遍,把大于基准元素的元素都交换到基准元素的另一边。
  • 可使用的方法:
    1. 双边循环法
    2. 单边循环法
  • 双边循环法:选择一个基准元素,并设置两个指针 left 和 right,指向最左或最右的连个元素。
    • 执行循环,从 right 指针开始,让指针指向的元素跟基准元素做比较,如果大于或等于 pivot,则指针向移动,如果小于 pivot,则 right 指针停止移动,切换到 left 指针。

单边循环法

  • 单边循环法:首先选定基准元素 pivot,同时,设置一个 mark 指针指向数列的起始位置,这个 mark 指针代表小于基准元素的区域边界。如果遍历到的元素大于基准元素,就继续往后遍历。如果遍历到的元素小于基准元素,把 mark 的指针右移一位,因为小于 pivot 的区域边界增大了。第二让最新遍历到的元素和 mark 指针所在的位置的元素交换位置。因为最新遍历到的元素属于小于 pivot 的区域。
Array.prototype.quickSort = function () {
    // 递归函数
    let rec = (arr) => {
        // 边界条件
        if (arr.length <= 1) return arr;
        // 分区数组
        let left = [];
        let right = [];
        // 基准元素
        let mid = arr[0];
        // 循环遍历
        for (let i = 1; i < arr.length; i++) {
            // 比基准小的元素放在基准前面 left,否则放在基准后面 right
            if (arr[i] < mid) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        // 递归调用两遍的子数组
        return [...rec(left), mid, ...rec(right)];
    };
    // 初始化递归函数
    let res = rec(this);
    res.forEach((item, index) => {
        this[index] = item;
    });
};

let arr = [98, 4, 6, 84, 42, 8674, 434, 56, 465];
arr.quickSort();
console.log(arr);

文章特殊字符描述:

  1. 问题标注 Q:(question)
  2. 答案标注 R:(result)
  3. 注意事项标准:A:(attention matters)
  4. 详情描述标注:D:(detail info)
  5. 总结标注:S:(summary)
  6. 分析标注:Ana:(analysis)
  7. 提示标注:T:(tips)
0人推荐
随时随地看视频
慕课网APP