算法基础 - 快速排序

三路快排：快速排序的一个优化版本

其主要过程：

1. 首先随机取一个数，将其作为锚点；
2. 定义三个数组，用于存储大于、等于、小于锚点的数；
3. 对数组进行循环，将数组的数分配到各个数组内；
4. 对大于和小于锚点的数组进行递归操作；
5. 最后返回一个解构后的新数组；

这里有非常直观的可视化排序过程：visualgo

实现

function quickSort(arr) {
    // 如果数组为空，则直接返回
    if(arr.length<=0) return [];
    // 取数组中间数作为锚点
    const pivot = arr[Math.floor(arr.length/2)] ;
    // 定义三个数组，left 用于存储小于锚点的数，mid 存储等于锚点的数，right 存储大于锚点的数
    const left = [], mid = [], right = [];
    // 对数组进行循环，将数放到指定的数组中
    for( let i = 0; i<arr.length; i++ ){
        if( arr[i] < pivot ){
            left.push(arr[i])
        }else if(arr[i] === pivot){
            mid.push(arr[i])
        }else{
            right.push(arr[i])
        }
    }
    // 左右数组再次调用快排，并对三个数组进行解构，返回一个新数组
    return [...quickSort(left), ...mid, ...quickSort(right)]
}

测试用例

const testArray = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48,];
console.log(quickSort(testArray));