本文是lhyt本人原創(chuàng)检痰，希望用通俗易懂的方法來理解一些細節(jié)和難點。轉(zhuǎn)載時請注明出處艾扮。文章最早出現(xiàn)于本人github
0.前言
相信大家面試的時候都要經(jīng)歷手寫什么什么排序這種事情吧风钻，要不就是大概說一下思路活喊。不許用各種語言封裝好的函數(shù)云头、api捐友，僅僅用原生的方法把他寫出來。雖然看起來沒什么意思溃槐，但是這也是考察一個人的基礎(chǔ)有沒有扎實楚殿、編程思想好不好的一種方法。
重要的事情說三遍：
主要理解快速排序８吞怠！砌溺！
主要理解快速排序Ｓ吧妗！规伐！
主要理解快速排序Ｐ非恪！猖闪！
而且要滾瓜爛熟鲜棠！
以下所有的排序都是升序
1.冒泡排序
先說最簡單的吧，冒泡培慌，就是指數(shù)值大的豁陆，就是一個大氣泡，慢慢冒到后面（水面）去吵护。對于要排序的數(shù)組盒音，一個個去遍歷表鳍，大的數(shù)往后移。往后移怎么做到呢祥诽，就是遍歷的時候譬圣，兩個數(shù)中（第j和j+1個）要是誰比較大，誰在后面（交換位置）雄坪。氣泡都聚集在水面（大數(shù)都從后面聚集在一起厘熟，所以每次第二層遍歷都會到len-1-j截止）
時間復(fù)雜度O(n^2)，如果是已經(jīng)排好的情況是O（n）
function bubble(arr){
for(var i = 0,len = arr.length;i
for (var j = 0; i < len-1-j; j++) {
if(arr[j]>arr[j+1]){
var temp = arr[j+1]
arr[j] = arr[j+1]
arr[j] = temp
}
}
}
return arr
}
2.快速排序（重點）
快排是面試問得最多的了维哈，也是目前用得最多绳姨，效率最穩(wěn)的方法”颗快速排序的最慢情況是O(n2)就缆，升序的時候。但它的數(shù)學期望是O(n log n) 谒亦，且O(n log n)記號中隱含的常數(shù)因子很小竭宰，比復(fù)雜度穩(wěn)定等于O(n log n)的歸并排序要小很多。對絕大多數(shù)順序性較弱的隨機數(shù)列而言份招，快速排序總是占優(yōu)切揭。
首先，取一個基準值（我們?nèi)〉谝粋€锁摔，也可以取中間廓旬、取最后都行），接著讓小于基準值的在左邊谐腰，大于的在右邊孕豹，分成左右兩堆。然后分別對左邊和右邊那堆采取同樣的操作十气，取基準值励背，讓基準值左邊都是小于他的，右邊都是大于他的砸西。一直重復(fù)操作叶眉，直到全部升序。
2.1另外開辟兩個空數(shù)組
這種方法容易理解芹枷，但是依賴另外開辟出來的數(shù)組衅疙。我們?nèi)〉谝粋€作為基準，從第二（特別注意鸳慈，第二個開始饱溢！不然棧溢出）個開始遍歷，小于基準的數(shù)放在左數(shù)組（left）走芋，大于基準的放在右數(shù)組理朋，接著對左數(shù)組和右邊數(shù)組重復(fù)操作絮识，再對左邊數(shù)組的左邊和右邊進行操作......直到數(shù)組長度為1
function quick(arr){
if(arr.length <= 1){
return arr
}
var pivot = arr[0]
var left = []
var right = []
var len = arr.length
for(var i = 1;i
if(arr[i]>pivot){
right.push(arr[i])
}else{
left.push(arr[i])
}
}
return quick(left).concat([pivot],quick(right))
}
當然網(wǎng)上也有人家從中間開始的，中間開始的話嗽上，就用splice去除這個值次舌，再給pivot賦值
2.2直接在原數(shù)組操作
這種比較難理解，但是不會占用其他內(nèi)存兽愤”四睿基準值也是取第一個，quick傳入3個參數(shù)：數(shù)組浅萧，子數(shù)組的起始位置逐沙、子數(shù)組的結(jié)束位置。第一次賦值肯定是quick（arr）洼畅，left和right是undefined吩案，left和right默認是第一個和最后一個數(shù)的索引。 partitionIndex是基準值索引帝簇。
核心部分是中間判斷l(xiāng)eft
取第一個基準值徘郭，從第二個（index）開始遍歷。index是目前最后一個小于基準值的索引（其實是留給基準值自己的一個空位）丧肴。如果遍歷中第i個有小于基準值的残揉，i與index互換，index再+1芋浮，這是什么效果呢抱环，可以看一下：8，5纸巷，10镇草，7，6的演示
基準值是8瘤旨，從5開始遍歷（var i = index; i <= right; i++）梯啤。
i=1發(fā)現(xiàn)5<8，arr【1】與arr【1】交換位置裆站，index+1，此時數(shù)組不變8黔夭，5宏胯，10，7本姥，6肩袍，但是index已經(jīng)是2
i=2發(fā)現(xiàn)10>8，跳過婚惫，index=2
i=3發(fā)現(xiàn)7<8氛赐，arr【3】與arr【2】交換魂爪，8，5艰管，7滓侍，10，6牲芋，index=3
i=4發(fā)現(xiàn)6<8撩笆，arr【4】與arr【3】交換，8缸浦，5夕冲，7，6裂逐，10歹鱼，index=4
遍歷已經(jīng)完成，把基準值和最后一個小于他的arr【index-1】互換6卜高，5弥姻，7，8篙悯，10蚁阳，已經(jīng)完成了基準值左邊都是小于他的、右邊都是大于他的目的鸽照。
一個模塊的操作完成螺捐，基準值索引partitionIndex變成index-1
接下來就是對分出來的左數(shù)組和右數(shù)組重復(fù)的遞歸操作
function quick(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeof left == 'number' ? left : 0,
right = typeof right == 'number' ? right : len-1;
if (left < right) {//保證小于基準值的在左邊，大的在右邊
var pivot = left, //基準值是數(shù)組的第一個
index = pivot + 1; //從數(shù)組的第二個開始
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
var temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
index++;
}
}
var temp = arr[pivot];
arr[pivot] = arr[index - 1];
arr[index - 1] = temp;
partitionIndex = index-1;
quick(arr, left, partitionIndex-1);
quick(arr, partitionIndex+1, right);
}
return arr;
}
3.選擇排序
表現(xiàn)最穩(wěn)定的排序之一矮燎，無論什么數(shù)據(jù)進去都是O(n2)復(fù)雜度定血，但是依賴額外內(nèi)存保存最小值
數(shù)組長度為len的數(shù)組中進行選擇排序時：
取后len個的最小值放數(shù)組第一個位置
取后len-1個的最小值放數(shù)組第二個位置
取后len-2個的最小值放數(shù)組第三個位置
.......
顯然，最后一個就是最大的诞外，前面的已經(jīng)完成了排序
function select(arr){
var min //保存運算過程中最小值索引
var temp
for (var i = 0,len = arr.length; i
min = i //先默認最小是自己
for(var j = i+1;j
if(arr[min]>arr[j]){
min = j //記錄更小的值的索引
}
}
temp = arr[i]
arr[i] = arr[min]
arr[min] = temp
}
return arr
}
4.插入排序
就像打牌一樣澜沟，自己是怎么整理的呢。拿著一張牌峡谊，一個個往下去對比茫虽，發(fā)現(xiàn)下一個大于（或等于）自己，上一個小于（或等于）自己既们，那就把他放在中間濒析。復(fù)雜度穩(wěn)定O（n^2）,最好的情況是已經(jīng)排序完成時O（n），依賴額外內(nèi)存啥纸，保存當前遍歷的數(shù)
function insert(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;//小于自己的數(shù)的索引
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];//如果滿足條件号杏，把當前的數(shù)插入中間
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
5.計數(shù)排序
將數(shù)組區(qū)間取出來（【min，max】）斯棒，然后對數(shù)組進行遍歷盾致，計算每一個數(shù)組元素在區(qū)間【min主经，max】中出現(xiàn)次數(shù)，最后從頭到尾把數(shù)組寫出來庭惜。復(fù)雜度是O（n）罩驻，比較穩(wěn)定，但是依賴額外內(nèi)存空間
計數(shù)排序需要全部都是整數(shù)蜈块！
這里鉴腻，我們?nèi)≌麛?shù)來試驗，所以只要取得最大值就行百揭。arr的值表示bucket的位置爽哎，如果bucket的某個位置是undefined，說明arr里面沒有這個位置的索引值
function count(arr) {
var max = Math.max(...arr)//需要知道最大值的器一，這里只能作弊了
var bucket = new Array(max+1),//一個被max+1個undefined填充的數(shù)組
sortedIndex = 0;//重寫arr的索引
for (var i = 0; i < arr.length; i++) {
if (!bucket[arr[i]]) {//第一次遇到bucket的某個索引值為arr值课锌，將undefined變成0
bucket[arr[i]] = 0;
}
bucket[arr[i]]++;//開始統(tǒng)計
}
for (var j = 0; j < max + 1; j++) {
while(bucket[j] > 0) {
arr[sortedIndex++] = j;//重寫arr
bucket[j]--;//再一次進入同樣的循環(huán)，直到?jīng)]有重復(fù)值（0的時候）
}
}
return arr;
}
6.基數(shù)排序
先比較個位數(shù)的大小祈秕，按順序分類渺贤，從頭到尾重新取出數(shù)字。再進行第二次比較请毛，比較十位數(shù)的大小志鞍，按順序分類，再從頭到尾取出........直到最高位方仿。要求全是整數(shù)固棚。
我們這里比較兩位數(shù)以內(nèi)的
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);//和計數(shù)排序一樣，這里只需要0-9的數(shù)組存放
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}
7.歸并排序
由名字可以知道仙蚜，這其實就是一種遞歸此洲。順序是比較前面兩個=>比較前面兩個的后面兩個=>比較前面四個=>比較前面四個的后面兩個=>比較前面6個的后面兩個=>比較前面8個........
始終都是O（nlogn）的復(fù)雜度，不受輸入數(shù)據(jù)影響委粉，但是依賴額外內(nèi)存
每一次2個數(shù)的小組比較呜师，兩個小組的數(shù)量一致而且排序方式也是升序，對比起來就是一一對比贾节。大的組比較也是一樣汁汗。數(shù)量不同只有數(shù)組長度非2的n次方的尾部的比較。
function mergeSort(arr) { //采用自上而下的遞歸方法
var len = arr.length;
if(len < 2) {
return arr;//遞歸到子數(shù)組長度為1為止
}
var middle = Math.floor(len / 2),//數(shù)組被分成左右兩個子數(shù)組
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {//兩個子數(shù)組從頭開始一一比較栗涂，歸并為一個排序好的數(shù)組
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());//取出第一個取比較
while (right.length)
result.push(right.shift());
return result;
}
原文來源于：lhyt的github
