快捷導(dǎo)航

JavaScript快速排序(quickSort)算法的實(shí)現(xiàn)方法總結(jié)

更新時(shí)間：2023年11月21日 11:01:48 作者：進(jìn)二開物

快速排序的思想式分治法,選一個(gè)基準(zhǔn)點(diǎn),然后根據(jù)大小進(jìn)行分配,分配然完畢之后,對(duì)已經(jīng)分配的進(jìn)行遞歸操作,最終形成快速排序,所以遞歸也是快速排序思想的一個(gè)重要組成部分,本文主要給大家介紹了JavaScript實(shí)現(xiàn)快速排序的寫法,需要的朋友可以參考下

什么是快速排序？

快速排序的思想式 分治法。選一個(gè)基準(zhǔn)點(diǎn)，然后根據(jù)大小進(jìn)行分配，分配然完畢之后，對(duì)已經(jīng)分配的進(jìn)行遞歸操作，最終形成快速排序。所以遞歸也是快速排序思想的一個(gè)重要組成部分。

基本思路

基準(zhǔn)點(diǎn)：選中基準(zhǔn)點(diǎn)，一般選擇數(shù)組第一項(xiàng)，當(dāng)然也可以隨機(jī)或者指定數(shù)據(jù)。
分區(qū)，一般分為 less/greater 或者 left/right
遞歸：對(duì)已有的分區(qū)經(jīng)進(jìn)行遞歸操作
合并：將已有的數(shù)據(jù)進(jìn)行合并

寫法一：基礎(chǔ)寫法

function quickSort(arr) {
    // 數(shù)組小于 1 不用排序，直接返回即可
    if(arr.length <= 1) {
        return arr;
    }
    
    const p = arr[0]; // 選定數(shù)組第一個(gè)為基準(zhǔn)點(diǎn)
    const left = []; // 左分區(qū)
    const right = []; // 右分區(qū)
    
    // 遍歷給左右分區(qū)
    for(let i = 1; i < arr.length; i++) {
        if(arr[i] < p) {
            // 小于基準(zhǔn)點(diǎn)放在左邊
            left.push(arr[i])
        }else {
            // 大于基準(zhǔn)點(diǎn)方在右邊
            right.push(arr[i])
        }
    }
    // 合一并且對(duì)左右分區(qū)，遞歸處理
    
    return quickSort(left).concat(p, quickSort(right))
}

寫法二：函數(shù)式

function quickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    } else {
        const p = arr[0]; // 確定中間值
        const left = arr.slice(1).filter(x => x <= p);
        const right = arr.slice(1).filter(x => x > p);
        return quickSort(left).concat(p, quickSort(right))
    }
}

使用 filter 過濾，偏向函數(shù)式編程，寫的代碼更加簡(jiǎn)潔。

寫法三：隨機(jī)基準(zhǔn)值

function randomizeQuickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    } else {
        const pi = Math.floor(Math.random() * arr.length); // 隨機(jī)基準(zhǔn)值索引
        const p = arr[pi];
        const left = arr.slice(0, pi).concat(arr.slice(pi + 1).filter(x => x <= p));
        const right = arr.slice(pi + 1).filter(x => x > p);
        return randomizeQuickSort(left).concat(p, randomizeQuickSort(right))
    }
}

隨機(jī)獲取基準(zhǔn)值索引，根據(jù)隨機(jī)索引獲基準(zhǔn)值，所有這兩個(gè)已知的值，就可以制作一個(gè)隨機(jī)索引快速排序了。

寫法四：三分法

function threeWayQuickSort(arr) {
    if (arr.length <= 1) {
        return arr;
    } else {
        const p = arr[0];
        const left = arr.filter(x => x < p);
        const mid = arr.filter(x => x === p); // 獲取所有的中間值，避免重復(fù)計(jì)算
        const right = arr.filter(x => x > p);
        return threeWayQuickSort(left).concat(mid, threeWayQuickSort(right))
    }
}

三路法，將二路基礎(chǔ)上，將自己看成一個(gè)中間數(shù)組，因?yàn)榕c自己相等的可能有很多。這樣就避免了在其他數(shù)組中，還有中間數(shù)據(jù)的重復(fù)比較, 一種快速排序的優(yōu)化。

排序算法的使用場(chǎng)景

大規(guī)模數(shù)據(jù)排序速度，比其他的算法要快

復(fù)雜度分析

快速排序的平均時(shí)間復(fù)雜度是 O(n log n) 這種復(fù)雜度是比較理想的。O(n log n) 來源是 劃分 O(n) 和 遞歸 O(log n) 的組合。

更難展望

雙軸快速排序
尾遞歸優(yōu)化

小結(jié)

文本主要講解常用算法中的快速排序的算法，快速排序的思想很簡(jiǎn)單，就是分與合配合遞歸的思想。選定一個(gè)基準(zhǔn)值，然后進(jìn)行對(duì)比分離，遞歸這個(gè)操作，然后重新配合在一起。當(dāng)然排序算法也是可以根據(jù)自己的需求進(jìn)行優(yōu)化的。

您可能感興趣的文章: