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

資訊專欄INFORMATION COLUMN

Javascript算法——快速排序

馬忠志 / 2884人閱讀

摘要：常見的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。這里主要介紹快速排序。快速排序是一種既不浪費空間又可以快一點的排序算法。

常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。這里主要介紹快速排序。

一圖勝千言：

1. 算法描述

快速排序由于排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經(jīng)常被采用，再加上快速排序思想----分治法也確實實用?？焖倥判蚴且环N既不浪費空間又可以快一點的排序算法。

2. 算法步驟

先從數(shù)列中取出一個數(shù)作為“基準(zhǔn)”。

分區(qū)過程：將比這個“基準(zhǔn)”大的數(shù)全放到“基準(zhǔn)”的右邊，小于或等于“基準(zhǔn)”的數(shù)全放到“基準(zhǔn)”的左邊。

再對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)。

3. 算法實現(xiàn) 
var quickSort = function(arr) {
    if (arr.length <= 1) { return arr; }
    var pivotIndex = Math.floor(arr.length / 2);   //基準(zhǔn)位置（理論上可任意選取）
    var pivot = arr.splice(pivotIndex, 1)[0];  //基準(zhǔn)數(shù)
    var left = [];
    var right = [];
    for (var 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));  //鏈接左數(shù)組、基準(zhǔn)數(shù)構(gòu)成的數(shù)組、右數(shù)組
};

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

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

相關(guān)文章

  • 深入淺出 JavaScript 的 Array.prototype.sort 排序算法

    摘要：快速排序是不穩(wěn)定的排序算法。瀏覽器的實現(xiàn)不同有什么影響排序算法不穩(wěn)定有什么影響舉個例子某市的機動車牌照拍賣系統(tǒng)，最終中標(biāo)的規(guī)則為按價格進行倒排序相同價格則按照競標(biāo)順位即價格提交時間進行正排序。 本文要解決的問題 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一種直觀的方式展示 Array.prototype.sort 的時間復(fù)雜度，看看它有多快？ 3、...

    itvincent 評論0 收藏0

  • JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法之美 - 歸并排序、快速排序、希爾排序、堆排序

    摘要：之所以把歸并排序快速排序希爾排序堆排序放在一起比較，是因為它們的平均時間復(fù)雜度都為。歸并排序是一種穩(wěn)定的排序方法。因此，快速排序并不穩(wěn)定。希爾排序思想先將整個待排序的記錄序列分割成為若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言 算法為王。 想學(xué)好前端，先練好內(nèi)功，只有內(nèi)功深厚者，前端之路才...

    haitiancoder 評論0 收藏0

  • 算法系列——JavaScript快速排序思想實現(xiàn)

    摘要：源碼實現(xiàn)快速排序理論理解起來很容易，但經(jīng)常是實際寫代碼，無從下手，下面是我根據(jù)快排的步驟實現(xiàn)的遞歸快速排序。合并第一次快速排序的，，數(shù)組。 原理 快速排序離不開遞歸的思想，你如果不了解遞歸，可以結(jié)合我另外一篇文章來學(xué)習(xí) 算法入門之遞歸分而治之思想的實現(xiàn) 網(wǎng)上有有趣的動態(tài)圖來表示快速排序，但其實我們大部分程序員都是腦子不太好使那種，即使看了形象生動的動態(tài)圖，還是想不到具體實現(xiàn)思路。 排序...

    lentrue 評論0 收藏0

  • JavaScript算法詳解——快速排序

    摘要：常見排序?qū)崿F(xiàn)的常見排序算法有冒泡排序選擇排序插入排序謝爾排序快速排序遞歸快速排序堆棧歸并排序堆排序過程快速排序的思想很簡單，整個排序過程只需要三步在數(shù)據(jù)集之中，找一個基準(zhǔn)點建立兩個數(shù)組，分別存儲左邊和右邊的數(shù)組利用遞歸進行下次比較看一個網(wǎng)頁 常見排序 javaScript實現(xiàn)的常見排序算法有:冒泡排序,選擇排序,插入排序,謝爾排序,快速排序(遞歸),快速排序(堆棧),歸并排序,堆排序 ...

    zhouzhou 評論0 收藏0

發(fā)表評論

0條評論

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