資訊專欄INFORMATION COLUMN
摘要：寫這篇文章源于之前的一次面試以及網(wǎng)上看到各種說原生的比快排快的例子，因為他們都沒有寫好快排。
寫這篇文章源于之前的一次面試以及網(wǎng)上看到各種說原生的sort比快排快的例子，因為他們都沒有寫好快排。面試的時候讓我寫一個快排，我寫出了我在網(wǎng)上看的的很簡潔的一段代碼（后來發(fā)現(xiàn)這個代碼在數(shù)據(jù)結(jié)構(gòu)和算法JavaScript描述這本書上也有）：
function quickSort(arr){
if(arr.length < 1){
return [];
}
var left = [],right = [],flag = arr[0];
for(var i=1;i
這樣寫的話，乍一看確實是快排的思想，把比主元小的元素放到左數(shù)組，把比主元大的元素放到右數(shù)組，然后分別對左右數(shù)組的元素進行排序最終拼接成新的數(shù)組。
但是計算機課程里講解快排的時候都不是這樣講解的，一趟快速排序的算法一般是這樣講解的：
設(shè)置兩個變量i、j，排序開始的時候：i=0，j=N-1；
以第一個數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]；
從j開始向前搜索，即由后開始向前搜索(j--)，找到第一個小于key的值A(chǔ)[j]，將A[j]和A[i]互換；
從i開始向后搜索，即由前開始向后搜索(i++)，找到第一個大于key的A[i]，將A[i]和A[j]互換；
重復(fù)第3、4步，直到i=j；
采用js實現(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);
}
對比這兩中快排的寫法，在時間復(fù)雜度上都是O(nlogn)，但是第二種寫法使用了更少的空間，第一種寫法的空間復(fù)雜度是O(nlogn),而第二種的空間復(fù)雜度是O(logn),而且對數(shù)組的操作都在原數(shù)組上進行，減去了創(chuàng)建空間的消耗和時間，在性能上無疑有了更多的提升。
下面是三種排序算法的一個對比：
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個數(shù)為例,由于每次排序后數(shù)組都發(fā)生了改變，所以每次都創(chuàng)建了新數(shù)組，以100000的基數(shù)來算的話，雖然不是同一個數(shù)組，但是結(jié)果也是值得參考的）：
在firefox下的運行結(jié)果：
不論是firefox還是chrome,第一種排序算法的時間都是最長的，第二種是最快的，原生的sort方法比第二種方法稍微慢一點，但比第一種還是快多了。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/83073.html
摘要：但是大家了解阮一峰快排事件嗎，是否知道快排的最佳實踐本文從一個爭執(zhí)講起，通過生動詳實的例子讓你真正了解快排。參考文檔快速排序復(fù)雜度分析如何看待文章面試官阮一峰版的快速排序完全是錯的快速排序算法的優(yōu)化思路總結(jié) 只要是個工程師，就或多或少的知道快排，其中很多人都能輕松的寫出一個快排的實現(xiàn)。但是大家了解阮一峰快排事件嗎，是否知道快排的最佳實踐？本文從一個爭執(zhí)講起，通過生動詳實的例子讓你真正了...
摘要：快排可以說是一道必知的常見面試題，同時也有多種實現(xiàn)方式。之所以使用隨機快速排序而不是普通的快排。其中交換數(shù)組元素位置，打印元素的方法我就沒貼了，代碼太長你們也不方便看。 快排可以說是一道必知的常見面試題，同時也有多種實現(xiàn)方式。在這篇文章中，我使用的是隨機三路快排。 之所以使用隨機快速排序而不是普通的快排。是因為前者可以使得數(shù)列有序的概率降低，從而使隨機快速排序平均速度是比快速排序要快的...
摘要：快排是一種不穩(wěn)定的排序算法，在經(jīng)過排序后，等值的元素的相對位置可能發(fā)生改變。 聲明：碼字不易，轉(zhuǎn)載請注明出處，歡迎文章下方討論交流。 前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會不定時更新，歡迎各位讀者監(jiān)督。本篇文章介紹排序算法中最常用也是面試中最容易考到的排序算法——快排，包括快排的思想和原理、java快排代碼、快排的特點性能和快排的適用場景。 0、其他排序算法索引(待更) java數(shù)據(jù)結(jié)構(gòu)與...
摘要：支持百度百度搜狗搜狗神馬搜索支持軟文內(nèi)頁優(yōu)化，有排名即可最快隔天上首頁效果絕佳，百度移動新算法已經(jīng)上線，技術(shù)源頭廠家招商合作可獨立后臺量大價可談平臺新活動聯(lián)系客服贈送元余額 支持百度PC、百度Wap、搜狗PC、搜狗Wap、360PC、360Wap、神馬搜索 支持軟文內(nèi)頁優(yōu)化，有排名即可！ 最快隔天上首頁！效果絕佳！，百度PC/移動新算法已經(jīng)上線！，技術(shù)源頭廠家招商合作可oem獨立后臺 ...
摘要：客戶端的瀏覽器根據(jù)雙方同意的安全等級，建立會話密鑰，然后利用網(wǎng)站的公鑰將會話密鑰加密，并傳送給網(wǎng)站。地址必須和一個網(wǎng)絡(luò)掩碼對應(yīng)使用缺一不可。網(wǎng)絡(luò)掩碼的主要作用是告訴計算機如何從地址中析取網(wǎng)絡(luò)標識和主機標識。 霸面的是前端實習(xí)生崗位，當時聽同學(xué)說前端缺人，還特意設(shè)了一個霸面區(qū)，就去溜了個彎兒，畢竟不試試，怎么知道自己有多菜呢o(￣︶￣)o一面技術(shù)面，面試官關(guān)注的點一直在數(shù)據(jù)結(jié)構(gòu)、算法、計...
閱讀 8014·2023-04-25 14:36
閱讀 1913·2021-11-22 09:34
閱讀 2245·2019-08-30 15:55
閱讀 3222·2019-08-30 11:19
閱讀 1386·2019-08-29 15:17
閱讀 643·2019-08-29 12:47
閱讀 3080·2019-08-26 13:38
閱讀 2727·2019-08-26 11:00
