前端学习数据结构与算法系列(八)：快速排序与三路快排

/**
 * 快速排序:
 * @param arr 需要进行快速排序的数组
 * @returns {*[]|*}
 */
const quickSort = function (arr) {
    if(arr.length < 2) return arr;
    // 随机选择0～arr.length之间选一个基准值
    const pivot = Math.floor(Math.random() * arr.length)
    // 声明两个数组，分别用于存放比基准值小的数据和比基准值大的数据
    let minArr = [];
    let maxArr = [];
    // 根据基准值填充数组
    for(let i = 0; i < arr.length; i++){
        // 大于基准值就放maxArr里
        if(arr[i] >= arr[pivot] && i !== pivot){
            maxArr.push(arr[i]);
        }
        // 小于基准值就放minArr里
        if(arr[i] < arr[pivot] && i !== pivot){
            minArr.push(arr[i])
        }
    }
    // 分别对基准值划分出来的数组递归调用快速排序，然后合并数组
    return [...quickSort(minArr), arr[pivot], ...quickSort(maxArr)];
}

const dataArr = [3,5,8,1,2,9,4,7,6];
console.log(quickSort(dataArr))

/**
 *
 * @param arr 需要进行三路快排的数组
 * @param L 数组的起始位置
 * @param R 数组的末尾位置
 * @returns {{lt: *, gt: *}}
 */
const partition = function (arr, L, R) {
    // 基准值为数组的零号元素
    let p = arr[L];
    // 左区间的初始值: L
    let lt = L;
    // 右区间的初始值: R+1
    let gt = R + 1;
    for (let i = L + 1; i < gt;){
        if(arr[i] === p){
            // 当前i指向的元素等于p
            i++;
        } else if(arr[i] > p){
            // 当前i指向的元素大于p，将gt-1处的元素与当前索引处的元素交换位置，gt--
            [arr[gt -1],arr[i]] = [arr[i],arr[gt - 1]];
            gt--;
        }else{
            // 当前i指向的元素小于p，将lt+1处的元素与当前索引处的元素交换位置，lt+1，i+1
            [arr[lt + 1],arr[i]] = [arr[i],arr[lt + 1]];
            lt++;
            i++;
        }
    }

    // i走向gt处，除了基准值外的元素，其余的空间已经分区完毕，交换基准值与lt处的元素，lt-1，最终得到我们需要的三个区间
    [arr[L],arr[lt]] = [arr[lt],arr[L]];
    lt--;
    console.log(`三路快排后的数组: ${arr}`);
    return {lt : lt, gt : gt};
}

const dataArr = [3,5,8,1,2,9,4,7,6];
console.log(partition(dataArr,0,dataArr.length - 1));

const threeWayFastRow = function (arr,L,R) {
    // 当前数组的起始位置大于等于数组的末尾位置时退出递归
    if(L >= R){
        return false;
    }
    let obj = partition(arr, L, R);
    // 递归执行: 将没有大于p,和小于p区间的元素在进行三路快排
    threeWayFastRow(arr,L,obj.lt);
    threeWayFastRow(arr,obj.gt,R);
}

console.time("三路快排");
const dataArr = [3,5,8,1,2,9,4,7,6];
threeWayFastRow(dataArr,0,dataArr.length - 1);
console.log(`三路快排完成: ${dataArr}`);
console.timeEnd("三路快排");

// 其他部分省略
/**
 * 生成一个随机数组
 * @param count
 * @returns {[]}
 */
const randomArray = function(count){
    let arr = [];
    for (let i = 0; i < count; i++) {
        arr[i] = Math.floor(Math.random() * 50 + 1);
    }
    return arr;
}

// ****普通快排其他部分省略****

// 生成数组
const dataArr = randomArray(10000);
console.time("普通快排");
quickSort(dataArr);
console.timeEnd("普通快排");

// ****三路快排其他部分省略****

// 生成数组
const dataArr = randomArray(10000);
console.time("三路快排");
threeWayFastRow(dataArr,0,dataArr.length - 1);
console.timeEnd("三路快排");

● 手写async await的最简实现（20行搞定）面试必考！● Vue3 尝鲜 Hook + TypeScript 取代 Vuex 实现图书管理小型应用● 类型即正义，TypeScript 从入门到实践（四）：5000字长文带你重新认识泛型