六種前端排序算法代碼演示

排序算法是前端算法中一個十分經(jīng)典的算法，因此它也是前端面試中常見的考察重點。如今前端行業(yè)火爆，就業(yè)市場對前端人才的要求也越來越高，排序算法是每個前端從業(yè)者都必須掌握的基礎(chǔ)知識。眾所周知，排序算法有六種，分別是冒泡排序、選擇排序、快速排序、歸并排序、基數(shù)排序。下面我為大家逐一用代碼演示這六大排序算法，感興趣的朋友一起來看看吧！

1、冒泡排序

（1）概念

冒泡排序，顧名思義，就像魚吐泡泡，泡泡越往上越大。第一次循環(huán)，開始比較當前元素與下一個元素的大小，如果比下一個元素小或者相等，則不需要交換兩個元素的值；若比下一個元素大的話，則交換兩個元素的值。然后，遍歷整個數(shù)組，第一次遍歷完之后，相同操作遍歷第二遍。

（2）性能

時間復雜度：平均時間復雜度是O(n^2)；空間復雜度：由于輔助空間為常數(shù)，所以空間復雜度是O(1)。

（3）代碼演示

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);

2、選擇排序

（1）概念

選擇排序，即每次都選擇最小的，然后換位置。第一遍，從數(shù)組中選出最小的，與第一個元素進行交換；第二遍，從第二個元素開始，找出最小的，與第二個元素進行交換；依次循環(huán)，完成排序。

（2）性能

時間復雜度：平均時間復雜度是O(n^2)，這是一個不穩(wěn)定的算法，因為每次交換之后，它都改變了后續(xù)數(shù)組的順序?？臻g復雜度：輔助空間是常數(shù)，空間復雜度為O(1)。

（3）代碼演示

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 ]

3、插入排序

（1）概念

插入排序就是將元素插入到已排序好的數(shù)組中。首先，循環(huán)原數(shù)組，然后，將當前位置的元素，插入到之前已排序好的數(shù)組中，依次操作。

（2）性能

時間復雜度：平均算法復雜度為O(n^2)；空間復雜度：輔助空間為常數(shù)，空間復雜度是O(1)。

（3）代碼演示

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 ]

4、快速排序

（1）概念

快速排序，從它的名字就應(yīng)該知道它很快，時間復雜度很低，性能很好。它將排序算法的時間復雜度降低到O。

（2）性能

時間復雜度：平均時間復雜度O(nlogn)，只有在特殊情況下會是O(n^2)，不過這種情況非常少；空間復雜度：輔助空間是logn，所以空間復雜度為O。

（3）代碼演示

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));

5、歸并排序

（1）概念

歸并排序，即將數(shù)組分成不同部分，然后注意排序之后，進行合并。首先，將相鄰的兩個數(shù)進行排序，形成n/2對，然后在每兩對進行合并，不斷重復，直至排序完。

（2）性能

時間復雜度：平均時間復雜度是O；空間復雜度：輔助空間為n，空間復雜度為O(n)。

（3）代碼演示

//迭代版本

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));

6、基數(shù)排序

（1）概念

基數(shù)排序，就是將數(shù)的每一位進行一次排序，最終返回一個正常順序的數(shù)組。首先，比較個位的數(shù)字大小，將數(shù)組的順序變成按個位依次遞增的，之后再比較十位，再比較百位的，直至最后一位。

（2）性能

時間復雜度：平均時間復雜度O(k*n)，最壞的情況是O(n^2)。

（3）代碼演示

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));

以上就是六種前端排序算法的代碼演示，大家都看明白了嗎？排序算法是前端學習中的基礎(chǔ)部分，只要大家明白它的原理，再多動手敲敲代碼，相信掌握前端排序算法并不困難。如果大家喜歡本篇文章，歡迎關(guān)注教育培訓網(wǎng)資訊欄目，本欄目將每天為大家更新更多的前端資訊。