作為程序員必備課題之一的算法系列中糊余，排序這個(gè)最為常見(jiàn)的算法實(shí)現(xiàn)也是很有必要掌握的霍殴，所以做一個(gè)系列的總結(jié)，便于交流學(xué)習(xí)
廢話少說(shuō)帝簇，進(jìn)入正題
如有誤徘郭，辛苦指正
背景介紹
（Quicksort）是對(duì)
的一種改進(jìn)靠益。
快速排序由在1960年提出。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分残揉，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小胧后，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以
抱环，以此達(dá)到整個(gè)數(shù)據(jù)變成
绩卤。 --- 快速排序算法
核心特點(diǎn)
(1)、在所需要排序的集合中江醇，選擇一個(gè)元素作為"基準(zhǔn)"（pivot）。
(2)何暇、然后以這個(gè)基準(zhǔn)值作為判斷依據(jù)陶夜，小于它則放到他的左邊，反之則放到另一邊裆站。
(3)条辟、最后對(duì)兩遍不停的重復(fù)步驟2，是的最終只剩下一個(gè)元素位置宏胯。
舉個(gè)例子
[ 1, 5, 4, 3, 6, 2, 7 ]
我們隨便定一個(gè)基準(zhǔn)值羽嫡，假設(shè)為3，那么根據(jù)核心特點(diǎn)肩袍，第一次執(zhí)行完畢后得到兩個(gè)數(shù)組
小于3的：[ 1, 2 ]
大于3的：[ 5, 4, 6, 7]
將小于3的的數(shù)組重復(fù)執(zhí)行步驟杭棵，根據(jù)核心特點(diǎn)，最后退出的條件是元素為1氛赐，所以小于3的數(shù)組最終為
[ 1, 2 ]
再將大于3的數(shù)組做同樣的操作魂爪，假設(shè)基準(zhǔn)值為6得到
小于6的：[ 5, 4 ]
大于6的：[ 7 ]
......
重復(fù)操作后最終將所有的數(shù)組連接起來(lái)即可
此時(shí)應(yīng)該大概了解了快速排序的算法流程，但是對(duì)細(xì)節(jié)還略有模糊艰管，那么我們?cè)诮Y(jié)合代碼做理解
代碼示例
1滓侍、我們創(chuàng)建一個(gè)排序方法，并接受一個(gè)參數(shù)牲芋，就是我們需要排序的數(shù)組
function quickSort( _array ){
}
2撩笆、我們需要設(shè)定一個(gè)基準(zhǔn)值，并創(chuàng)建兩個(gè)數(shù)組用來(lái)存放小于/大于基準(zhǔn)值的數(shù)的集合
function quickSort( _array ){
//假設(shè)我取了數(shù)組中間的數(shù)作為基準(zhǔn)值缸浦，得到他的下標(biāo), 我們使用~~來(lái)獲取值為floor時(shí)的整數(shù)部分夕冲，也可以使用Math.floor()來(lái)實(shí)現(xiàn)
var _pivot_index = ~~( _array.length / 2 );
//基準(zhǔn)值
var _pivot = _array.splice(_pivot_index, 1)[0];
//我們需要兩個(gè)數(shù)組來(lái)存放大于小于基準(zhǔn)值的集合
var _left = [] ,
_right = [];
}
3、我們先來(lái)進(jìn)行一次循環(huán)餐济，將大于/小于基準(zhǔn)值的數(shù)的集合耘擂，區(qū)分開來(lái)
function quickSort( _array ){
//假設(shè)我取了數(shù)組中間的數(shù)作為基準(zhǔn)值，得到他的下標(biāo), 我們使用~~來(lái)獲取值為floor時(shí)的整數(shù)部分絮姆，也可以使用Math.floor()來(lái)實(shí)現(xiàn)
var _pivot_index = ~~( _array.length / 2 );
//基準(zhǔn)值
var _pivot = _array.splice(_pivot_index, 1)[0];
//我們需要兩個(gè)數(shù)組來(lái)存放大于小于基準(zhǔn)值的集合
var _left = [] ,
_right = [];
for( var i = 0; i < _array.length; i++){
//這里進(jìn)行判斷醉冤，如果大于基準(zhǔn)值則放到右側(cè)數(shù)組秩霍，反之則放到左側(cè)
_array[i] > _pivot ? _right.push( _array[i] ) : _left.push( _array[i] );
}
}
4、這樣我們區(qū)分?jǐn)?shù)組就已經(jīng)完成了蚁阳，接下來(lái)我們就是要將左右兩個(gè)數(shù)組铃绒，分別作為參數(shù)傳進(jìn)來(lái)，執(zhí)行相同的操作螺捐，那么順理成章的我們就想到了遞歸實(shí)現(xiàn), 所以我門增加一個(gè)return 遞歸操作
function quickSort( _array ){
// 假設(shè)我取了數(shù)組中間的數(shù)作為基準(zhǔn)值颠悬，得到他的下標(biāo), 我們使用~~來(lái)獲取值為floor時(shí)的整數(shù)部分，也可以使用Math.floor()來(lái)實(shí)現(xiàn)
var _pivot_index = ~~( _array.length / 2 );
//基準(zhǔn)值
var _pivot = _array.splice(_pivot_index, 1)[0];
// 我們需要兩個(gè)數(shù)組來(lái)存放大于小于基準(zhǔn)值的集合
var _left = [] ,
_right = [];
for( var i = 0; i < _array.length; i++){
// 這里進(jìn)行判斷定血，如果大于基準(zhǔn)值則放到右側(cè)數(shù)組赔癌，反之則放到左側(cè)
_array[i] > _pivot ? _right.push( _array[i] ) : _left.push( _array[i] );
}
// 因?yàn)槲覀冏罱K要將拆分的數(shù)組連接起來(lái)，所以這里可以使用concat方法
// 遞歸左邊的數(shù)組 連接基準(zhǔn)值 在鏈接遞歸右邊的數(shù)組
return quickSort( _left ).concat( [ _pivot ], quickSort( _right ) );
}
5澜沟、最后我們知道灾票，遞歸的一個(gè)必要點(diǎn)就是退出條件，否則程序會(huì)進(jìn)入死循環(huán)茫虽，根據(jù)上面的核心特點(diǎn)我們知道刊苍，此時(shí)退出的條件就是當(dāng)數(shù)組的長(zhǎng)度小于等于1時(shí)，遞歸退出濒析，那么我們?cè)谧铋_始增加一個(gè)if判斷
function quickSort( _array ){
// 這里我們?cè)黾右粋€(gè)遞歸退出條件正什，當(dāng)數(shù)組長(zhǎng)度小于等于1時(shí)，退出
if ( _array.length <= 1 ) return _array;
// 假設(shè)我取了數(shù)組中間的數(shù)作為基準(zhǔn)值号杏，得到他的下標(biāo), 我們使用~~來(lái)獲取值為floor時(shí)的整數(shù)部分婴氮，也可以使用Math.floor()來(lái)實(shí)現(xiàn)
var _pivot_index = ~~( _array.length / 2 );
//基準(zhǔn)值
var _pivot = _array.splice(_pivot_index, 1)[0];
// 我們需要兩個(gè)數(shù)組來(lái)存放大于小于基準(zhǔn)值的集合
var _left = [] ,
_right = [];
for( var i = 0; i < _array.length; i++){
// 這里進(jìn)行判斷，如果大于基準(zhǔn)值則放到右側(cè)數(shù)組馒索，反之則放到左側(cè)
_array[i] > _pivot? _right.push( _array[i] ) : _left.push( _array[i] );
}
// 因?yàn)槲覀冏罱K要將拆分的數(shù)組連接起來(lái)莹妒，所以這里可以使用concat方法
// 遞歸左邊的數(shù)組 連接基準(zhǔn)值 在鏈接遞歸右邊的數(shù)組
return quickSort( _left ).concat( [ _pivot ], quickSort( _right ) );
}
至此我們就完成了快速排序的基本實(shí)現(xiàn)。
當(dāng)然此方法實(shí)現(xiàn)只能作為快速了解快排思路的例子绰上，實(shí)際運(yùn)用中旨怠，會(huì)帶來(lái)更大的內(nèi)存開銷等等，等待系列做完蜈块，將會(huì)逐一分析鉴腻，并提供更好的思路。
