快排

galois 發布于2019-08-20 16:40 / 1357人閱讀

摘要：寫這篇文章源于之前的一次面試以及網上看到各種說原生的比快排快的例子，因為他們都沒有寫好快排。

寫這篇文章源于之前的一次面試以及網上看到各種說原生的sort比快排快的例子，因為他們都沒有寫好快排。面試的時候讓我寫一個快排，我寫出了我在網上看的的很簡潔的一段代碼（后來發現這個代碼在數據結構和算法JavaScript描述這本書上也有）：

function quickSort(arr){
    if(arr.length < 1){
            return [];
    }
    var left = [],right = [],flag = arr[0];
    for(var i=1;i
這樣寫的話，乍一看確實是快排的思想，把比主元小的元素放到左數組，把比主元大的元素放到右數組，然后分別對左右數組的元素進行排序最終拼接成新的數組。
但是計算機課程里講解快排的時候都不是這樣講解的，一趟快速排序的算法一般是這樣講解的：

設置兩個變量i、j，排序開始的時候：i=0，j=N-1；
以第一個數組元素作為關鍵數據，賦值給key，即key=A[0]；
從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個小于key的值A[j]，將A[j]和A[i]互換；
從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的A[i]，將A[i]和A[j]互換；
重復第3、4步，直到i=j；

采用js實現的版本如下：
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);
}

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

下面是三種排序算法的一個對比：
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下的一個運行情況（以100000個數為例,由于每次排序后數組都發生了改變，所以每次都創建了新數組，以100000的基數來算的話，雖然不是同一個數組，但是結果也是值得參考的）：

在firefox下的運行結果：

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

云服務器 GPU云服務器快排快排會寫嗎

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

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

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

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

Jaden 2019-08-23 13:58 評論0 收藏0
面試官：快排會寫嗎？

摘要：快排可以說是一道必知的常見面試題，同時也有多種實現方式。之所以使用隨機快速排序而不是普通的快排。其中交換數組元素位置，打印元素的方法我就沒貼了，代碼太長你們也不方便看。快排可以說是一道必知的常見面試題，同時也有多種實現方式。在這篇文章中，我使用的是隨機三路快排。之所以使用隨機快速排序而不是普通的快排。是因為前者可以使得數列有序的概率降低，從而使隨機快速排序平均速度是比快速排序要快的...

UCloud 2019-08-16 13:41 評論0 收藏0
Java數據結構與算法——快速排序

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

Panda 2019-08-16 11:12 評論0 收藏0
精詞快排SEO不限指數任意關鍵詞1元/天最快最快隔天上首頁

摘要：支持百度百度搜狗搜狗神馬搜索支持軟文內頁優化，有排名即可最快隔天上首頁效果絕佳，百度移動新算法已經上線，技術源頭廠家招商合作可獨立后臺量大價可談平臺新活動聯系客服贈送元余額支持百度PC、百度Wap、搜狗PC、搜狗Wap、360PC、360Wap、神馬搜索支持軟文內頁優化，有排名即可！最快隔天上首頁！效果絕佳！，百度PC/移動新算法已經上線！，技術源頭廠家招商合作可oem獨立后臺 ...

honmaple 2021-11-24 10:30 評論0 收藏0
記一次騰訊霸面---前端

摘要：客戶端的瀏覽器根據雙方同意的安全等級，建立會話密鑰，然后利用網站的公鑰將會話密鑰加密，并傳送給網站。地址必須和一個網絡掩碼對應使用缺一不可。網絡掩碼的主要作用是告訴計算機如何從地址中析取網絡標識和主機標識。霸面的是前端實習生崗位，當時聽同學說前端缺人，還特意設了一個霸面區，就去溜了個彎兒，畢竟不試試，怎么知道自己有多菜呢o(￣︶￣)o一面技術面，面試官關注的點一直在數據結構、算法、計...

ralap 2019-08-22 16:25 評論0 收藏0