算法學習筆記：排序算法

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

冒泡排序

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

function bubbleSort(arr) {
  for (var i = ; i < arr.length - ; i++) {
    for (var j = ; j < arr.length - i - ; j++) {
      var temp;
      if (arr[j] > arr[j + ]) { // 相鄰兩個元素比較，大的往後移動
        temp = arr[j]
        arr[j] = arr[j+]
        arr[j+] = temp
      }
    }
  }
  console.log(arr)
}
bubbleSort([,,,,,,,,,,,,,,])
複制代碼

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

冒泡排序，在數組本身就是有序的情況下(最好情況)，需要需要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 = ; i < arr.length; i++) {
    index = i
    for (var j = i + ; 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([,,,,,,,,,,,,,,])
複制代碼

為了更直覺的展示排序的過程，讓我們來看動态圖檔展示：

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

插入排序

插入排序的實作思路和選擇排序的實作思路有點類似，先将第一個元素設為已排序，然後周遊剩餘的元素，如果已排序的元素大于目前的提取元素，已排序的元素向右移動一位，否則就将目前提取的元素插入，來看具體的代碼實作：

function insetSort(arr) {
  for (var i = ; i < arr.length; i++) {
    var temp = arr[i] // 提取出來的元素
    var j = i - 
    while (arr[j] > temp) { // 比較已排序元素和目前提取出來的元素
      arr[j+] = arr[j]
      j--
    }
    arr[j+] = temp
  }
  console.log(arr)
}
insetSort([,,,,,,,,,,,,,,])
複制代碼

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

希爾排序

希爾排序又叫縮小增量排序，希爾排序的主要思想是使數組中任意相隔h的元素都是有序的，h就是希爾增量，實作的希爾排序的方法就是：對相隔h的元素進行分組，對每組進行使用插入排序，使子序列變成有序序列，增量逐漸遞減一直到1為止，在例子中我将h增量設為array.length/2，遞減的過程就是不斷除以2，是不是被我的解釋弄的有點暈，讓我們先來看一個示範過程了解一下:

如圖所示，一共15個元素，增量就是15/2為7，第一輪的分組即為[2, 26, 48],[44, 26],[38, 2],[5, 46],[47, 4],[15, 19],[36, 50],然後進行插入排序,得到新的序列[ 3, 27, 2, 5, 4, 15, 36, 26, 44, 38, 46, 47, 19, 50, 48 ]，然後在進行分組，增量為7/2為3：

第二輪分組[3, 5, 36, 2, 19],[44, 47, 26, 46, 50], [38, 15, 27, 4, 48],然後進行插入排序，得到序列[ 3, 4, 2, 5, 26, 15, 19, 27, 44, 36, 46, 47, 38, 50, 48 ]，然後再進行分組，增量為3/2為1，再插入排序得到的就是一個有序序列了，最好讓我們來看具體的代碼實作：

function shellSort(arr) {
  var n = arr.length
  for (var gap = parseInt(n/); gap > ; gap=parseInt(gap/)) {
    for (var i=gap; i<arr.length; i++) {
      var j = i - gap, temp = arr[i]
      while (arr[j] > temp) {
        arr[j+gap] = arr[j]
        j = j - gap
      }
      arr[j+gap] = temp
    }
  }
  console.log(arr)
}
shellSort([,,,,,,,,,,,,,,])
複制代碼

其實希爾排序也不難，隻要按照上面的分解圖示一步一步的了解去編寫，相信大家都能寫得出來，上面這種形式的增量設定就是二分的形式設定，然後插入排序，還有一種希爾排序的寫法就是自定義增量，然後子序列裡的元素兩兩比較，來看具體代碼：

function shellSort(arr) {
  var n = arr.length, gap = 
  while (gap < n / ) {
    gap = gap *  + 
  }
  for (gap; gap > ; gap=parseInt(gap/)) {
    for (var i=gap; i<arr.length; i++) {
      for (var j = i - gap;j >= ; j-=gap) {
        if (arr[j] > arr[j+gap]) {
          var temp = arr[j+gap]
          arr[j+gap] = arr[j]
          arr[j] = temp
        }
      }
    }
  }
  console.log(arr)
}
shellSort([,,,,,,,,,,,,,,])
複制代碼

希爾排序更高效的原因在于它權衡了子數組的規模和有序性，各個子數組都很短，排序之後的子數組都是部分有序的，是以在希爾排序的效率要比插入排序高。

分治法

在介紹歸并排序和快速排序有必要先介紹一下分治法相關的内容，為什麼呢？因為歸并排序和快速排序都是分治法的典型應用。分治法的設計思路就是：将一個大問題分解成若幹個規模嬌小的相同子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解決這些子問題，然後将各個子問題的解合并得到原問題的解分治法所能解決的問題一般有如下幾個特點：

把該問題縮小到一定規模就可以容易解決
該問題可以被分解為若幹個規模較小的相同問題
利用該問題的子問題的解向上合并可以得到該問題的解
該問題分解出的子問題是互相獨立的

歸并排序

歸并排序就是分治法的典型應用之一，歸并排序的實作有兩種，一種是自頂向下的歸并排序，另一種就是自底向上的歸并排序。

自頂向下的歸并排序

向來看第一種，自頂向下的歸并排序的實作思路是不斷二分，然後對二分後的最小序列分别進行排序後，再将排序後的結果向上合并得到最終的有序數組，讓我們先通過一個樹結構來了解歸并排序的過程：

從圖中可以看到将一個數組0-14的元素不斷二分，分到最後一層，然後互相比較，得到新的有序序列，然後向上合并，在進行比較，不斷反複，合并出最終的有序序列，這就是自頂向下的歸并排序的思路，通過這個思路你是否能自己寫出排序的方法呢？

好了，接下來就讓我們看看具體的代碼實作:

function sort(arr) {
  var n = arr.length
  if (n < ) return arr
  var mid = Math.ceil(n / )
  var left = arr.slice(, mid)
  var right = arr.slice(mid)
  return merge(sort(left), sort(right));
}

function merge(left, right){
  var result = []
  while (left.length && right.length) {
    if (left[] < right[]) {
      result.push(left.shift())
    } else {
      result.push(right.shift())
    }
  }
  while (left.length) {
    result.push(left.shift())
  }
  while (right.length) {
    result.push(right.shift())
  }
  return result;
}
var arr=[,,,,,,,,,,,,,,];
console.log(sort(arr))
複制代碼

代碼實作是不是很容易了解呢？相信大家經過仔細的思考過後都能看得懂，為了友善更好的了解，來看一下動圖的排序過程：

自底向上的歸并排序

自底向上的歸并排序思路是将長度為n的數組看成n個長度為1的數組，然後兩兩向上歸并排序，得到新的數組，不斷向上歸并排序，直到得到長度為n的數組，這樣的排序比之前自頂向下的排序代碼要少，下面來看具體的代碼實作：

function merge(arr, start, mid, end){
  var i = start, j= mid + , copy = []
  for (var k = start; k <= end; k++) {
    copy[k] = arr[k]
  }
  for (var k = start; k <= end; k++) {
    if (i > mid) { // 左邊取完取右邊的元素
      arr[k] = copy[j]
      j++
    } else if (j > end) { // 右邊取完取左邊的元素
      arr[k] = copy[i]
      i++
    } else if (copy[j] < copy[i]) { // 右邊的元素小于左邊的元素，取右邊的元素
      arr[k] = copy[j]
      j++ 
    } else { // 左邊的元素小于右邊的元素，取左邊的元素
      arr[k] = copy[i]
      i++
    }
  }
  console.log(arr)
}

function sort(arr) {
  var n = arr.length
  for (var i = ; i < n; i = i + i) { // i子數組的大小
    for (var j = ; j < n - i; j = j + i + i) { // j數組的索引
      var start = j
      var end = Math.min(j + i + i - , n)
      var mid = parseInt((start + end) / )
      merge(arr, start, mid, end)
    }
  }
}

var arr=[,,,,,,,,,,,,,,];
sort(arr)
複制代碼

為了友善了解，已經在代碼中加了必要的注釋，可能這段代碼比之前的要難了解一些，需要大家耐心多花一些時間去了解

快速排序

快速排序也是一種分治的排序算法，由于它實作簡單并且效率比一般的排序算法高，是以，它的應用範圍非常廣泛，接下來讓我們來看快速排序的排序過程：

将數組的第一個元素做為基準，從數組末尾開始找比基準小的數，找到就停下來，記下索引j，然後從基準右邊開始找比基準大的數找到停下來，記下索引i，然後交換i和j上的元素，得到數組：

然後繼續從44的位置開始找比基準3小的一直移動到2，此時索引i和索引j相等，将基準3和i、j對應的值交換位置得到：

此時基準數3前面的元素都是比它小的數，後面元素都是比它大的數，然後從基準數前後拆成兩個數組，在遞歸執行前面同樣的操作。看來上面的排序過程，你是不是有代碼的實作了呢？可以先試着寫一下實作的代碼，這樣更容易了解，接下來就讓我來看一下具體代碼：

function sort(arr, left, right) {
  var temp = arr[left],i = left, j = right, t;
  if (left < right) {
    while (i != j) {
      while (arr[j] >= temp && i < j) {
        j--
      }
      while (arr[i] <= temp && i < j) {
        i++
      }
      if (i < j) {
        t = arr[i]
        arr[i] = arr[j]
        arr[j] = t
      }
    }
    arr[left] = arr[i]
    arr[i] = temp
    sort(arr, left, i - )
    sort(arr, i + , right)
  }
  return arr
}
var arr=[,,,,,,,,,,,,,,];
console.log(sort(arr, , arr.length - ))
複制代碼

看了代碼之後是不是覺得并不難呢？這種快速排序的實作其實有一個問題不知道大家注意到沒有，當數組中有多個重複元素的時候，重複的元素隻要排了一個就不需要重複排了，但是這中快速排序的實作并沒有考慮這種情況，即便重複的元素還是會執行排序，是以有人提出了更優的快速排序方法“三向切分的快速排序”，讓我們先來看代碼實作有什麼不同：

function sort(arr, left, right) {
  var temp = arr[left],i = left, j = right,k = left + , t;
  if (left < right) {
    while (k <= j) {
      if (arr[k] < temp) {
        t = arr[k]
        arr[k] = arr[i]
        arr[i] = t
        i++;
        k++;
      } else if (arr[k] > temp) {
        t = arr[k]
        arr[k] = arr[j]
        arr[j] = t
        j--;
      } else {
        k++;
      }
    }
    sort(arr, left, i - )
    sort(arr, j + , right)
  }
  return arr
}
var arr=[,,,,,,,,,,,,,,,,];
console.log(sort(arr, , arr.length - ))
複制代碼

總體思路和之前的一樣保證基準值前面的比它小後面的比它大，唯一不同的地方就是用了一個臨時下标k去作比較，把小的丢到基準值前面，大的值就和末尾的值交換，得到新值再與基準值比較，當與基準值相等的時候，就隻需要将臨時下标的值+1而不需要排序了

總結

這篇文章主要介紹了幾種常用的排序算法，也是個人算法學習的記錄，後面會繼續寫一些關于算法與資料結構相關的内容，希望感興趣的朋友可以多多關注。

如果本篇文章有錯誤或不嚴謹的地方，歡迎批評指正，如果喜歡，歡迎點贊收藏，希望能在評論裡看到大家的交流

算法學習筆記：排序算法

冒泡排序

選擇排序

插入排序

希爾排序

分治法

歸并排序

自頂向下的歸并排序

自底向上的歸并排序

快速排序

總結

繼續閱讀

underscore模闆功能的使用和學習

Java經典面試題詳解：帶你手撸紅黑樹總結

python面試題之Python 的特點和優點是什麼

面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。一、疊代器差別二、vector三、Map、Set四、vector_map 為什麼比map效率高五、如何選擇六、容器選擇原則七、效率對比

poj3249

CSS之折疊菜單

web開發之前後端渲染

JavaScript的那些坑之事件代理事件代理事件階段

測試理論面試題

軟體測試面試題整理

PAT 1089 Insert or Merge[難]

ACS基本配置-權限等級管理

vue （vue2.0）使用總結(從大體結構總結)

父子元件間傳值的實作父子元件間傳值的實作

vue搭建過程及出現問題

軟體測試工程師跳槽：收到面試電話後，我會做的事。