? ? ?在算法中宁脊，排序的方法有很多種，大致可以分為五類贤姆，八種榆苞。插入排序分為：希爾排序，直接插入排序霞捡；選擇排序：簡單選擇排序坐漏，堆排序；交換排序：快速排序，冒泡排序仙畦；還有兩類為：歸并排序和基數(shù)排序。本文作為這個系列的第一講音婶，來介紹交換排序的第一種排序方式:快速排序慨畸。
? ? ?前端程序猿在操作數(shù)組的時候一定會遇到排序的需求，javascript數(shù)組默認會提供一個升序排序方法（ARRAY.prototype.sort）衣式。使用數(shù)組調(diào)用這個方法之后會返回一個排序之后的數(shù)組寸士，但是這個數(shù)組默認是對字符進行排序，簡單來說如果對數(shù)組[5,4,3,2,1]調(diào)用sort方法會得到升序的[1,2,3,4,5]碴卧，但是如果對數(shù)組[10,20,1,2]進行sort方法調(diào)用弱卡，會得到[1,10,2,20]這樣的進行首字符排序的數(shù)組。解決方法就是自己定義一個方法住册，返回任意兩個變量的差值婶博，將這個方法作為參數(shù)傳入sort()方法。這時返回值就為按數(shù)字排序荧飞。具體實現(xiàn)：
var a ?= [20,10,2,1];
a.sort();//返回值[1,10,2,20]
function compare(a,b) {
? ? ?return a-b;
}
a.sort(compare);//返回值[1,2,10,20]凡人。
? 前面介紹了一下javascript提供的排序方法，這個排序算法的本質(zhì)就是今天要介紹的快速排序算法叹阔∧又幔快速排序算法是由Tony Hoare在1959年提出的。這種排序算法和它的名字一樣耳幢，特點就是排序速度很快岸晦，維基百科上是這么形容他的：
When implemented well, it can be about two or three times faster than its main competitors,merge sortandheapsort.
Mathematical analysisof quicksort shows that,on average, the algorithm takesO(nlogn) comparisons to sortnitems. In theworst case, it makes O(n2) comparisons, though this behavior is rare.
在較優(yōu)的情況下，它所花費的時間可能是其他排序算法（如歸并排序睛藻，堆排序）的二分之一甚至是三分之一启上。對于快速排序進行數(shù)學分析顯示，它的平均時間復(fù)雜度僅僅為O（nlgn）修档。在極端的情況下碧绞，時間復(fù)雜度為O（n2）但是這種情況極難遇到。
可見快速排序是一種效率極高吱窝，速度很快的排序算法讥邻，快速排序?qū)嵸|(zhì)上用到了分治的思想，就是將一個復(fù)雜的問題轉(zhuǎn)化為幾個簡單的問題來逐一解決院峡。接下來兴使，就開始介紹快速排序算法。
要把一個數(shù)組進行快速排序和把大象裝進冰箱一樣照激，一共分三個步驟：
1发魄、在數(shù)組中找到一個支點，也可以叫做基準。
注：這個基準就是數(shù)組中任意一個元素励幼。
2汰寓、遍歷整個數(shù)組，將比基準大的元素放到基準的右面苹粟，將比基準小的元素放到基準的左面有滑。
3、對基準左面的數(shù)組和基準右面得數(shù)組重復(fù)前兩步嵌削。
看完上面的三個步驟毛好，很多人一定會覺得似懂非懂，實踐才能出真知苛秕，我舉一個例子：
待排序的數(shù)組：[5,4,3,2,1]
第一步肌访、這里默認以3為基準（哪個元素為基準都可以）
第二步、將數(shù)組中比3大的元素放到3的右側(cè)艇劫，比3小的元素放到3的左側(cè)——》[2,1,3,5,4]
第三步吼驶、這個時候這個數(shù)組拋去基準可以分為兩部分[2,1]，[5,4]港准；兩個數(shù)組
? ? ? ? ? ? [2,1]設(shè)基準為2旨剥，因為1比2小所以1放在2的左邊——》[1,2]
? ? ? ? ? ? [5,4]設(shè)基準為5，因為4比5小所以4放在5的左邊——》[4,5]
然后再重復(fù)第一步浅缸，發(fā)現(xiàn)繼續(xù)劃分的數(shù)組只有一個元素了轨帜，所以不需要在進行下去了，最后將分開的數(shù)組和基準進行結(jié)合就得到了排序之后的數(shù)組：[1,2]+[3]+[4,5]——》[1,2,3,4,5]
思路有了衩椒，下面就來進行代碼的實現(xiàn)：
代碼的實現(xiàn)也是那三個步驟蚌父，按部就班的進行實現(xiàn)。
第一步：
首先將快速排序封裝一個函數(shù)毛萌，參數(shù)可以傳入一個待排序的數(shù)組苟弛。
var quicklySort = function(arr){
};
由于后面要進行遞歸的進行調(diào)用，所以要設(shè)置一個限定條件阁将，也就是上面第三步最后膏秫，如果分治之后的數(shù)組的長度為1或者傳入的數(shù)組是個空數(shù)組，將函數(shù)停止運行做盅，并返回排序之后的數(shù)組：
if(arr.length<=1){
? ? ?return arr;
}
準備工作做完真正的開始上面的第一步操作：在數(shù)組中找到一個支點缤削，也可以叫做基準
這里為了方便我們將數(shù)組的二分之一的位置取為基準，并取到這個基準
var pivotIndex = Math.floor(arr.length/2);//這里調(diào)用了js當中的四舍五入方法吹榴，防止數(shù)組長度為奇數(shù)的情況亭敢，對數(shù)組進行小數(shù)位 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? // 舍去操作；另外Math.ceil()這個是舍去小數(shù)位图筹，整數(shù)位+1的效果帅刀；Math.round() ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?// 實現(xiàn)四舍五入;在js中最常用的三種對數(shù)字進行四舍五入的方法让腹。
var pivot = arr.splice(pivotIndex,1);//數(shù)組的splice方法，實現(xiàn)的數(shù)組定位刪除扣溺，插入的功能骇窍，第一個參數(shù)為刪除元素的索引，第 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//二個為刪除元素的個數(shù)锥余，第三個是在這個位置插入的元素像鸡。這里將基準保存到pivot變量 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? //中，并在數(shù)組中刪除哈恰。
第二步：遍歷整個數(shù)組，將比基準大的元素放到基準的右面志群，將比基準小的元素放到基準的左面着绷。
var left = [];//先定義存放左右元素的數(shù)組
var right = []
for(var i=0;i<arr.length;i++){
? ? ?if(arr[i]<pivot){
? ? ? ? ? ? ? left.push(arr[i]);
? ? ? }else{
? ? ? ? ? ? ? right.push(arr[i]);
? ? ?}
}
第三步、對左右數(shù)組繼續(xù)進行前兩步锌云，并將左右數(shù)組和基準拼到一起
return quicklySort(left).concat([pivot]+quicklySort(right));//數(shù)組的concat方法荠医，把兩個數(shù)組合并，如果只用加法操作符最后得 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//到的是一個排完序的字符串
雖然關(guān)于代碼篇幅很多桑涎，但是主要是我講解的文字彬向，代碼其實沒有很多，將這些偽代碼合并就是下面的這個方法攻冷。
關(guān)于快速排序的內(nèi)容就是以上的這些娃胆，可能好多程序猿都會覺得前端開發(fā)碰不到數(shù)據(jù)結(jié)構(gòu)，算法的知識等曼，在日常工作中可能永遠都不會需要去了解的很深里烦，沒什么用。其實我之前一直也是這種想法禁谦，上學的時候也覺得這種東西搞科學研究的時候才能用上胁黑，學會框架怎么用，怎么用語言的特性編代碼才是最關(guān)鍵的州泊，但是漸漸發(fā)現(xiàn)丧蘸。程序猿這類工作和修煉武功非常像，小時候玩過一個游戲叫天龍八部遥皂，游戲里面的主角僅僅學會絕世武功是沒用的力喷，需要搭配內(nèi)功心法才能發(fā)揮最大的威力。在程序開發(fā)中渴肉，程序語言也許就是絕世的武功冗懦，而數(shù)據(jù)結(jié)構(gòu)算法這樣的知識才是內(nèi)功，因為這些內(nèi)功不限于你會什么武功仇祭，只要你的內(nèi)功足夠深厚披蕉，什么武功能威震四方，但是如果你的武功非常強大，但是內(nèi)功嚴重不足没讲，也許就會練著絕世武功眯娱，但是發(fā)揮的效果也就和一般的野狐禪一樣，水平一直停步不前爬凑。在日常的程序開發(fā)中徙缴，面對同樣的問題，不同的人解決的方法可能會不同嘁信，雖然都能實現(xiàn)功能于样。但是只有內(nèi)功深厚的人才會寫出更優(yōu)的代碼，更易于維護的代碼潘靖。我想這也是國內(nèi)具有號召力的互聯(lián)網(wǎng)公司招聘的第一條就是精通數(shù)據(jù)結(jié)構(gòu)算法等計算機基礎(chǔ)知識穿剖，因為一門程序語言對于有點基礎(chǔ)的人來說一兩周就可以上手干活了，但是基礎(chǔ)知識的掌握不是一朝一夕可以掌握的卦溢，所以練好內(nèi)功糊余，才是王道！
這是我的第一篇博客单寂，希望自己能堅持下去贬芥，加油！
