Java教程

排序之快速排序

本文主要是介绍排序之快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

    • 快速排序
      • 1 动画
      • 2 思想
      • 3 实现步骤
      • 4 解法
        • 写法1
        • 写法2
      • 5 分析
          • 时间复杂度
          • 空间复杂度
          • 稳定性
      • 参考资料:

快速排序

1 动画

快速排序.gif

2 思想

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据要小,再按这种方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,使整个数据变成有序序列。

3 实现步骤

  • 选择一个基准元素target(一般选择第一个数)
  • 将比target小的元素移动到数组左边,比target大的元素移动到数组右边
  • 分别对target左侧和右侧的元素进行快速排序

4 解法

写法1

这种写法浪费大量存储空间,写法简单

  1. 单独开辟两个存储空间left和right来存储每次递归比target小和大的序列
  2. 每次递归直接返回left、target、right拼接后的数组
function quickSort1(array) {
    if (array.length < 2) { // 递归出口
        return array;
    }
    const target = array[0]; // 取数组第一个数为基准元素
    const left = []; // 左边数组,存放比 target 小的数
    const right = []; // 右边数组,存放不比 target 小的数
    for (let i = 1; i < array.length; i++) { // 遍历数组,把元素分到左右两个数组
        if (array[i] < target) {
            left.push(array[i]);
        } else {
            right.push(array[i]);
        }
    }
    return quickSort1(left).concat([target], quickSort1(right)); // 递归排序,并把左右两边数组和 target 合并
}

// 测试
const array2 = [7, 6, 5, 4, 3, 2, 1];
console.log('quickSort1 ', quickSort1(array2));

写法2

  1. 定义基准点 target,定义头尾双指针,头指针 left 指向数组最左侧,尾指针 right 指向数组最右侧

  2. 在头尾指针未相撞之前(即 left < right)

    • 尾指针往左移动,遇到比 target 大的就忽略,遇到比 target 小的,就把尾指针的值赋值给头指针

    • 头指针往右移动,遇到比 target 小的就忽略,遇到比 target 大的,就把头指针的值赋值给尾指针

  3. 步骤2执行完之后,比 target 大的被分到数组右侧,比 target 小的被分到数组左侧,这时候把 target 插入数组

function quickSort2(array, start, end) {
    if (start >= end) return; // 递归出口
    const target = array[start]; // 定义基准元素
    
    let left = start; // 头指针 left 指向数组最左侧
    let right = end; // 尾指针 right 指向数组最右侧

    while (left < right) { // 头尾指针未相撞
        while (left < right && array[right] >= target) { // array[right] 比 target大(或相等),忽略
            right--;
        }
        array[left] = array[right]; // 尾指针的值赋值给头指针
        while (left < right && array[left] < target) { // array[left] 比 target小,忽略
            left++;
        }
        array[right] = array[left]; // 头指针的值赋值给尾指针
    }
    array[left] = target; // 把 target 插入数组

    // target 左右两边递归排序
    quickSort2(array, start, left - 1);
    quickSort2(array, left + 1, end);
    return array;
}

// 测试
const array = [3, 1, 5, 4, 7, 2, 6];
console.log('quickSort2 ', quickSort2(array, 0, array.length-1));

5 分析

时间复杂度
  • 最佳情况:O(nlogn)

  • 最差情况:O(n²)

    最差情况比如,[1, 2, 3, 4, 5],每次都拿第一个元素为target,然后再扫描后面的元素。相当于内外双循环,所以时间复杂度为O(n²)

  • 平均情况:O(nlogn)

空间复杂度

O(logn)(递归调用消耗)

稳定性

不稳定:快速排序每次交换的元素都有可能不是相邻的,因此它有可能打破原来值为相同的元素之间的顺序。因此,快速排序并不稳定

参考资料:

  • JavaScript 数据结构与算法之美 - 十大经典排序算法汇总

  • awesome-coding-js

这篇关于排序之快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!