前端排序算法總結(jié)

happen 發(fā)布于2019-08-21 16:40 / 2971人閱讀

摘要：前言排序算法可能是你學(xué)編程第一個(gè)學(xué)習(xí)的算法，還記得冒泡嗎當(dāng)然，排序和查找兩類算法是面試的熱門選項(xiàng)。本篇將會(huì)總結(jié)一下，在前端的一些排序算法。函數(shù)的性能相信對(duì)于排序算法性能來說，時(shí)間復(fù)雜度是至關(guān)重要的一個(gè)參考因素。

前言

排序算法可能是你學(xué)編程第一個(gè)學(xué)習(xí)的算法，還記得冒泡嗎？

當(dāng)然，排序和查找兩類算法是面試的熱門選項(xiàng)。如果你是一個(gè)會(huì)寫快排的程序猿，面試官在比較你和一個(gè)連快排都不會(huì)寫的人的時(shí)候，會(huì)優(yōu)先選擇你的。那么，前端需要會(huì)排序嗎？答案是毋庸置疑的，必須會(huì)?，F(xiàn)在的前端對(duì)計(jì)算機(jī)基礎(chǔ)要求越來越高了，如果連排序這些算法都不會(huì)，那么發(fā)展前景就有限了。本篇將會(huì)總結(jié)一下，在前端的一些排序算法。如果你喜歡我的文章，歡迎評(píng)論，歡迎Star~。歡迎關(guān)注我的github博客

正文

首先，我們可以先來看一下js自身的排序算法sort()

Array.sort

相信每個(gè)使用js的都用過這個(gè)函數(shù)，但是，這個(gè)函數(shù)本身有些優(yōu)點(diǎn)和缺點(diǎn)。我們可以通過一個(gè)例子來看一下它的功能：

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 ]

相信你也已經(jīng)看出來它在處理上的一些差異了吧。首先，js中的sort會(huì)將排序的元素類型轉(zhuǎn)化成字符串進(jìn)行排序。不過它是一個(gè)高階函數(shù)，可以接受一個(gè)函數(shù)作為參數(shù)。而我們可以通過傳入內(nèi)部的函數(shù)，來調(diào)整數(shù)組的升序或者降序。

sort函數(shù)的性能：相信對(duì)于排序算法性能來說，時(shí)間復(fù)雜度是至關(guān)重要的一個(gè)參考因素。那么，sort函數(shù)的算法性能如何呢？通過v8引擎的源碼可以看出，Array.sort是通過javascript來實(shí)現(xiàn)的，而使用的算法是快速排序，但是從源碼的角度來看，在實(shí)現(xiàn)上明顯比我們所使用的快速排序復(fù)雜多了，主要是做了性能上的優(yōu)化。所以，我們可以放心的使用sort()進(jìn)行排序。

冒泡排序

冒泡排序，它的名字由來于一副圖——魚吐泡泡，泡泡越往上越大。

回憶起這個(gè)算法，還是最初大一的c++課上面。還是自己上臺(tái)，在黑板上實(shí)現(xiàn)的呢！

思路：第一次循環(huán)，開始比較當(dāng)前元素與下一個(gè)元素的大小，如果比下一個(gè)元素小或者相等，則不需要交換兩個(gè)元素的值；若比下一個(gè)元素大的話，則交換兩個(gè)元素的值。然后，遍歷整個(gè)數(shù)組，第一次遍歷完之后，相同操作遍歷第二遍。

圖例：

代碼實(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);

代碼地址

性能：

時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度是O(n^2)

空間復(fù)雜度：由于輔助空間為常數(shù)，所以空間復(fù)雜度是O(1);

改進(jìn)：

我們可以對(duì)冒泡排序進(jìn)行改進(jìn)，使得它的時(shí)間復(fù)雜度在大多數(shù)順序的情況下，減小到O(n);

加一個(gè)標(biāo)志位，如果沒有進(jìn)行交換，將標(biāo)志位置為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 ]

記錄最后一次交換的位置，因?yàn)樽詈笠淮谓粨Q的數(shù)，是在這一次排序當(dāng)中最大的數(shù)，之后的數(shù)都比它大。在最佳狀態(tài)時(shí)，時(shí)間復(fù)雜度也會(huì)縮小到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ù)組中選出最小的，與第一個(gè)元素進(jìn)行交換；第二遍，從第二個(gè)元素開始，找出最小的，與第二個(gè)元素進(jìn)行交換；依次循環(huán)，完成排序

圖例：

代碼實(shí)現(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 ]

代碼地址

性能：

時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度是O(n^2)，這是一個(gè)不穩(wěn)定的算法，因?yàn)槊看谓粨Q之后，它都改變了后續(xù)數(shù)組的順序。

空間復(fù)雜度：輔助空間是常數(shù)，空間復(fù)雜度為O(1);

