本文是lhyt本人原創(chuàng)，希望用通俗易懂的方法來理解一些細節(jié)和難點。轉(zhuǎn)載時請注明出處。文章最早出現(xiàn)于本人github
0.前言
相信大家面試的時候都要經(jīng)歷手寫什么什么排序這種事情吧，要不就是大概說一下思路。不許用各種語言封裝好的函數(shù)、api，僅僅用原生的方法把他寫出來。雖然看起來沒什么意思，但是這也是考察一個人的基礎(chǔ)有沒有扎實、編程思想好不好的一種方法。
重要的事情說三遍：
主要理解快速排序?。?！
主要理解快速排序?。。?/p>
主要理解快速排序?。?！
而且要滾瓜爛熟！
以下所有的排序都是升序
1.冒泡排序
先說最簡單的吧，冒泡，就是指數(shù)值大的，就是一個大氣泡，慢慢冒到后面（水面）去。對于要排序的數(shù)組，一個個去遍歷，大的數(shù)往后移。往后移怎么做到呢，就是遍歷的時候，兩個數(shù)中（第j和j+1個）要是誰比較大，誰在后面（交換位置）。氣泡都聚集在水面（大數(shù)都從后面聚集在一起，所以每次第二層遍歷都會到len-1-j截止）
時間復雜度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ù)因子很小，比復雜度穩(wěn)定等于O(n log n)的歸并排序要小很多。對絕大多數(shù)順序性較弱的隨機數(shù)列而言，快速排序總是占優(yōu)。
首先，取一個基準值（我們?nèi)〉谝粋€，也可以取中間、取最后都行），接著讓小于基準值的在左邊，大于的在右邊，分成左右兩堆。然后分別對左邊和右邊那堆采取同樣的操作，取基準值，讓基準值左邊都是小于他的，右邊都是大于他的。一直重復操作，直到全部升序。
2.1另外開辟兩個空數(shù)組
這種方法容易理解，但是依賴另外開辟出來的數(shù)組。我們?nèi)〉谝粋€作為基準，從第二（特別注意，第二個開始！不然棧溢出）個開始遍歷，小于基準的數(shù)放在左數(shù)組（left），大于基準的放在右數(shù)組，接著對左數(shù)組和右邊數(shù)組重復操作，再對左邊數(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ù)組重復的遞歸操作
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)復雜度，但是依賴額外內(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)下一個大于（或等于）自己，上一個小于（或等于）自己，那就把他放在中間。復雜度穩(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ù)組寫出來。復雜度是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)]有重復值（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）的復雜度，不受輸入數(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
