一、前言
傳統的計算機算法和數據結構領域，都是基於java或者c/c++等。沒用javascript實現過或是沒仔細看過相關算法的原理，導致寫起來浪費很多時間。對於一個前端來說，尤其是筆試面試的時候，算法方面考的其實不難（十大排序算法或是和十大排序算法同等難度的）。
算法由來：9世紀波斯數學家提出的算法「al-Khowarizmi」，阿拉伯人對數學史的貢獻很大，讓人欽佩。
二、說明
1、排序的定義：對序列的對象根據某一個關鍵字進行排序。
比如：需要對數字進行排序，1,7,10,2,6,40,33,99，使得1<2<6<7<10<33<40<99，就是類似於站隊，矮的在前面，高的在後邊。
2、算法的評述短髮優劣術語的說明
穩定：a原本在b的前面，而a=b，排序後a仍然在b的前面；不穩定：a原本在前面，而a=b，排序後a可能出現在b的後邊；
內排序：所有排序操作都在內存中完成；外排序：由於數據很大，因此把數據放在磁碟中，排序通過磁碟和內存的數據傳輸才能進行。
時間複雜度：一個算法執行需要耗費的時間；空間複雜度：運行這一個算法需要內存的大小。可以參考：javascript系列--時間複雜度和空間複雜度
3、排序算法圖片總結
解釋：n表示數據規模，k表示桶的個數，in-place表示佔用常數內存，out-place表示佔用額外內存。
排序分類：
三、冒泡排序（Bubble Sort）
最常用的排序算法之一，穩定排序。
思路：重複的訪問每一個元素，一次比較兩個元素，如果順序不對就交換位置。
冒泡的由來：越大的元素會經過交換，浮動到元素的最後邊。
描述：（1）比較相鄰的元素，如果第一個比第二個大，就交換位置。（2）對每一對相鄰元素做同樣的工作，從開始的第一對到最後一對，這樣最後的元素就是最大的；（3）針對所有元素，重複上述步驟，除了最後一個元素。
// 冒泡算法functionbubbleSort(arr){var len = arr.length;for(var i = 0;i < len; i++){for(var j =0;j < len-1-i;j++){if(arr[j]>arr[j+1]){var temp = arr[j+1]; arr[j+1] = arr[j]; arr[j] = temp; } } }return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(bubbleSort(arr));分析：一共進行14趟，每一趟比較15-i次，因為那i次在上一趟中已經排好序了。
改進的冒泡1
思路：設置一個標誌性變量flag，用於記錄每一趟排序中最後一次進行交換的位置。由於flag的位置之後的元素均已經交換到位，多以下一趟排序只需要掃到flag位置。
// 改進冒泡算法，加入標誌位functionbubbleSort2(arr){var i = arr.length - 1;while(i > 0){var flag = 0;for(var j = 0;j < i;j++){if(arr[j]>arr[j+1]){ flag = j;console.log('交換前數組順序：',arr);var temp = arr[j+1];arr[j+1] = arr[j]; arr[j] = temp;console.log( '比較的元素：',arr[j], arr[j+1],'交換的位置:',flag,'交換後數組順序：',arr) } } i = flag; }return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(bubbleSort2(arr));
改進的冒泡2
思路：傳統的冒泡排序每一趟值呢周到一個最大值或者最小值，我們可以每一趟排序中進行正向和反向兩遍冒泡，一次可以得到兩個最終值（最大和最小），從而是排序趟數減少了一半。
// 改進冒泡算法3，一趟找出最大值和最小值functionbubbleSort3(arr){var low = 0;var high = arr.length - 1;var temp,j;while(low < high){for(j = low;j < high;++j){ //正向冒泡，找最大值if(arr[j] > arr[j+1]){ temp = arr[j+1];arr[j+1] = arr[j]; arr[j] = temp; } } --high; //修改high，前移一位for(j = high; j > low; --j){if (arr[j]<arr[j-1]) { temp = arr[j]; arr[j]=arr[j-1];arr[j-1]=temp; } } ++ low; }return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(bubbleSort3(arr));
總結：
最佳情況：O(n)（已經是正序的情況）
最壞情況：O(n*2)（已經是倒敘的情況）
平均情況：O(n*2)
四、選擇排序（selection sort）
最常用的排序算法之一，但是是不穩定排序。
無論是什麼數據進去，時間複雜度都是O(n*2)。數據規模越小越好，唯一的好處就是不佔用額外的空間。
思路：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。然後再從剩餘未排序的數組匯總繼續尋找最小（大）元素，依次類推。
描述：（1）初始狀態：無序區為R[1...n]，有序區為空；（2）第i趟排序（i = 1,2,3,...,n-1)開始的時候，當前有序區R[1,...,i-1]和無序區R[i,...,n]。從該趟排序從當前無序區中選出關鍵字最小的記錄R[k]，將R[k]與無序區的第一個記錄R[1]交換，使無序區R[1,...,i]減少1個，和有序區R[i+1,...,n]增加1個。
// 選擇排序functionselectionSort(arr){var length = arr.length;var minIndex,temp;for(var i = 0;i < length - 1;i++){ minIndex = i;for(var j = i + 1;j<length;j++){if(arr[j] < arr[minIndex]){ minIndex = j; } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; }return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(selectionSort(arr));
總結：
最佳情況：O(n*2)
最壞情況：O(n*2)
平均情況：O(n*2)
五、插入排序（insertion sort）
插入排序也比較常見，穩定排序。
插入排序的代碼實現雖然沒有冒泡排序和選擇排序那麼簡單粗暴，但它的原理應該是最容易理解的了，因為只要打過撲克牌的人都應該能夠秒懂。
思路：通過構建有序序列，對於未排序的元素在已排序的序列中從後向前掃描，並找到相應的位置並插入。插入排序的實現上，通常採用in-place排序（需要用到O(1)的額外空間排序），因此從後向前掃描的時候，需要反覆把已排序的元素逐步向後移動，為最新元素提供插入空間。
描述：（1）從第一個元素開始，該元素被認為是已經被排序；（2）取出下一個元素，在已經排序的元素序列中從後往前掃描；（3）如果已排序的元素大於新元素，將該元素移動到下一個位置；（4）重複步驟3，直到找到已排序的元素小於或者等於新元素的位置；（5）將新元素插入到該位置；（6）重複2-5的步驟。
// 插入排序 insertion sortfunctioninsertionSort(arr){var length = arr.length;for(var i = 1;i < length;i++){var current = arr[i];var j = i - 1;while(j>=0 && arr[j]>current){ arr[j+1] = arr[j]; j--; } arr[j+1] = current; }return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(insertionSort(arr));
改進的插入排序
思路：查找插入位置時使用二分查找的方式。
// 改進的插入排序 二分查找 insertion sortfunctioninsertionSort(arr){var length = arr.length;for(var i = 1;i < length;i++){var current = arr[i];var left = 0;var right = i - 1;while(left <= right){var middle = parseInt((left+right)/2);if(current < arr[middle]){ right = middle - 1; }else{ left = middle + 1; } }for(var j = i - 1;j >= left;j--){ arr[j+1] = arr[j]; } arr[left] = current; }return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(insertionSort(arr));
總結：
最佳情況：O(n)
最壞情況：O(n*2)
平均情況：O(n*2)
六、希爾排序（shellsort）
突破排序的時間複雜度O(n*2)，達到O(nlogn)，不穩定的排序。
是一種簡單的插入排序的改進版，與插入排序的區別是：希爾排序會優先比較距離較遠的元素。希爾排序也被稱為縮小增量排序。
思路：核心在於間隔序列的設定。既可以提前設定好間隔序列，也可以動態的定義間隔序列。
描述：將整個待排序的記錄序列分割成若干個子序列分貝進行直接插入排序。（1）選擇一個增量序列t1,t2,t3,...,tk，其中ti>tj，tk = 1；（2）按照增量序列個數k，對序列進行k趟排序；（2）每趟排序，根據對應的增量ti，將待排序分隔成若干長度為m的子序列，分別對各子表進行直接插入排序。增量因子為1的時候，整個序列作為一個表來處理，表長度即為整個序列的長度。
// 希爾排序 shell sortfunctionshellSort(arr){var length = arr.length,temp,gap = 1;while(gap < length/5){ gap = gap*5 + 1; }for(gap;gap>0;gap = Math.floor(gap/5)){for(var i = gap;i<length;i++){ temp = arr[i];var j = i - gap;while(j>=0 && arr[j]>temp){ arr[j+gap] = arr[j]; j = j-gap; } arr[j+gap] = temp; } }return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(shellSort(arr));希爾排序圖示（圖片來源網絡）：
總結：
最佳情況：O(nlog2n)
最壞情況：O(nlog2n)
平均情況：O(nlogn)
六、歸併排序（merge sort）
突破排序的時間複雜度O(n*2)，達到O(nlogn)，穩定的排序。
歸併排序跟選擇排序一樣，不受數據的影響，但表現比選擇排序好。始終是O(nlogn)的時間複雜度。代價是額外的內存空間。
思路：算法採用的是分治法的一個典型應用，是一種穩定的排序，將已經有序的子序列合併，得到完全有序的序列。先讓每一個子序列都有序，使子序列裡面有序，將兩個有序表合併，稱為二路歸併。
描述：（1）把長度為n的輸入序列分為兩個長度為n/2的子序列；（2）對這兩個子序列分別採用歸併排序；（3）將兩個排序好的子序列合併成一個最終的排序序列。
// 歸併排序 merge sort
functionmergeSort(arr){var length = arr.length;if(length<2){return arr; }var middle = Math.floor(length/2);var left = arr.slice(0, middle);var right = arr.slice(middle);return merge(mergeSort(left), mergeSort(right));}functionmerge(left, right){var result = [];while(left.length && right.length){if(left[0] <= right[0]){ 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;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(mergeSort(arr));
總結：
最佳情況：O(n)
最壞情況：O(nlogn)
平均情況：O(nlogn)
七、快速排序（quick sort）
突破排序的時間複雜度O(n*2)，達到O(nlogn)，空間複雜度為O(logn)，不穩定的排序。
顧名思義，快排，速度就是快，效率高，處理大數據的最快的排序算法之一。
思路：也是分治法的思想，通過一趟排序將待排序的元素分為獨立的兩個部分，其中一部分記錄的關鍵字均比另外一部分的關鍵字小，然後分別對這兩部分繼續進行排序，已達到整個序列有序。
描述：分治法吧一個串list分為兩個子串sub-list。（1）從串中挑一個元素，作為基準；（2）從新排序串，所有元素比基準值小的擺放在基準的前面，所有元素比基準值大的擺在基準的後邊，相同的數可以到任意一邊。這個分區退出後，基準就位於中間位置，這個稱為分區操作；（3）遞歸的把小於基準值的元素的子串和大於基準值的子串進行排序。
覺得還是不是很懂，那我們在看看具體實現：
具體實現：
（1）一般是取序列的第一個作為基準數；
（2）設置 i，j 兩個指針分別指向最左端和最右端；
（3）每次比較都從右端 j 指針開始項左移動，尋找比基準點小的數，然後停止移動；
（4）然後左側指針 i 向右移動尋找比基準數大的數，然後停止移動；
（5）此時交換 i 和 j 所指向的內容，這算一趟中一次交換完成，直到 i ， j 指針相遇位置k，這時候將基準數和k位置的數字交換，這算完成了一趟排序。
// 快排 quicksortfunctionquickSort(arr,left,right){if(left<right){var x = arr[left]; //基準數，一般取第一個值var i = left; //左邊的指針var j = right; //右邊的指針var temp; //臨時變量while(i != j){ //每一趟進行的多次比較和交換最終找到位置kwhile(arr[j]>=x && i<j){ //大於基準數，j指針向左移動，直到小於基準數 j--; }while(arr[i]<=x && i<j){ //小於基準數，j指針向左移動，直到大於基準數 i++; }if(i<j){ temp = arr[i];arr[i] = arr[j];arr[j] = temp; } } arr[left] = arr[i]; //交換基準數和k位置的數 arr[i] = x; quickSort(arr, left, i - 1); //遞歸 quickSort(arr, i + 1,right); //遞歸 }return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(quickSort(arr,0,arr.length-1));
還有一種方法實現
// 快排 quicksort 方法二functionquickSort2(arr){if(arr.length <= 1){return arr}var xIndex = Math.floor(arr.length/2);var x = arr.splice(xIndex, 1)[0];var left = [];var right = [];for(var i=0;i<arr.length;i++){if(arr[i] < x){ left.push(arr[i]); }else{ right.push(arr[i]); } }return quickSort2(left).concat([x], quickSort2(right));}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(quickSort2(arr,0,arr.length-1));這種方法更容易理解，缺點肯定是空間複雜度升高了。
總結：
這個是自己實現的，但是javascript中已經有了原生的sort原生。原生的實現還是比自己寫的快。
最佳情況：O(nlogn)
最壞情況：O(n*2)
平均情況：O(nlogn)
八、堆排序（heap sort）
一種利用堆概念來排序的選擇排序，是一種不穩定的排序。
思路：利用堆這種數據結構設計的排序算法。堆積是一個近似完全的二叉樹的結構，並且擁有堆積的性質：子節點的鍵值或者索引總小於（大於）它的父節點。
描述：（1）將初始待排序序列（r1,r2,r3,...,rn）構建成一個大頂堆，此堆為初始的無序區；（2）將堆頂元素r[1]與最後一個元素r[n]互換，此時得到新的無序區(r1,r2,r3,...,rn-1)和顯得有序區（rn）,且滿足r[1,2,3,...,n-1]<=r[n]；（3）由於交換後的新的堆頂r[1]可能違反堆的性質，因此需要對當前無序區(r1,r2,r3,...,rn-1)調整為新堆，然後再次將r[1]與無序區最後一個元素互換，得到新的無序區（r1,r2,r3,...,rn-2）和新的有序區（rn-1,rn），不斷重複這個過程，直到有序區的元素個數為n-1，這樣整個排序過程完成。
// 堆排序functionheapAdjust(arr, i, length){var left = 2*i+1;var right = 2*i+2;var largest = i;var temp;if(left<length && arr[largest]<arr[left]){ largest = left; }if(right<length && arr[largest] < arr[right]){ largest = right; }if(largest != i){ temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp; heapAdjust(arr, largest, length); }}functionheapSort(arr){// 建立大頂堆var heapSize = arr.length;var temp;for(var i=Math.floor(heapSize/2)-1;i>=0;i--){ heapAdjust(arr,i,heapSize); }// 堆排序for(var j = heapSize-1;j>=1;j--){ temp = arr[0]; arr[0] = arr[j]; arr[j] = temp; heapAdjust(arr,0,--heapSize); }return arr;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(heapSort(arr));
總結：
最佳情況：O(nlogn)
最壞情況：O(nlogn)
平均情況：O(nlogn)
九、計數排序（counting sort）
將輸入的數據值轉化為鍵存儲在額外開闢的數組空間，一種線性的時間複雜度，一種穩定的排序。
注意：計數排序要求輸入的數據必須是有確定範圍的整數。
思路：計數排序使用一個額外的數組C，其中第i個元素是待排序數組A中的值等於i的元素的個數，然後根據數組C來講A中的元素排到正確的位置。只能對整數排序。
描述：（1）找出待排序數組中最大和最小的元素；（2）統計數組中每一個值為i的元素出現的次數，存入到數組c的第i項；（3）對所有的計數累加（從c的第一個元素開始，每一項和前一項相加）；（4）反向填充到目標數組：將每一個元素 i 放在新數組的第C（i）項，每放一個元素就將c（i）減1。
// 計數排序 functioncountingSort(arr){var length = arr.length;var B =[];var C = [];var min = max = arr[0];for(var i=0;i<length;i++){ min = min <= arr[i]?min:arr[i]; max = max >= arr[i]?max:arr[i]; C[arr[i]] = C[arr[i]]?C[arr[i]] + 1 : 1; }for(var j = min;j < max;j++){ C[j+1] = (C[j+1] || 0) + (C[j] || 0); }for(var k=length-1;k>=0;k--){ B[C[arr[k]]-1] = arr[k]; C[arr[k]]--; }return B;}var arr = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];console.log(countingSort(arr));
總結：
最佳情況：O(n+k)
最壞情況：O(n+k)
平均情況：O(n+k)
十、桶排序（bucket sort）
桶排序其實是計數排序的升級。利用的是函數的映射關係，高效在於映射函數，一種穩定的排序。
思路：假設輸入數據服從均勻分布，將數據分到有限的數量的桶裡，每一個桶再分別排序（這時候可能會用到其他排序算法，也可以使用桶排序進行遞歸）
描述：（1）設置一個定量的數組作為空桶；（2）遍歷輸入數據，並且將數據一個一個方法哦對應的桶裡去；（3）對每個不是空的桶進行排序；（4）從不是空桶裡把排序好的數據拼接起來。
// 桶排序 functionbucketSort(array, num) {if (array.length <= 1) {return array; }var len = array.length, buckets = [], result = [], min = max = array[0], regex = '/^[1-9]+[0-9]*$/', space, n = 0; num = num || ((num > 1 && regex.test(num)) ? num : 10);console.time('桶排序耗時');for (var i = 1; i < len; i++) { min = min <= array[i] ? min : array[i]; max = max >= array[i] ? max : array[i]; } space = (max - min + 1) / num;for (var j = 0; j < len; j++) {var index = Math.floor((array[j] - min) / space);if (buckets[index]) { // 非空桶，插入排序var k = buckets[index].length - 1;while (k >= 0 && buckets[index][k] > array[j]) { buckets[index][k + 1] = buckets[index][k]; k--; } buckets[index][k + 1] = array[j]; } else { //空桶，初始化 buckets[index] = []; buckets[index].push(array[j]); } }while (n < num) { result = result.concat(buckets[n]); n++; }console.timeEnd('桶排序耗時');return result;}var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];console.log(bucketSort(arr,4));總結：
最佳情況：O(n+k)
最壞情況：O(n+k)
平均情況：O(n+k)
十一、基數排序（radix sort）
基數排序也是非比較的排序算法，對每一位進行排序，從低位開始排序。一種穩定排序算法。
思路：基數排序是按照低位先排序，然後收集，再按照高位排序，然後再收集；依次類推，直到最高位；有時候有些屬性是有優先級順序的，先按照低優先級排序，再按照高優先級排序。最後順序就是高優先級咋前，高優先級相同的低優先級高的在前。基數培訓基於分別排序，分別手機，所以是穩定的。
描述：（1）取得數組中最大數，並取得位數；（2）arr為原數組，從最低位開始取每個位組成radix數組；（3）對radix進行計數排序（利用計數排序適用於小範圍數的特點）。
// 基數排序 functionradixSort(arr, maxDigit) {var mod = 10;var dev = 1;var counter = [];console.time('基數排序耗時');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]); }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; } } } }console.timeEnd('基數排序耗時');return arr;}var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];console.log(radixSort(arr,2));
總結：
最佳情況：O(n*k)
最壞情況：O(n*k)
平均情況：O(n*k)
基數排序和計數排序和桶排序
都利用了桶的概念，但是對桶的使用上有明顯差異。
1、基數排序：根據鍵值的每位數來分配桶；
2、計數排序：每個桶只存儲單一鍵值；
3、桶排序：每個通存儲一定範圍的數值。
十二、總結
排序算法其實還是很有研究的必要，雖然很多不咋用，但是有時候掌握算法的思路對於你在遇到其他問題時候可以觸類旁通。作為一個算法的弱雞，有問題的地方希望各位看官指導一下。參考資源來源於網絡和自己覺得寫的不好的地方。