国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

前端 排序算法總結

happen / 2964人閱讀

摘要:前言排序算法可能是你學編程第一個學習的算法,還記得冒泡嗎當然,排序和查找兩類算法是面試的熱門選項。本篇將會總結一下,在前端的一些排序算法。函數的性能相信對于排序算法性能來說,時間復雜度是至關重要的一個參考因素。

前言

排序算法可能是你學編程第一個學習的算法,還記得冒泡嗎?

當然,排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿,面試官在比較你和一個連快排都不會寫的人的時候,會優先選擇你的。那么,前端需要會排序嗎?答案是毋庸置疑的,必須會。現在的前端對計算機基礎要求越來越高了,如果連排序這些算法都不會,那么發展前景就有限了。本篇將會總結一下,在前端的一些排序算法。如果你喜歡我的文章,歡迎評論,歡迎Star~。歡迎關注我的github博客

正文

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

Array.sort

相信每個使用js的都用過這個函數,但是,這個函數本身有些優點和缺點。我們可以通過一個例子來看一下它的功能:

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會將排序的元素類型轉化成字符串進行排序。不過它是一個高階函數,可以接受一個函數作為參數。而我們可以通過傳入內部的函數,來調整數組的升序或者降序。

sort函數的性能:相信對于排序算法性能來說,時間復雜度是至關重要的一個參考因素。那么,sort函數的算法性能如何呢?通過v8引擎的源碼可以看出,Array.sort是通過javascript來實現的,而使用的算法是快速排序,但是從源碼的角度來看,在實現上明顯比我們所使用的快速排序復雜多了,主要是做了性能上的優化。所以,我們可以放心的使用sort()進行排序。

冒泡排序

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

回憶起這個算法,還是最初大一的c++課上面。還是自己上臺,在黑板上實現的呢!

思路:第一次循環,開始比較當前元素與下一個元素的大小,如果比下一個元素小或者相等,則不需要交換兩個元素的值;若比下一個元素大的話,則交換兩個元素的值。然后,遍歷整個數組,第一次遍歷完之后,相同操作遍歷第二遍。

圖例:

代碼實現:

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)

空間復雜度:由于輔助空間為常數,所以空間復雜度是O(1);

改進:

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

加一個標志位,如果沒有進行交換,將標志位置為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 ]

記錄最后一次交換的位置, 因為最后一次交換的數,是在這一次排序當中最大的數,之后的數都比它大。在最佳狀態時,時間復雜度也會縮小到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 ]
選擇排序

選擇排序,即每次都選擇最小的,然后換位置

思路:

第一遍,從數組中選出最小的,與第一個元素進行交換;第二遍,從第二個元素開始,找出最小的,與第二個元素進行交換;依次循環,完成排序

圖例:

代碼實現:

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),這是一個不穩定的算法,因為每次交換之后,它都改變了后續數組的順序。

空間復雜度:輔助空間是常數,空間復雜度為O(1);

插入排序

插入排序,即將元素插入到已排序好的數組中

思路:

首先,循環原數組,然后,將當前位置的元素,插入到之前已排序好的數組中,依次操作。

圖例:

代碼實現:

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)

空間復雜度:輔助空間為常數,空間復雜度是O(1)

我們仨之間

其實,三個算法都是難兄難弟,因為算法的時間復雜度都是在O(n^2)。在最壞情況下,它們都需要對整個數組進行重新調整。只是選擇排序比較不穩定。

快速排序

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

思路:

首先,我們需要找到一個基數,然后將比基數小的值放在基數的左邊,將比基數大的值放在基數的右邊,之后進行遞歸那兩組已經歸類好的數組。

圖例:

原圖片太大,放一張小圖,并且附上原圖片地址,有興趣的可以看一下:

原圖片地址

代碼實現:

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)

歸并排序

歸并排序,即將數組分成不同部分,然后注意排序之后,進行合并

思路:

