成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

js 排序算法之快速排序

Eidesen / 1002人閱讀

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

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

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

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

最壞時間復(fù)雜度：O($n^2$)  當(dāng)選擇的基準(zhǔn)值為最大值或最小值時
穩(wěn)定性：不穩(wěn)定
平均時間復(fù)雜度：O(n*$log_2$n)
阮一峰版 內(nèi)存占用較多 
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)的額外存儲空間，也就跟歸并排序一樣不好。額外需要的存儲器空間配置，在實際上的實現(xiàn)，也會極度影響速度和高速緩存的性能。
真正的快排

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

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

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

在數(shù)據(jù)集之中，選擇一個元素作為”基準(zhǔn)”（pivot）。

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

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

步驟：

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

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

所以一般選取了除數(shù)組最后一個元素為基準(zhǔn)元素后，會將該基準(zhǔn)元素換到最后一個元素上；這里便直接選取數(shù)組中最后一個元素為基準(zhǔn)元素，對整個數(shù)組進行分區(qū)操作[0~arr.length-1].當(dāng)然也可以只對數(shù)組中某一連續(xù)數(shù)組元素進行分區(qū)，即只對數(shù)組中這一小部分元素進行排序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;
    }
    // 數(shù)組分區(qū)，左小右大
    function partition(arr, left, right) {
        let storeIndex = left;
        let pivot = arr[right]; // 直接選最右邊的元素為基準(zhǔn)元素
        for(let i = left; i < right; i++) {
            if(arr[i] < pivot) {
                swap(arr, storeIndex, i);
                storeIndex++; // 交換位置后，storeIndex 自增 1，代表下一個可能要交換的位置
            } 
        }
        swap(arr, storeIndex, right); // 將基準(zhǔn)元素放置到最后的正確位置上
        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實現(xiàn)快速排序算法的詳細解釋
常見排序算法 - 快速排序 (Quick Sort)
算法的時間復(fù)雜度和空間復(fù)雜度-總結(jié)

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/97233.html

相關(guān)文章

  • JavaScript專題之解讀 v8 排序源碼

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

    princekin 評論0 收藏0

  • Java排序算法之——快速排序

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

    Yangyang 評論0 收藏0

  • Deep in JS - 收藏集 - 掘金

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

    enali 評論0 收藏0

  • PHP算法之四大基礎(chǔ)算法

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

    isLishude 評論0 收藏0

  • 算法學(xué)習(xí)之路，排序之快速排序（Java實現(xiàn)）

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

    charles_paul 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<