前端的排序算法總結

xioqua 發布于2019-08-23 18:15 / 3087人閱讀

摘要：參考冒泡排序典型的排序方法，命名來自魚呼吸時吹出的氣泡，上層的氣泡總是最大的。時間復雜度，屬于不穩定的算法特殊情況下會是空間復雜度輔助空間是，所以空間復雜度為

參考lianjie

冒泡排序

典型的排序方法，命名來自魚呼吸時吹出的氣泡，上層的氣泡總是最大的。

思路：兩層循環，內層循環對比相鄰兩個數據（j,j+1），假設j > j + 1則交換元素位置。
外層循環為長度限制，在內層第一次循環完成后減少長度1（因為最后一個泡已經固定，為這個數組的最大值）

function bubbleSort(arr){
  for(let i = 0; i < arr.length - 1; i++){
    let flag = false;
    for(let j = 0; j < arr.length - i - 1; j++){
      if(arr[j] > arr[j + 1]){
          let temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;;
          flag = true;
      }
    }
    if(!flag){
      break;
    }
  }
  return arr;
}

加一個標志位flag，如果沒有進行交換，將標志位置為false，表示排序完成。

時間復雜度O(n^2)，最優情況下是O(n)

空間復雜度O(1)

選擇排序

顧名思義，每次都選擇最小的，然后交換位置

思路：兩層循環，內層循環為選取第一個位置的值，然后將它與剩下的值作對比，得到比它小的則交換位置。外層循環為控制第一位值的固定（一次循環后，第一位則為該數組最小的值，下一次循環不必帶上）。

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;
      }
    }
      let temp = arr[i];
      arr[i] = arr[index ];
      arr[index] = temp;
  }
  return arr;
}

時間復雜度：O(n^2)，屬于不穩定的算法（每次交換之后，它都改變了后續數組的順序）

空間復雜度：O(1)

快速排序

思路：二分法，先找一個基數，分隔出以基數為界的左右兩個數組，然后遞歸重復這個步驟，直到分組剩余一個數，則我們認為已經排列完成。

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

時間復雜度：O(n*logn)，屬于不穩定的算法,特殊情況下會是O(n^2)

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

云服務器 GPU云服務器排序算法總結字母的排序算法最好的排序算法選擇排序的算法過程

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

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

前端排序算法總結

摘要：前言排序算法可能是你學編程第一個學習的算法，還記得冒泡嗎當然，排序和查找兩類算法是面試的熱門選項。本篇將會總結一下，在前端的一些排序算法。函數的性能相信對于排序算法性能來說，時間復雜度是至關重要的一個參考因素。前言排序算法可能是你學編程第一個學習的算法，還記得冒泡嗎？當然，排序和查找兩類算法是面試的熱門選項。如果你是一個會寫快排的程序猿，面試官在比較你和一個連快排都不會寫的人的時...

happen 2019-08-21 16:40 評論0 收藏0
前端排序算法總結；前端面試題2.0；JavaScript異步編程

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

aaron 2019-08-01 17:38 評論0 收藏0
前端排序算法總結；前端面試題2.0；JavaScript異步編程

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

ARGUS 2019-08-21 16:43 評論0 收藏0
前端排序算法總結；前端面試題2.0；JavaScript異步編程

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

April 2019-08-30 15:53 評論0 收藏0
前端中經常出現的算法總結

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

noONE 2019-08-20 12:12 評論0 收藏0
Deep in JS - 收藏集 - 掘金

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

enali 2019-08-20 16:36 評論0 收藏0