插入排序

插入排序，即將元素插入到已排序好的數(shù)組中

思路：

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

圖例：

代碼實(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 ]

代碼地址

性能：

時(shí)間復(fù)雜度：平均算法復(fù)雜度為O(n^2)

空間復(fù)雜度：輔助空間為常數(shù)，空間復(fù)雜度是O(1)

我們仨之間

其實(shí)，三個(gè)算法都是難兄難弟，因?yàn)樗惴ǖ臅r(shí)間復(fù)雜度都是在O(n^2)。在最壞情況下，它們都需要對(duì)整個(gè)數(shù)組進(jìn)行重新調(diào)整。只是選擇排序比較不穩(wěn)定。

快速排序

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

思路：

首先，我們需要找到一個(gè)基數(shù)，然后將比基數(shù)小的值放在基數(shù)的左邊，將比基數(shù)大的值放在基數(shù)的右邊，之后進(jìn)行遞歸那兩組已經(jīng)歸類好的數(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));

代碼地址

性能：

時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度O(nlogn)，只有在特殊情況下會(huì)是O(n^2)，不過這種情況非常少

空間復(fù)雜度：輔助空間是logn，所以空間復(fù)雜度為O(logn)

歸并排序

歸并排序，即將數(shù)組分成不同部分，然后注意排序之后，進(jìn)行合并

思路：

首先，將相鄰的兩個(gè)數(shù)進(jìn)行排序，形成n/2對(duì)，然后在每兩對(duì)進(jìn)行合并，不斷重復(fù)，直至排序完。

圖例：

代碼實(shí)現(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));

代碼地址

性能：

時(shí)間復(fù)雜度：平均時(shí)間復(fù)雜度是O(nlogn)

空間復(fù)雜度：輔助空間為n，空間復(fù)雜度為O(n)

基數(shù)排序

基數(shù)排序，就是將數(shù)的每一位進(jìn)行一次排序，最終返回一個(gè)正常順序的數(shù)組。

思路：

首先，比較個(gè)位的數(shù)字大小，將數(shù)組的順序變成按個(gè)位依次遞增的，之后再比較十位，再比較百位的，直至最后一位。

圖例：

代碼實(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));

代碼地址

性能：

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

總結(jié)

我們一共實(shí)現(xiàn)了6種排序算法，對(duì)于前端開發(fā)來說，熟悉前面4種是必須的。特別是快排，基本面試必考題。本篇的內(nèi)容總結(jié)分為六部分：

冒泡排序

選擇排序

插入排序

快速排序

歸并排序

基數(shù)排序

排序算法，是算法的基礎(chǔ)部分，需要明白它的原理，總結(jié)下來排序可以分為比較排序和統(tǒng)計(jì)排序兩種方式，本篇前5種均為比較排序，基數(shù)排序?qū)儆诮y(tǒng)計(jì)排序的一種。希望看完的你，能夠去動(dòng)手敲敲代碼，理解一下

如果你對(duì)我寫的有疑問，可以評(píng)論，如我寫的有錯(cuò)誤，歡迎指正。你喜歡我的博客，請(qǐng)給我關(guān)注Star~呦。大家一起總結(jié)一起進(jìn)步。歡迎關(guān)注我的github博客

GPU云服務(wù)器云服務(wù)器排序算法總結(jié) 最大流算法總結(jié) 最短路徑算法總結(jié) 最高優(yōu)先數(shù)優(yōu)先調(diào)度算法實(shí)驗(yàn)總結(jié)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/88580.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

happen

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

電機(jī)與拖動(dòng)，直流發(fā)電機(jī)實(shí)驗(yàn)，江南大學(xué)物聯(lián)網(wǎng)自動(dòng)化

閱讀 1689·2021-11-15 11:37
Contabo：德國/美國/新加坡大硬盤存儲(chǔ)vps;加2美元可以升級(jí)100G NVMe

閱讀 3422·2021-09-28 09:44
racknerd，美國勞工節(jié)，洛杉磯/猶他州獨(dú)立服務(wù)器促銷，默認(rèn)5個(gè)IP，可選Windows, Li

閱讀 1662·2021-09-07 10:15
Contabo：西雅圖VPS，4核8G內(nèi)存/200G SSD，不限流量，免費(fèi)快照，€4.99/月起

閱讀 2799·2021-09-03 10:39
CSS揭秘之《偽隨機(jī)背景》

閱讀 2697·2019-08-29 13:20
小demo原生js同步翻譯，可以玩玩兒

閱讀 1304·2019-08-29 12:51
讓開發(fā)事半功倍-js數(shù)組處理方法

閱讀 2214·2019-08-26 13:44
javascript系列--this指向和apply，call，bind三者的區(qū)別

閱讀 2131·2019-08-23 18:02

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

前端排序算法總結(jié)

相關(guān)文章