深入了解javascript數(shù)組的sort方法

1、深入了解javascrip數(shù)組的sor方法在javascrip中，數(shù)組對象有一個有趣的方法sort它接收一個類型為函數(shù)的參數(shù)作為排序的依據(jù)。這意味著開發(fā)者只需要關注如何比較兩個值的大小，而不用管排序這件事內部是如何實現(xiàn)的。不過了解一下sor的內部實現(xiàn)也不是一件壞事，何不深入了解一下呢？算法課上，我們會接觸很多種排序算法，什么冒泡排序、選擇排序、快速排序、堆排序等等。那么avascrip的sor方法釆用哪種排序算法呢？要搞清楚這個問題，呃，直接看好了。v中對rra的實現(xiàn)是釆用javascrip完成的，粗看下來，使用了快速排序算法，但明顯比我們熟悉的快速排序要復雜。那么到底復雜在什么地方？為什么要

2、搞這么復雜？這是我們今天要探討的問題?？焖倥判蛩惴焖倥判蛩惴ㄖ员环Q為快速排序算法，是因為它能達到最佳和平均時間復雜度均為Q是一種應用非常廣泛的排序算法。它的原理并不復雜，先找出一個基準元素（pivot任意元素均可），然后讓所有元素跟基準元素比較，比基準元素小的，放到一個集合中，其他的放到另一個集合中；再對這兩個集合執(zhí)行快速排序，最終得到完全排序好的序列。所以快速排序的核心是不斷把原數(shù)組做切割，切割成小數(shù)組后再對小數(shù)組進行相同的處理，這是一種典型的分治的算法設計思路。實現(xiàn)一個簡單的快速排序算法并不困難。我們不妨試一下：ctiouickSort(arr,fif(!arrarr.lengtif

3、(arr.lengtvarpivot=arrvarsmallSetvarbigSet=for(vari=1iarrifnc(arri，,pivot)smallSet.push(arri，elsect.push(arriarrickSort(smac).concat(pivot).concatickSort這是一個非常基礎的實現(xiàn)，選取數(shù)組的第一項作為基準元素。原地（ip）a排序我們可以注意到，上面的算法中，我們其實是創(chuàng)建了一個新的數(shù)組作為計算結果，從空間使用的角度看是不經濟的。javascrip的快速排序算法中并沒有像上面的代碼那樣創(chuàng)建一個新的數(shù)組，而是在原數(shù)組的基礎上，通過交換元素位置實現(xiàn)排序

4、。所以，類似于ps、popspice幾個方法，sor方法也是會修改原數(shù)組對象的！我們前面說過，快速排序的核心在于切割數(shù)組。那么如果只是在原數(shù)組上交換元素，怎么做到切割數(shù)組呢？很簡單，我們并不需要真的把數(shù)組切割出來，只需要記住每個部分起止的索引號。舉個例子，假設有一個數(shù)組，選取第一項為基準元素，那么按照原始的快速排序算法，會把這個數(shù)組切割成兩個小數(shù)組：。但是我們同樣可以不切割，先通過比較、交換元素，將原數(shù)組修改成，再根據(jù)基準元素的位置，認為號元素是一組，號元素是一組，為了表述方便，我這里將比基準元素小的元素組成的分區(qū)叫小數(shù)分區(qū)，另一個分區(qū)叫大數(shù)分區(qū)。這很像電腦硬盤的分區(qū)，并不是真的把硬盤分成了盤

5、、盤，而是記錄下一些起止位置，在邏輯上分成了若干個分區(qū)。類似的，在快速排序算法中，我們也把這個過程叫做分區(qū)（partition。所以相應的，我也要修改一下之前的說法了，快速排序算法的核心是分區(qū)。說了這么多，還是實現(xiàn)一個帶分區(qū)的快速排序吧：ctionswap(arr,from,toif(from=to)returnvartemparrfrom，;arrfrom，arrto，;arrto，=temp;unctionQuickSortWithPartition(arr,func,from,toif(!arrarr.length)return，;if(arr.lengt1)returnarr;frof

6、rom|to=to|arrth-varpivot=arrfrom，varsmallfrom;varbigIndex=from+1;for(;bigIndex=to;bigIndex+)if(func(arrbigIndex,pivot)=to-1)returnarr;varpivot=arrfrom;varsmallEnd=from+1;varbigBegin=to;while(smallEnd0&smallEndbigBegin)bigBegin-;while(func(arrsmallEnd,pivot)0&smallEndbigBegin)smallEnd+;if(smallEnd1;v

7、ari0=arrfrom;vari1=arrto;vari2=arrmiddle;vartemp;if(func(i0,i1)0)temp=i0;=i1;=temp;if(func(i0,i2)0)arrmiddle=i0;arrfrom=i2;arrto=i1;returni0;elsearrfrom=i0;if(func(i1,i2)0)arrmiddle=i1;arrto=i2;returni1;elsearrmiddle=i2;arrto=i1;returni2;這個例子里我完全沒管基準元素的位置，一是降低復雜度，另一個原因是下面討論重復元素處理時，基準元素的位置沒什么意義。不過我把最

8、小的值賦給了第一個元素，最大的值賦給了第二個元素，后面處理重復元素時會有幫助。當然，僅僅是三數(shù)取中獲得的基準元素，也不見得是可靠的。于是有一些其他的取中值的方法出現(xiàn)。有幾種比較典型的手段，一種是平均間隔取一個元素，多個元素取中位數(shù)(即多取幾個，增加可靠性)；一種是對三數(shù)取中進行遞歸運算，先把大數(shù)組平均分成三塊，對每一塊進行三數(shù)取中，會得到三個中值，再對這三個中值取中位數(shù)。不過查閱v8的源代碼，發(fā)現(xiàn)v8的基準元素選取更為復雜。如果數(shù)組長度不超過1000,則進行基本的三數(shù)取中；如果數(shù)組長度超過1000,那么v8的處理是除去首尾的元素，對剩下的元素每隔200左右(200215,并不固定)挑出一個元素

9、。對這些元素排序，找出中間的那個，并用這個元素跟原數(shù)組首尾兩個元素一起進行三數(shù)取中。這段代碼我就不寫了。針對重復元素的處理到目前為止，我們在處理元素比較的時候比較隨意，并沒有太多地考慮元素相等的問題。但實際上我們做了這么多性能優(yōu)化，對于重復元素引起的性能問題并沒有涉及到。重復元素會帶來什么問題呢？設想一下,一個數(shù)組里如果所有元素都相等,基準元素不管怎么選都是一樣的。那么在分區(qū)的時候，必然出現(xiàn)除基準元素外的其他元素都被分到一起去了，進入最差性能的case。那么對于重復元素應該怎么處理呢？從性能的角度，如果發(fā)現(xiàn)一個元素與基準元素相同，那么它應該被記錄下來，避免后續(xù)再進行不必要的比較。所以還是得改分

10、區(qū)的代碼。functionQuickSortWithPartitionDump(arr,func,from,to)if(!arr|!arr.length)return;from=from|0;to=to|arr.length-1;if(from=to-1)returnarr;varpivot=getPivot(arr,func,from,to);varsmallEnd=from;varbigBegin=to;for(vari=smallEnd+1;ibigBegin;i+)varorder=func(arri,pivot);if(order0)while(bigBegini&order0)bi

11、gBegin-;order=func(arrbigBegin,pivot);if(bigBegin=i)break;swap(arr,i,bigBegin);if(order0)swap(arr,i,smallEnd);smallEnd+;QuickSortWithPartitionDump(arr,func,from,smallEnd);QuickSortWithPartitionDump(arr,func,bigBegin,to);returnarr;簡單解釋一下這段代碼，上文已經說過，在getPivot方法中，我將比基準小的元素放到第一位，把比基準大的元素放到最后一位。定義三個變量sma

12、llEnd、bigBegin、i,從from到smallEnd之間的元素都比基準元素小，從smallEnd到i之間的元素都和基準元素一樣大，從倒bigBegin之間的元素都是還沒有比較的，從bigBegin到to之間的元素都比基準元素大。了解這個關系就好理解這段代碼了。遍歷從smallEnd+1到bigBegin之間的元素：*如果這個元素小于基準，那么smallEnd增加1,這時smallEnd位置的元素是等于基準元素的(或者此時smallEnd與i相等)，交換smallEnd與i處的元素就可以了。*如果這個元素大于基準，相對比較復雜一點。此時讓bigBegin減小1,檢查大數(shù)分區(qū)前面一個元素

13、是不是大于基準，如果大于基準，重復此步驟，不斷讓bigBegin減小1，直到找到不比基準大的元素(如果這個過程中，發(fā)現(xiàn)DigBegin與i相等，則中止遍歷，說明分區(qū)結束)。找到這個不比基準大小元素時需要區(qū)分是不是比基準小。如果比基準小，需要做兩步交換，先將位置的大數(shù)和bigBegin位置的小數(shù)交換，這時跟第一種case同時，smallEnd增加1，并且將i位置的小數(shù)和smallEnd位置的元素交換。如果和基準相等，則只需要將位置的大數(shù)和bigBegin位置的小數(shù)交換。*如果這個元素與基準相等，什么也不用做。小數(shù)組優(yōu)化對于小數(shù)組(小于16項或10項。v8認為10項以下的是小數(shù)組。)，可能使用快速

14、排序的速度還不如平均復雜度更高的選擇排序。所以對于小數(shù)組，可以使用選擇排序法要提高性能，減少遞歸深度。functioninsertionSort(a,func,from,to)for(vari=from+1;i=from;j-)vartmp=aj;if(func(tmp,element)0)aj+1=tmp;elsebreak;aj+1=element;v8引擎沒有做的優(yōu)化由于快速排序的不穩(wěn)定性(少數(shù)情況下性能差，前文已經詳細描述過)，DavidMusser于1997設計了內省排序法(Introsort)。這個算法在快速排序的基礎上，監(jiān)控遞歸的深度。一旦長度為n的數(shù)組經過了logn層遞歸(快速

15、排序算法最佳情況下的遞歸層數(shù))還沒有結束的話，就認為這次快速排序的效率可能不理想，轉而將剩余部分換用其他排序算法，通常使用堆排序算法(Heapsort，最差時間復雜度和最優(yōu)時間復雜度均為nlogn)。v8引擎額外做的優(yōu)化快速排序遞歸很深，如果遞歸太深的話，很可以出現(xiàn)“爆?！保覀儜摫M可能避免這種情況。上面提到的對小數(shù)組采用選擇排序算法，以及釆用內省排序算法都可以減少遞歸深度。不過/8引擎中，做了一些不太常見的優(yōu)化，每次我們分區(qū)后，v8引擎會選擇元素少的分區(qū)進行遞歸，而將元素多的分區(qū)直接通過循環(huán)處理，無疑這樣的處理大大減小了遞歸深度。我大致扌田8這種處理的過程寫一下：functionquickSort(arr,from,to)while(true)/排序分區(qū)過程省略/.if(to-bigBeginsmallEnd-from)quickSort(a,bigBegin,to);to=smallEnd;elsequickSort(a,from,smallEnd);from=bigBegin;不得不說是一個很巧妙的實現(xiàn)?？偨Y不知不覺這篇文章寫了這么長。本來想對比各種優(yōu)化之間的性能差異，現(xiàn)在看來也沒有什么必要