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

資訊專(zhuān)欄INFORMATION COLUMN

快排

galois / 1366人閱讀

摘要：寫(xiě)這篇文章源于之前的一次面試以及網(wǎng)上看到各種說(shuō)原生的比快排快的例子，因?yàn)樗麄兌紱](méi)有寫(xiě)好快排。

寫(xiě)這篇文章源于之前的一次面試以及網(wǎng)上看到各種說(shuō)原生的sort比快排快的例子，因?yàn)樗麄兌紱](méi)有寫(xiě)好快排。面試的時(shí)候讓我寫(xiě)一個(gè)快排，我寫(xiě)出了我在網(wǎng)上看的的很簡(jiǎn)潔的一段代碼（后來(lái)發(fā)現(xiàn)這個(gè)代碼在數(shù)據(jù)結(jié)構(gòu)和算法JavaScript描述這本書(shū)上也有）：

function quickSort(arr){
    if(arr.length < 1){
            return [];
    }
    var left = [],right = [],flag = arr[0];
    for(var i=1;i

這樣寫(xiě)的話(huà)，乍一看確實(shí)是快排的思想，把比主元小的元素放到左數(shù)組，把比主元大的元素放到右數(shù)組，然后分別對(duì)左右數(shù)組的元素進(jìn)行排序最終拼接成新的數(shù)組。
但是計(jì)算機(jī)課程里講解快排的時(shí)候都不是這樣講解的，一趟快速排序的算法一般是這樣講解的：



設(shè)置兩個(gè)變量i、j，排序開(kāi)始的時(shí)候：i=0，j=N-1；


以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；


從j開(kāi)始向前搜索，即由后開(kāi)始向前搜索(j--)，找到第一個(gè)小于key的值A(chǔ)[j]，將A[j]和A[i]互換；


從i開(kāi)始向后搜索，即由前開(kāi)始向后搜索(i++)，找到第一個(gè)大于key的A[i]，將A[i]和A[j]互換；


重復(fù)第3、4步，直到i=j；



采用js實(shí)現(xiàn)的版本如下：


function quickSort_two(arr){
    function sort(start,end){
        if(start + 1 > end){
            return;
        }
        var flag = arr[start],f = start,l = end;
        while(f < l){
            while(f < l && arr[l] > flag){
                l--;
            }
            arr[f] = arr[l];
            while(f < l && arr[f] <= flag){
                f++;
            }
            arr[l] = arr[f];
        }
        arr[f] = flag;
        sort(start,f-1);
        sort(f+1,end);   
    }
    sort(0,arr.length-1);
}



對(duì)比這兩中快排的寫(xiě)法，在時(shí)間復(fù)雜度上都是O(nlogn)，但是第二種寫(xiě)法使用了更少的空間，第一種寫(xiě)法的空間復(fù)雜度是O(nlogn),而第二種的空間復(fù)雜度是O(logn),而且對(duì)數(shù)組的操作都在原數(shù)組上進(jìn)行，減去了創(chuàng)建空間的消耗和時(shí)間，在性能上無(wú)疑有了更多的提升。



下面是三種排序算法的一個(gè)對(duì)比：


function quickSort_one(arr){
    if(arr.length < 1){
            return [];
    }
    var left = [],right = [],flag = arr[0];
    for(var i=1;i end){
            return;
        }
        var flag = arr[start],f = start,l = end;
        while(f < l){
            while(f < l && arr[l] > flag){
                l--;
            }
            arr[f] = arr[l];
            while(f < l && arr[f] <= flag){
                f++;
            }
            arr[l] = arr[f];
        }
        arr[f] = flag;
        sort(start,f-1);
        sort(f+1,end);   
    }
    sort(0,arr.length-1);
}

function quickSort_three(arr){
    arr.sort(function(a,b){
        return a-b;
    });
}

function countTime(fn,arr){
    var start = Date.now();
    fn(arr);
    var end = Date.now();
    console.log(end - start);
}

function randomVal(num){
    var arr = [];
    for(var i=0;i

在chrome下的一個(gè)運(yùn)行情況（以100000個(gè)數(shù)為例,由于每次排序后數(shù)組都發(fā)生了改變，所以每次都創(chuàng)建了新數(shù)組，以100000的基數(shù)來(lái)算的話(huà)，雖然不是同一個(gè)數(shù)組，但是結(jié)果也是值得參考的）：




在firefox下的運(yùn)行結(jié)果：




不論是firefox還是chrome,第一種排序算法的時(shí)間都是最長(zhǎng)的，第二種是最快的，原生的sort方法比第二種方法稍微慢一點(diǎn)，但比第一種還是快多了。

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

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

相關(guān)文章

  • 一篇文章讓你真正了解快速排序

    摘要：但是大家了解阮一峰快排事件嗎，是否知道快排的最佳實(shí)踐本文從一個(gè)爭(zhēng)執(zhí)講起，通過(guò)生動(dòng)詳實(shí)的例子讓你真正了解快排。參考文檔快速排序復(fù)雜度分析如何看待文章面試官阮一峰版的快速排序完全是錯(cuò)的快速排序算法的優(yōu)化思路總結(jié) 只要是個(gè)工程師，就或多或少的知道快排，其中很多人都能輕松的寫(xiě)出一個(gè)快排的實(shí)現(xiàn)。但是大家了解阮一峰快排事件嗎，是否知道快排的最佳實(shí)踐？本文從一個(gè)爭(zhēng)執(zhí)講起，通過(guò)生動(dòng)詳實(shí)的例子讓你真正了...

    Jaden 評(píng)論0 收藏0

  • 面試官：快排會(huì)寫(xiě)嗎？

    摘要：快排可以說(shuō)是一道必知的常見(jiàn)面試題，同時(shí)也有多種實(shí)現(xiàn)方式。之所以使用隨機(jī)快速排序而不是普通的快排。其中交換數(shù)組元素位置，打印元素的方法我就沒(méi)貼了，代碼太長(zhǎng)你們也不方便看。 快排可以說(shuō)是一道必知的常見(jiàn)面試題，同時(shí)也有多種實(shí)現(xiàn)方式。在這篇文章中，我使用的是隨機(jī)三路快排。 之所以使用隨機(jī)快速排序而不是普通的快排。是因?yàn)榍罢呖梢允沟脭?shù)列有序的概率降低，從而使隨機(jī)快速排序平均速度是比快速排序要快的...

    UCloud 評(píng)論0 收藏0

  • Java數(shù)據(jù)結(jié)構(gòu)與算法——快速排序

    摘要：快排是一種不穩(wěn)定的排序算法，在經(jīng)過(guò)排序后，等值的元素的相對(duì)位置可能發(fā)生改變。 聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。 前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專(zhuān)題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本篇文章介紹排序算法中最常用也是面試中最容易考到的排序算法——快排，包括快排的思想和原理、java快排代碼、快排的特點(diǎn)性能和快排的適用場(chǎng)景。 0、其他排序算法索引(待更) java數(shù)據(jù)結(jié)構(gòu)與...

    Panda 評(píng)論0 收藏0

  • 精詞快排SEO不限指數(shù)任意關(guān)鍵詞1元/天最快最快隔天上首頁(yè)

    摘要：支持百度百度搜狗搜狗神馬搜索支持軟文內(nèi)頁(yè)優(yōu)化，有排名即可最快隔天上首頁(yè)效果絕佳，百度移動(dòng)新算法已經(jīng)上線(xiàn)，技術(shù)源頭廠(chǎng)家招商合作可獨(dú)立后臺(tái)量大價(jià)可談平臺(tái)新活動(dòng)聯(lián)系客服贈(zèng)送元余額 支持百度PC、百度Wap、搜狗PC、搜狗Wap、360PC、360Wap、神馬搜索 支持軟文內(nèi)頁(yè)優(yōu)化，有排名即可！ 最快隔天上首頁(yè)！效果絕佳！，百度PC/移動(dòng)新算法已經(jīng)上線(xiàn)！，技術(shù)源頭廠(chǎng)家招商合作可oem獨(dú)立后臺(tái) ...

    honmaple 評(píng)論0 收藏0

  • 記一次騰訊霸面---前端

    摘要：客戶(hù)端的瀏覽器根據(jù)雙方同意的安全等級(jí)，建立會(huì)話(huà)密鑰，然后利用網(wǎng)站的公鑰將會(huì)話(huà)密鑰加密，并傳送給網(wǎng)站。地址必須和一個(gè)網(wǎng)絡(luò)掩碼對(duì)應(yīng)使用缺一不可。網(wǎng)絡(luò)掩碼的主要作用是告訴計(jì)算機(jī)如何從地址中析取網(wǎng)絡(luò)標(biāo)識(shí)和主機(jī)標(biāo)識(shí)。 霸面的是前端實(shí)習(xí)生崗位，當(dāng)時(shí)聽(tīng)同學(xué)說(shuō)前端缺人，還特意設(shè)了一個(gè)霸面區(qū)，就去溜了個(gè)彎兒，畢竟不試試，怎么知道自己有多菜呢o(￣︶￣)o一面技術(shù)面，面試官關(guān)注的點(diǎn)一直在數(shù)據(jù)結(jié)構(gòu)、算法、計(jì)...

    ralap 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

galois

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<