前言
排序算法可能是你學編程第一個學習的算法屈糊，還記得冒泡嗎？
當然琼了，排序和查找兩類算法是面試的熱門選項逻锐。如果你是一個會寫快排的程序猿，面試官在比較你和一個連快排都不會寫的人的時候雕薪，會優(yōu)先選擇你的昧诱。那么，前端需要會排序嗎所袁？答案是毋庸置疑的盏档，必須會。現(xiàn)在的前端對計算機基礎要求越來越高了燥爷，如果連排序這些算法都不會蜈亩，那么發(fā)展前景就有限了。本篇將會總結一下前翎，在前端的一些排序算法稚配。
正文
Array.sort
相信每個使用js的都用過這個函數(shù)，但是港华，這個函數(shù)本身有些優(yōu)點和缺點道川。我們可以通過一個例子來看一下它的功能：
const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];
console.log(arr.sort()); ? // [ 1, 10, 100, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88 ]
console.log(arr.sort((item1, item2) => item1 - item2)); // [ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]
相信你也已經看出來它在處理上的一些差異了吧。首先，js中的sort會將排序的元素類型轉化成字符串進行排序愤惰。不過它是一個高階函數(shù)苇经，可以接受一個函數(shù)作為參數(shù)。而我們可以通過傳入內部的函數(shù)宦言，來調整數(shù)組的升序或者降序扇单。
sort函數(shù)的性能：相信對于排序算法性能來說，時間復雜度是至關重要的一個參考因素奠旺。那么蜘澜，sort函數(shù)的算法性能如何呢？通過v8引擎的源碼可以看出响疚，Array.sort是通過javascript來實現(xiàn)的鄙信，而使用的算法是快速排序，但是從源碼的角度來看忿晕，在實現(xiàn)上明顯比我們所使用的快速排序復雜多了装诡，主要是做了性能上的優(yōu)化。所以践盼，我們可以放心的使用sort()進行排序鸦采。
冒泡排序
冒泡排序，它的名字由來于一副圖——魚吐泡泡咕幻，泡泡越往上越大渔伯。
思路：第一次循環(huán)，開始比較當前元素與下一個元素的大小肄程，如果比下一個元素小或者相等锣吼，則不需要交換兩個元素的值；若比下一個元素大的話蓝厌，則交換兩個元素的值玄叠。然后，遍歷整個數(shù)組褂始，第一次遍歷完之后诸典，相同操作遍歷第二遍描函。
圖例：
代碼實現(xiàn)：
const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];
function bubbleSort(arr){
?for(let i = 0; i < arr.length - 1; i++){
? ?for(let j = 0; j < arr.length - i - 1; j++){
? ? ?if(arr[j] > arr[j + 1]){
? ? ? ?swap(arr, j, j+1);
? ? ?}
? ?}
?}
?return arr;
}
function swap(arr, i, j){
?let temp = arr[i];
?arr[i] = arr[j];
?arr[j] = temp;
}
console.log(arr);
性能：
時間復雜度：平均時間復雜度是O(n^2)
空間復雜度：由于輔助空間為常數(shù)崎苗，所以空間復雜度是O(1);
改進：
我們可以對冒泡排序進行改進，使得它的時間復雜度在大多數(shù)順序的情況下舀寓，減小到O(n);
1.加一個標志位胆数，如果沒有進行交換，將標志位置為false互墓，表示排序完成必尼。
const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];
function swap(arr, i, j){
?const temp = arr[i];
?arr[i] = arr[j];
?arr[j] = temp;
}
for(let i = 0; i < arr.length - 1; i++){
?let flag = false;
?for(let j = 0; j < arr.length - 1 - i; j++){
? ?if(arr[j] > arr[j+1]){
? ? ?swap(arr, j, j+1);
? ? ?flag = true;
? ?}
?}
?if(!flag){
? ?break;
?}
}
console.log(arr); ?//[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]
2.記錄最后一次交換的位置， 因為最后一次交換的數(shù)，是在這一次排序當中最大的數(shù)判莉，之后的數(shù)都比它大豆挽。在最佳狀態(tài)時，時間復雜度也會縮小到O(n);
const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50 ,112];
function swap(arr, i, j){
?let temp = arr[i];
?arr[i] = arr[j];
?arr[j] = temp
}
function improveBubble(arr, len){
?for(let i = len - 1; i >= 0; i--){
? ?let pos = 0;
? ?for(let j = 0; j < i; j++){
? ? ?if(arr[j] > arr[j+1]){
? ? ? ?swap(arr, j, j+1);
? ? ? ?pos = j + 1;
? ? ?}
? ?}
? ?len = pos + 1;
?}
?return arr;
}
console.log(improveBubble(arr, arr.length)); ?// [ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100, 112 ]
選擇排序
選擇排序券盅，即每次都選擇最小的帮哈，然后換位置
思路：
第一遍，從數(shù)組中選出最小的锰镀，與第一個元素進行交換娘侍；第二遍，從第二個元素開始泳炉，找出最小的憾筏，與第二個元素進行交換；依次循環(huán)花鹅，完成排序
圖例：
代碼實現(xiàn)：
const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];
function swap(arr, i, j){
?var temp = arr[i];
?arr[i] = arr[j];
?arr[j] = temp;
}
function selectionSort(arr){
?for(let i = 0; i < arr.length - 1; i++){
? ?let index = i;
? ?for(let j = i+1; j < arr.length; j++){
? ? ?if(arr[index] > arr[j]){
? ? ? ?index = j;
? ? ?}
? ?}
? ?swap(arr, i, index);
?}
?return arr;
}
console.log(selectionSort(arr)); // [ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]
性能：
時間復雜度：平均時間復雜度是O(n^2)氧腰，這是一個不穩(wěn)定的算法，因為每次交換之后刨肃，它都改變了后續(xù)數(shù)組的順序容贝。
空間復雜度：輔助空間是常數(shù)，空間復雜度為O(1);
插入排序
插入排序之景，即將元素插入到已排序好的數(shù)組中
圖例：
代碼實現(xiàn)：
const arr = [1, 20, 10, 30, 22, 11, 55, 24, 0, 31, 88, 12, 100, 50 ,112];
function insertSort(arr){
?for(let i = 0; i < arr.length; i++){
? ?let temp = arr[i];
? ?for(let j = 0; j < i; j++){
? ? ?if(temp < arr[j] && j === 0){
? ? ? ?arr.splice(i, 1);
? ? ? ?arr.unshift(temp);
? ? ? ?break;
? ? ?}else if(temp > arr[j] && temp < arr[j+1] && j < i - 1){
? ? ? ?arr.splice(i, 1);
? ? ? ?arr.splice(j+1, 0, temp);
? ? ? ?break;
? ? ?}
? ?}
?}
?return arr;
}
console.log(insertSort(arr)); ?// [ 0, 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100, 112 ]
性能：
時間復雜度：平均算法復雜度為O(n^2)
空間復雜度：輔助空間為常數(shù)斤富，空間復雜度是O(1)
我們仨之間
其實，三個算法都是難兄難弟锻狗，因為算法的時間復雜度都是在O(n^2)满力。在最壞情況下，它們都需要對整個數(shù)組進行重新調整轻纪。只是選擇排序比較不穩(wěn)定油额。
快速排序
快速排序，從它的名字就應該知道它很快刻帚，時間復雜度很低潦嘶，性能很好。它將排序算法的時間復雜度降低到O(nlogn)
思路：
首先崇众，我們需要找到一個基數(shù)掂僵，然后將比基數(shù)小的值放在基數(shù)的左邊，將比基數(shù)大的值放在基數(shù)的右邊顷歌，之后進行遞歸那兩組已經歸類好的數(shù)組锰蓬。
圖例：
原圖片太大，放一張小圖眯漩，并且附上原圖片地址芹扭，有興趣的可以看一下：
代碼實現(xiàn)：
const arr = [30, 32, 6, 24, 37, 32, 45, 21, 38, 23, 47];
function quickSort(arr){
?if(arr.length <= 1){
? ?return arr;
?}
?let temp = arr[0];
?const left = [];
?const right = [];
?for(var i = 1; i < arr.length; i++){
? ?if(arr[i] > temp){
? ? ?right.push(arr[i]);
? ?}else{
? ? ?left.push(arr[i]);
? ?}
?}
?return quickSort(left).concat([temp], quickSort(right));
}
console.log(quickSort(arr));
性能：
時間復雜度：平均時間復雜度O(nlogn)麻顶，只有在特殊情況下會是O(n^2)，不過這種情況非常少
空間復雜度：輔助空間是logn舱卡，所以空間復雜度為O(logn)
歸并排序
歸并排序辅肾，即將數(shù)組分成不同部分，然后注意排序之后轮锥，進行合并
思路：
首先宛瞄，將相鄰的兩個數(shù)進行排序，形成n/2對交胚，然后在每兩對進行合并份汗，不斷重復，直至排序完蝴簇。
圖例：
代碼實現(xiàn)：
//迭代版本
const arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]
function mergeSort(arr){
?const len = arr.length;
?for(let seg = 1; seg < len; seg += seg){
? ?let arrB = [];
? ?for(let start = 0; start < len; start += 2*seg){
? ? ?let row = start, mid = Math.min(start+seg, len), heig = Math.min(start + 2*seg, len);
? ? ?let start1 = start, end1 = mid;
? ? ?let start2 = mid, end2 = heig;
? ? ?while(start1 < end1 && start2 < end2){
? ? ? ?arr[start1] < arr[start2] ? arrB.push(arr[start1++]) : arrB.push(arr[start2++]);
? ? ?}
? ? ?while(start1 < end1){
? ? ? ?arrB.push(arr[start1++]);
? ? ?}
? ? ?while(start2 < end2){
? ? ? ?arrB.push(arr[start2++]);
? ? ?}
? ?}
? ?arr = arrB;
?}
?return arr;
}
console.log(mergeSort(arr));
//遞歸版
const arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
function mergeSort(arr, seg = 1){
?const len = arr.length;
?if(seg > len){
? ?return arr;
?}
?const arrB = [];
?for(var start = 0; start < len; start += 2*seg){
? ?let low = start, mid = Math.min(start+seg, len), heig = Math.min(start+2*seg, len);
? ?let start1 = low, end1 = mid;
? ?let start2 = mid, end2 = heig;
? ?while(start1 < end1 && start2 < end2){
? ? ?arr[start1] < arr[start2] ? arrB.push(arr[start1++]) : arrB.push(arr[start2++]);
? ?}
? ?while(start1 < end1){
? ? ?arrB.push(arr[start1++]);
? ?}
? ?while(start2 < end2){
? ? ?arrB.push(arr[start2++]);
? ?}
?}
?return mergeSort(arrB, seg * 2);
}
console.log(mergeSort(arr));
性能：
時間復雜度：平均時間復雜度是O(nlogn)
空間復雜度：輔助空間為n杯活，空間復雜度為O(n)
基數(shù)排序
基數(shù)排序，就是將數(shù)的每一位進行一次排序熬词，最終返回一個正常順序的數(shù)組旁钧。
思路：
首先，比較個位的數(shù)字大小互拾，將數(shù)組的順序變成按個位依次遞增的歪今，之后再比較十位，再比較百位的颜矿，直至最后一位寄猩。
圖例：
代碼實現(xiàn)：
const arr = [3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127, 10000];
function radixSort(arr){
?let maxNum = Math.max(...arr);
?let dis = 0;
?const len = arr.length;
?const count = new Array(10);
?const tmp = new Array(len);
?while(maxNum >=1){
? ?maxNum /= 10;
? ?dis++;
?}
?for(let i = 1, radix = 1; i <= dis; i++){
? ?for(let j = 0; j < 10; j++){
? ? ?count[j] = 0;
? ?}
? ?for(let j = 0; j < len; j++){
? ? ?let k = parseInt(arr[j] / radix) % 10;
? ? ?count[k]++;
? ?}
? ?for(let j = 1; j < 10; j++){
? ? ?count[j] += count[j - 1];
? ?}
? ?for(let j = len - 1; j >= 0 ; j--){
? ? ?let k = parseInt(arr[j] / radix) % 10;
? ? ?tmp[count[k] - 1] = arr[j];
? ? ?count[k]--;
? ?}
? ?for(let j = 0; j < len; j++){
? ? ?arr[j] = tmp[j];
? ?}
? ?radix *= 10;
?}
?return arr;
}
console.log(radixSort(arr));
性能：
時間復雜度：平均時間復雜度O(k*n)，最壞的情況是O(n^2)
總結
我們一共實現(xiàn)了6種排序算法骑疆，對于前端開發(fā)來說田篇，熟悉前面4種是必須的。特別是快排箍铭，基本面試必考題泊柬。本篇的內容總結分為六部分：
冒泡排序
選擇排序
插入排序
快速排序
歸并排序
基數(shù)排序
排序算法，是算法的基礎部分诈火，需要明白它的原理兽赁，總結下來排序可以分為比較排序和統(tǒng)計排序兩種方式，本篇前5種均為比較排序冷守，基數(shù)排序屬于統(tǒng)計排序的一種刀崖。希望看完的你，能夠去動手敲敲代碼教沾，理解一下
引文地址：https://segmentfault.com/a/1190000011294349
