文章目录

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

快速排序

1 动画

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