算法學習筆記：排序算法(一)

renweihub 發布于2019-08-23 14:25 / 3571人閱讀

摘要：如果有錯誤或不嚴謹的地方，歡迎批評指正，如果喜歡，歡迎點贊收藏

算法對大多數前端工程師來說都是一個比較不愿意提及的話題，因為學了，感覺在工作中直接應用的場景不多，不學，大廠面試必考算法，總結來說就是：沒有學習算法的源動力，為面試學習算法總不會令人動力去學習，沒有動力想要學好算法自然也很難，對我來說，學習算法的動力就是希望寫出更高效率的代碼，更好的理解各種前端框架的設計思路，因此，后面會寫幾篇有關算法的學習筆記，下面進入這篇文章正題：排序算法

冒泡排序

排序算法中最簡單最基礎的就是冒泡排序，這種排序的思想就是相鄰兩個元素進行兩兩比較，大的放后面，每一輪選出最大的元素，讓我們來看具體代碼：

function bubbleSort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    for (var j = 0; j < arr.length - i - 1; j++) {
      var temp;
      if (arr[j] > arr[j + 1]) { // 相鄰兩個元素比較，大的往后移動
        temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp
      }
    }
  }
  console.log(arr)
}
bubbleSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])

為了更好的看到排序的過程，讓我們來看下面動態圖片：

冒泡排序，在數組本身就是有序的情況下(最好情況)，需要需要n-1次比較能完成，但是在最壞的情況下需要比較和交換n-1+n-2+n-3+...+1=n(n-1)/2次，其算法復雜度為O(n^2)

選擇排序

選擇排序是最直觀簡單的一種排序算法，具體實現思路就是：把第一個元素假定為最小元素，遍歷后面沒有排序的元素，如果發現比當最小元素小的值，就記下數組下標，循環執行，當一輪循環結束，將最小下標對應的值和當前元素調換位置，來看具體代碼實現：

function selectionSort(arr) {
  var index,temp // index:最小值下標索引，temp:臨時變量
  for (var i = 0; i < arr.length; i++) {
    index = i
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[index]) {
        index = j
      }
    }
    temp = arr[i]
    arr[i] = arr[index]
    arr[index] = temp
  }
  console.log(arr)
}
selectionSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])

為了更直觀的展示排序的過程，讓我們來看動態圖片展示：

對于選擇排序來說，比較次數是固定的，而交換次數則和數組的是否有序有關，但數組是正序時，不需要交換，當數組是倒序時，需要交換n-1次，它的時間復雜度是O(n^2)

插入排序

插入排序的實現思路和選擇排序的實現思路有點類似，先將第一個元素設為已排序，然后遍歷剩余的元素，如果已排序的元素大于當前的提取元素，已排序的元素向右移動一位，否則就將當前提取的元素插入，來看具體的代碼實現：

function insetSort(arr) {
  for (var i = 0; i < arr.length; i++) {
    var temp = arr[i] // 提取出來的元素
    var j = i - 1
    while (arr[j] > temp) { // 比較已排序元素和當前提取出來的元素
      arr[j+1] = arr[j]
      j--
    }
    arr[j+1] = temp
  }
  console.log(arr)
}
insetSort([3,44,38,5,47,15,36,26,27,2,46,4,19,50,48])

插入排序在最好的情況下，也就是數組正序排列的時候，只要執行n-1次比較和0次交換時間復雜度為O(n)，當為倒序時，需要n^2/2次比較和n^2/2次交換，其時間復雜依然為O(n^2)

總結

這篇文章主要介紹了幾個最簡單的排序算法，后面的文章會繼續介紹排序算法相關的內容。
如果有錯誤或不嚴謹的地方，歡迎批評指正，如果喜歡，歡迎點贊收藏

云服務器 GPU云服務器學習排序算法排序算法圖解排序算法總結桶排序算法

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

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

算法學習筆記一、時空復雜度

摘要：動態規劃背包士兵路徑復雜度談算法一定要考慮復雜度時間復雜度和空間復雜度時間復雜度計算機基本操作的次數匯編指令的條數尋址跳轉空間復雜度所需占用的內存字節數兩者區別空間是可以返回利用的。面試求職班一筆記算法主要研究：時空復雜度算法的特征：有窮性，確定性，可行性，可能沒有輸入，但一定有輸出常用算法窮舉法（eg：求N個數的全排列；8皇后問題）減而治之（二分查找...

wuyumin 2019-08-16 11:08 評論0 收藏0
JavaScript學習筆記 - 基礎排序算法

摘要：本文記錄了我在學習前端上的筆記，方便以后的復習和鞏固。冒泡排序算法步驟比較相鄰的元素。這步做完后，最后的元素會是最大的數。重復第二步，直到所有元素均排序完畢。得到序列第二趟，，和進行交換。本文記錄了我在學習前端上的筆記，方便以后的復習和鞏固。推薦大家去看看這一本gitBook上的書十大經典排序算法本文就是看這本書記錄的筆記。冒泡排序 1.算法步驟 1.比較相鄰的元素。如果第一個比第...

mindwind 2019-08-20 15:33 評論0 收藏0
javaScript排序算法學習筆記

摘要：排序算法學習筆記用于創建數組冒泡排序冒泡排序比較任何兩個相鄰的項，如果第一個比第二個大，則交換它們。歸并排序歸并排序是一種分治算法。完成下列操作的前提是數組均已經完成。 javaScript排序算法學習筆記 // 用于創建數組 function createNonSortedArray(size) { var array = new ArrayList(); for( ...

lentoo 2019-08-26 13:35 評論0 收藏0
算法學習筆記：排序算法(二)

摘要：上一篇中已經介紹了幾個簡單的排序算法，這一篇文章我將繼續向大家介紹排序算法相關的內容，本篇的會介紹希爾排序快速排序歸并排序以及分治算法的思想，希望通過本文章能夠加深大家對排序算法的理解。上一篇中已經介紹了幾個簡單的排序算法，這一篇文章我將繼續向大家介紹排序算法相關的內容，本篇的會介紹希爾排序、快速排序、歸并排序以及分治算法的思想，希望通過本文章能夠加深大家對排序算法的理解。希爾排序...

William_Sang 2019-08-23 14:40 評論0 收藏0
優秀程序員都應該學習的 GitHub 上開源的數據結構與算法項目

摘要：強烈推薦上值得前端學習的數據結構與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數據結構，提供進一步閱讀的解釋和鏈接。數據結構和算法必知必會的個代碼實現。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言算法為王。想學好前端，先練好內功，內功不行，就算招式練的再花哨，終究成不了高手；只有內功深厚者，前端之路才會走得...

cheukyin 2019-08-26 10:17 評論0 收藏0