js 排序算法之快速排序

Eidesen 發布于2019-08-23 11:38 / 992人閱讀

摘要：快速排序是一種劃分交換排序?？焖倥判蚧诿芭葸f歸分治。他在大數據情況下是最快的排序算法之一，平均事件復雜度很低而且前面的系數很小，在大量隨機輸入的情況下最壞情況出現的概率是極小的。

快速排序是一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法。

分治法的基本思想是：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解。

快速排序基于冒泡、遞歸分治。他在大數據情況下是最快的排序算法之一，平均事件復雜度很低而且前面的系數很小，在大量隨機輸入的情況下最壞情況出現的概率是極小的。

最壞時間復雜度：O($n^2$)  當選擇的基準值為最大值或最小值時
穩定性：不穩定
平均時間復雜度：O(n*$log_2$n)

阮一峰版內存占用較多

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;
    }
    let pivotIndex = Math.floor(arr.length / 2);
    let pivot = arr.splice(pivotIndex, 1)[0];
//  let pivot = arr.splice(pivotIndex, 1);  3 < [9] //true
    let left = [];
    let right = [];
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat(pivot, quickSort(right));
}

上面簡單版本的缺點是，它需要Ω(n)的額外存儲空間，也就跟歸并排序一樣不好。額外需要的存儲器空間配置，在實際上的實現，也會極度影響速度和高速緩存的性能。

真正的快排

按照維基百科中的原地(in-place)分區版本，實現快速排序方法如下：