首先,將相鄰的兩個數進行排序,形成n/2對,然后在每兩對進行合并,不斷重復,直至排序完。

圖例:

代碼實現:

//迭代版本
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)

基數排序

基數排序,就是將數的每一位進行一次排序,最終返回一個正常順序的數組。

思路:

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

圖例:

代碼實現:

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)

總結

我們一共實現了6種排序算法,對于前端開發來說,熟悉前面4種是必須的。特別是快排,基本面試必考題。本篇的內容總結分為六部分:

冒泡排序

選擇排序

插入排序

快速排序

歸并排序

基數排序

排序算法,是算法的基礎部分,需要明白它的原理,總結下來排序可以分為比較排序和統計排序兩種方式,本篇前5種均為比較排序,基數排序屬于統計排序的一種。希望看完的你,能夠去動手敲敲代碼,理解一下

如果你對我寫的有疑問,可以評論,如我寫的有錯誤,歡迎指正。你喜歡我的博客,請給我關注Star~呦。大家一起總結一起進步。歡迎關注我的github博客

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/88580.html

相關文章

  • 前端排序算法總結前端面試題2.0;JavaScript異步編程

    摘要:與異步編程按照維基百科上的解釋獨立于主控制流之外發生的事件就叫做異步。因為的存在,至少在被標準化的那一刻起,就支持異步編程了。然而異步編程真正發展壯大,的流行功不可沒。在握手過程中,端點交換認證和密鑰以建立或恢復安全會話。 1、前端 排序算法總結 排序算法可能是你學編程第一個學習的算法,還記得冒泡嗎? 當然,排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿,面試官在比較...

    aaron 評論0 收藏0
  • 前端排序算法總結前端面試題2.0;JavaScript異步編程

    摘要:與異步編程按照維基百科上的解釋獨立于主控制流之外發生的事件就叫做異步。因為的存在,至少在被標準化的那一刻起,就支持異步編程了。然而異步編程真正發展壯大,的流行功不可沒。在握手過程中,端點交換認證和密鑰以建立或恢復安全會話。 1、前端 排序算法總結 排序算法可能是你學編程第一個學習的算法,還記得冒泡嗎? 當然,排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿,面試官在比較...

    ARGUS 評論0 收藏0
  • 前端排序算法總結前端面試題2.0;JavaScript異步編程

    摘要:與異步編程按照維基百科上的解釋獨立于主控制流之外發生的事件就叫做異步。因為的存在,至少在被標準化的那一刻起,就支持異步編程了。然而異步編程真正發展壯大,的流行功不可沒。在握手過程中,端點交換認證和密鑰以建立或恢復安全會話。 1、前端 排序算法總結 排序算法可能是你學編程第一個學習的算法,還記得冒泡嗎? 當然,排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿,面試官在比較...

    April 評論0 收藏0
  • 前端中經常出現的算法總結

    摘要:在一段時間的學習之后,我總結羅列了前端中常見見的幾個算法一排序算法排序算法是比較開發的算法之一,方法種類較多,在此列舉兩種簡單的排序算法冒泡排序和快速排序。 雖說我們很多時候前端很少有機會接觸到算法,但對算法的理解和掌握是一個優秀工程師的評價標準之一,而且當我們面對較為復雜的問題,這些基礎知識的積累可以幫助我們更好的優化解決思路。在一段時間的學習之后,我總結羅列了前端中常見見的幾個算法...

    noONE 評論0 收藏0
  • Deep in JS - 收藏集 - 掘金

    摘要:今天同學去面試,做了兩道面試題全部做錯了,發過來給道典型的面試題前端掘金在界中,開發人員的需求量一直居高不下。 排序算法 -- JavaScript 標準參考教程(alpha) - 前端 - 掘金來自《JavaScript 標準參考教程(alpha)》,by 阮一峰 目錄 冒泡排序 簡介 算法實現 選擇排序 簡介 算法實現 ... 圖例詳解那道 setTimeout 與循環閉包的經典面...

    enali 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<