function quickSort(arr) {
    function swap(arr, i, k) {
        let temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
    // 數組分區，左小右大
    function partition(arr, left, right) {
        let storeIndex = left;
        let pivot = arr[right]; // 直接選最右邊的元素為基準元素
        for(let i = left; i < right; i++) {
            if(arr[i] < pivot) {
                swap(arr, storeIndex, i);
                storeIndex++; // 交換位置后，storeIndex 自增 1，代表下一個可能要交換的位置
            } 
        }
        swap(arr, storeIndex, right); // 將基準元素放置到最后的正確位置上
        return storeIndex;
    }
    function sort(arr, left, right) {
        if(left > right) {
            return;
        }
        let storeIndex = partition(arr, left, right);
        sort(arr, left, storeIndex - 1);
        sort(arr, storeIndex + 1, right);
    }
    sort(arr, 0, arr.length - 1);
    return arr;
}

利用分治法來處理快排，主要的思想是：

在數據集之中，選擇一個元素作為”基準”（pivot）。

所有小于”基準”的元素，都移到”基準”的左邊；所有大于”基準”的元素，都移到”基準”的右邊。這個操作稱為分區 (partition) 操作，分區操作結束后，基準元素所處的位置就是數組最終排序后它的位置。

對”基準”左邊和右邊的兩個子集，不斷重復第一步和第二步，直到所有子集只剩下一個元素為止。

步驟：

首先，把基準元素移到結尾（如果直接選擇最后一個元素為基準元素，那就不用移動）；
然后從左到右（除了最后的基準元素），循環移動小于等于基準元素的元素到數組的開頭，每次移動 storeIndex 自增 1，表示下一個小于基準元素將要移動到的位置；
循環結束后 storeIndex 所代表的的位置就是基準元素的所有擺放的位置；所以最后將基準元素所在位置（這里是 right）與 storeIndex 所代表的的位置的元素交換位置。
完成一次分區；

tips：這里為什么要把基準元素放到數組的最后一個元素的位置上，是為了方便對數組中除了基準元素以外的所有元素進行遍歷，并方便在找到基準元素的排序位置 storeIndex 后進行兩兩交換。倘若不如此，需要將該基準元素從原數組中取出來（類似阮一峰版做法arr.splice(pivotIndex, 1)）,循環遍歷完所有除基準元素外的元素后，找到基準元素的最后排序位置 storeIndex后，需要將基準元素插入進來（用到插入排序的思想），顯然這種方式較為復雜。

所以一般選取了除數組最后一個元素為基準元素后，會將該基準元素換到最后一個元素上；這里便直接選取數組中最后一個元素為基準元素，對整個數組進行分區操作[0~arr.length-1].當然也可以只對數組中某一連續數組元素進行分區，即只對數組中這一小部分元素進行排序sort(arr, start, end);。

function quickSort(arr, start, end) {
    function swap(arr, i, k) {
        let temp = arr[i];
        arr[i] = arr[k];
        arr[k] = temp;
    }
    // 數組分區，左小右大
    function partition(arr, left, right) {
        let storeIndex = left;
        let pivot = arr[right]; // 直接選最右邊的元素為基準元素
        for(let i = left; i < right; i++) {
            if(arr[i] < pivot) {
                swap(arr, storeIndex, i);
                storeIndex++; // 交換位置后，storeIndex 自增 1，代表下一個可能要交換的位置
            } 
        }
        swap(arr, storeIndex, right); // 將基準元素放置到最后的正確位置上
        return storeIndex;
    }
    function sort(arr, left, right) {
        if(left > right) {
            return;
        }
        let storeIndex = partition(arr, left, right);
        sort(arr, left, storeIndex - 1);
        sort(arr, storeIndex + 1, right);
    }
    sort(arr, start, end);
    return arr;
}
quickSort([3,7,8,5,2,1,9,5,4], 3, 7) // 只對部分元素排序

References

JS實現快速排序算法的詳細解釋
常見排序算法 - 快速排序 (Quick Sort)
算法的時間復雜度和空間復雜度-總結

云服務器 GPU云服務器快速排序算法最好的快速排序算法最快速的排序算法 js快速排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/97233.html

JavaScript專題之解讀 v8 排序源碼

摘要：插入排序是穩定的算法。所以準確的說，當數組長度大于的時候，采用了快速排序和插入排序的混合排序方法。在對數組進行了一次快速排序后，然后對兩個子集分別進行了插入排序，最終修改數組為正確排序后的數組。 JavaScript 專題系列第二十篇，也是最后一篇，解讀 v8 排序源碼前言 v8 是 Chrome 的 JavaScript 引擎，其中關于數組的排序完全采用了 JavaScript 實...

princekin 2019-08-21 17:07 評論0 收藏0
Java排序算法之——快速排序

摘要：代碼片段語言組織能力有限，直接上代碼排序算法之快速排序參數為需要排序的數組參數為數組的起始下角標即參數為數組的最后下角標即經過一輪排序，已經將數組分為左右兩部分進行遞歸排序總結快速排序的精髓在于分治思想，分而治之，它的時間復雜度為。算法簡述所謂快速排序算法是基于交換排序和遞歸思想的，它的速度的確如名字所示——快！并且這種一算一般被用作數量級比較大的數據當中，在大數據中有著很重要的地...

Yangyang 2019-08-14 12:19 評論0 收藏0
Deep in JS - 收藏集 - 掘金

摘要：今天同學去面試，做了兩道面試題全部做錯了，發過來給道典型的面試題前端掘金在界中，開發人員的需求量一直居高不下。排序算法 -- JavaScript 標準參考教程（alpha） - 前端 - 掘金來自《JavaScript 標準參考教程（alpha）》，by 阮一峰目錄冒泡排序簡介算法實現選擇排序簡介算法實現 ... 圖例詳解那道 setTimeout 與循環閉包的經典面...

enali 2019-08-20 16:36 評論0 收藏0
PHP算法之四大基礎算法

摘要：而在證明算法是正確的基礎上，第二步就是分析算法的時間復雜度。算法的時間復雜度反映了程序執行時間隨輸入規模增長而增長的量級，在很大程度上能很好反映出算法的優劣與否。 showImg(https://segmentfault.com/img/remote/1460000016451712?w=800&h=341); 前言雖然工作中，你覺得自己并沒有涉及到算法這方面的東西，但是算法是程序的...

isLishude 2019-07-01 12:31 評論0 收藏0
算法學習之路，排序之快速排序（Java實現）

摘要：接下來我來說明快速排序的思路以及實現的代碼?？焖倥判蛩悸肥紫仁嵌x一個變量，把數組的第一個元素的值賦給，然后定義兩個變量指向數組的第一個元素和最后一個元素。今天突然想寫個排序，以前寫過，然后寫了之后一直出錯，然后自己百度了一下，看了別人寫的方法，自己也嘗試著寫了一個。接下來我來說明快速排序的思路以及實現的代碼。快速排序思路：首先是定義一個變量key，把數組的第一個元素的值賦給key...

charles_paul 2019-08-14 15:38 評論0 收藏0