演算法

大O表示法

用來描述電腦演算法的效率，

數據項個數發生變化時，演算法的效率也會跟著發生改變

常見的大O表示方法

當我們寫一個演算法的時候，其運行過程，並不是完全跟上面例子相同，它可能是個多項式，我們可以通過一些推導得出它們的大O表示法

推導成大O表示法

1、用常量1取代運行時間中所有的加法常量

2、在修改後的運行次數函數中，只保留最高階項

3、如果最高存在且不為1，則去除與這個項相乘的常數

舉例

1、如果得出的是一個常量，可以直接用上面第一條比如：76 用大O表示就是O(1)

2、如果得出的是多項式，比如：2N$^2$ + 3n + 1，根據上面第二條就等於 2N$^2$再根據第三條就等於O(N$^2$)

排序演算法

註意: 如果你在面試中不知道寫什麼排序演算法好，儘可能寫快速排序演算法，在大部分情況下，快速排序是效率最高的

排序演算法有很多例如：冒泡、選擇、插入、歸併、計數、基數、希爾、堆、桶。

用三個簡單排序和兩個高級排序進行實例。

三個簡單排序

冒泡

思路

1、對未排序的的各個元素從頭到尾依次比較相鄰的兩個元素大小關係

2、如果左邊比右邊的高，則兩者交換位置

3、向右移動一個位置，比較後面兩個

4、當走到最右邊的時候，最高的一定被放在了最右邊

5、按照這個思路，從左端重新開始，這次走到倒數第二個位置即可

6、依次類推就可以將數據排序完成

代碼

// 封裝ArrayList
function ArrayList() {
  this.array = []

    ArrayList.prototype.insert = function (item) {
    this.array.push(item)
  }

  ArrayList.prototype.toString = function () {
    return this.array.join()
  }
}
// 交換位置函數
ArrayList.prototype.swap = function (m, n) {
  var temp = this.array[m]
  this.array[m] = this.array[n]
  this.array[n] = temp
}
ArrayList.prototype.bubbleSort = function () {
  // 1.獲取數組的長度
  var length = this.array.length

  // 2.反向迴圈, 因此次數越來越少
  for (var i = length - 1; i >= 0; i--) {
    // 3.根據i的次數, 比較迴圈到i位置
    for (var j = 0; j < i; j++) {
      // 4.如果j位置比j+1位置的數據大, 那麼就交換
      if (this.array[j] > this.array[j+1]) {
        // 交換
        this.swap(j, j+1)
      }
    }
  }
}

效率

根據N項數據的比較次數

是（N-1）+（N-2）+（N-3）+…+1 = N*(N-1)/2

推導成大O表示法N*(N-1)/2 = N$^2$/2-N/2，根據規則二變成N$^2$/2再根據規則三變成N$^2$

因此冒泡排序的比較次數大O表示法是O(N$^2$)

根據N項數據的交換次數

是N*(N-1)/2（比較次數）／2結果是交換的次數，為什麼除以2是因為如果有兩次比較才需要交換一次（不可能每次比較都需要交換一次），那麼就需要在比較次數的基礎上再除以2，由於常量不包含在大O表示法中，因此我們可以認為交換次數的大O表示法也是O(N$^2$)

選擇

選擇排序改進了冒泡排序，將交換次數由O(N$^2$)減少到了O(N)

但是比較次數依然是O(N$^2$)

思路

1、選定第一個索引位置，然後和後面的元素依次比較

2、如果後面的項，小於第一個索引位置的項，則與第一個交換位置

3、經過第一輪的比較後，可以確定第一個位置的項是最小的

4、然後用同樣的方式把剩下的項逐個比較

5、選擇排序，第一輪會選出第一小的值，第二輪會選出第二小的值，直到最後

代碼

ArrayList.prototype.selectionSort = function () {
  // 1.獲取數組的長度
  var length = this.array.length

  // 2.外層迴圈: 從0位置開始取出數據, 直到length-2位置
  for (var i = 0; i < length - 1; i++) {
    // 3.內層迴圈: 從i+1位置開始, 和後面的內容比較
    var min = i
    for (var j = min + 1; j < length; j++) {
      // 4.如果i位置的數據大於j位置的數據, 記錄最小的位置
      if (this.array[min] > this.array[j]) {
        min = j
      }
    }
    this.swap(min, i)
  }
}

效率

根據N項數據的比較次數

和冒泡排序的相同都是N*(N-1)/2

因此選擇排序的比較次數大O表示法也是O(N$^2$)

根據N項數據的交換次數

選擇排序每次進行選擇的時候，最多需要交換一次，一共遍歷了N-1次

所以選擇排序的交換次數用大O表示法是O(N)，所以選擇排序在效率上通常是被認為高於冒泡排序的

插入

插入排序是簡單排序中效率最好的

思路

局部有序

1、插入排序的核心思想是局部有序

2、局部有序就好比一個隊列中，我們選了一個作為標記的成員

3、被標記的左邊成員已經是局部有序的

4、這意味著，有一部分人是按照順序排列好的，有一部分人還是沒有順序

插入排序的思路

1、從第一個元素開始，該元素可以被認為已經被排序

2、取出下一個元素，在已經排序的隊列中從後向前掃描

3、如果該元素（已排序）的大於新元素，將該元素移到下一個位置

4、重覆第三步驟，直到已經找到已排序的元素小於或者等於新元素的位置

5、將新元素插入到該位置後，再重覆上列步驟

代碼

 ArrayList.prototype.insertionSort = function () {
   //獲取數據長度
   var length = this.arr.length;
   // 第一次迴圈直接從第二項開始，第一項預設為已排序，結尾是長度-1項
   for(var i = 1;i<length;i++){
     // 因為不斷訪問要插入的項，所以把它保存起來，方便逐個和已排序對比
     var temp = this.arr[i];
     // 由於要從i-1項不斷往前找，先把i備份成j，通過操作j來不斷向前
     var j = i;
     // 第一次獲取到前面一項做對比，如果前面的小於要插入的，j不能為0，不然會訪問到-1項
     while(this.arr[j-1]>temp && j>0){
       // 如果大於，就讓當前項等於數組前一個項
       // 當前項不會丟失，已經保存在temp
       this.arr[j] = this.arr[j-1]
       // 再將j遞減，這樣可以在已排序數組中把位置向前移動
       j--
     }
     // 小於要插入的，直接重新賦值到當前項
     this.arr[j] = temp
   }
 }

效率

插入排序的比較次數

1、第一趟時需要的最多次數是1，第二趟時需要的是2，依次類推最後一趟是n-1次

2、因此插入排序的最多次是：1+2+3+...+N-1 = N *(N-1)/2

3、然而每趟發現插入點的之前，平均只有全體數據項的一半需要進行比較

4、我們可以再除以2得到 N *(N-1)/4，所以相對於選擇排序，其比較次數是少了一半的

插入排序的複製次數

1、第一趟時，需要的最多複製次數是1，第二趟最多的複製次數是2，依次類推，最後一趟是N-1次

2、因此複製次數最多是1+2+3+...+N-1=N *(N-1)/2

3、平均次數N *(N-1)/4

兩個高級排序

希爾

希爾排序是插入排序的一種改進版，速度更快了，他主要採用了一種分組的方式

思路

希爾排序的核心就是將數據進行分組，但不是按順序等量分組，而是

1、設置一個間隔數，例如間隔數是3那麼,[n,n+3]是一組，[n+1,n+3+1]是一組

2、將所有數據都分好組後，讓他們組內進行排序

3、排好序後，數值肯定離自己正確位置很近了，然後不斷縮短間隔數，

4、直到間隔數為1，就是插入排序所執行的邏輯了

增量

上面的間隔數值是我們舉例的，那麼到底選擇多少合適呢？

1、選擇合適的增量

• 在希爾排序的原稿中，他建議的初始間距是N/2，把每趟排序分成兩半
• 如果N=100的數組，那麼間隔序列為：50，25，12，6，3，1
• 這個方法的好處就是不需要在排序前為找到合適的增量進行計算

2、Hibbard增量排序

• 增量的演算法為2^k-1，也就是1，3，4，7...等等
• 這種增量的最壞複雜度為O(N^3/2),猜想的平均複雜度為O(N^5/4),目前尚未被證明

3、Sedgewick增量排序

• {1,5,19,41,109….}該序列中的項或者是94^i-9*2^i+1,或者是4^i-32^i+1
• 這種增量最壞的複雜度為O(N^4/3),平均複雜度為O(N7^6),但也沒有被完全證明

代碼

這裡我們使用上面的第一種

ArrayList.prototype.shellSort = function () {
    // 1、獲取數組長度
  var length = this.array.length
    // 2、獲取初次間隔值，防止小數出現，使用floor
  var gap = Math.floor(length / 2)
    // 3、如果間隔值小於1了就停止，
  // 最後一次等於1的時候就跟插入排序執行的一樣了
  while (gap >=1) {
    // 4、實現插入排序，起始點是間隔的位置，比如是5，就是數組中下標為5的
    for (var i = gap; i < length; i++) {
            // 保存間隔的位置數
      var j = i
      // 保存間隔位置的值
      var temp = this.array[i]
            // 5、尋找合適位置
      // 第一個判斷語句是防止溢出左側，
      // 第二個判斷語句是左側的上一個間隔位置的值，需要大於當前的
      while (j > gap - 1 && this.array[j - gap] > temp) {
        // 如果大於，就讓左側上一個間隔位置的值移動到當前位置
        this.array[j] = this.array[j - gap]
        // 就讓j值等於原來左側上一個間隔位置的值
        j -= gap
      }
            // 如果不大於還是保存在原來的位置
            // 6、最後將間隔的位置值插入到j，也就是屬於他的合適位置
      this.array[j] = temp
    }

        // 7、縮小間隔值，直到等於1
    gap = Math.floor(gap / 2)
  }
}

效率

1、希爾排序的效率跟增量是有關係的

2、它的效率證明非常困難

3、但是經過統計，最壞的情況下時間複雜度為O(N$^2$)，通常情況下都是要好於O(N$^2$)

4、在合適的增量和某些數量N的情況下，還要好於快速排序。

快速

快速排序幾乎可以說是所有排序中速度最快的，它可以在一次迴圈中(其實是遞歸調用)，找出某個元素的正確位置，並且該元素之後不需要任何移動

1、但是，沒有一種演算法是在任意情況下都是最優的

2、希爾排序在特定情況下要快於快速排序

3、但是快速排序在大多數情況下都是要快於希爾排序的

思路

比如我們有這樣一組數據[13，81，92，43，65，34，57，26，75，6]

1、我們從其中選出了65，(也可以是其他任意數字)

2、通過演算法，將所有小於65的放到65左邊，大於65的放到65的右邊

3、再遞歸處理左邊的數據，(比如從左邊選了31來處理左側)，遞歸處理右邊的數據(比如選了75來處理,但是選81可能最合適，因為就不用再往右邊放了）

4、就這樣通過不斷的遞歸處理，完成排序

樞紐

上面選擇的65，31，75或者81就是樞紐

怎麼樣才能選擇合適的樞紐呢

我們可以取數組的頭，中，尾的中位數

7，4，5，8，9選出來的就是7，5，9，排好序就是5，7，9中位數就是7

代碼

// 位置交換函數
ArrayList.prototype.swap = function (m, n) {
  var temp = this.array[m]
  this.array[m] = this.array[n]
  this.array[n] = temp
}

// 選擇樞紐
ArrayList.prototype.median = function (left, right) {
  // 1.求出中間的位置，以防有小數點，所以使用floor
  var center = Math.floor((left + right) / 2)

  // 2.判斷並且進行交換
  if (this.array[left] > this.array[center]) {
    this.swap(left, center)
  }
  if (this.array[center] > this.array[right]) {
    this.swap(center, right)
  }
  if (this.array[left] > this.array[right]) {
    this.swap(left, right)
  }

  // 3.巧妙的操作: 將center移動到right - 1的位置.
  // 這樣方便我們迴圈只對左側數據進行操作
  this.swap(center, right - 1)

  // 4.返回樞紐
  return this.array[right - 1]
}
// 快速排序實現
ArrayList.prototype.quickSort = function () {
  this.quickSortRec(0, this.array.length - 1)
}

ArrayList.prototype.quickSortRec = function (left, right) {
  // 0.遞歸結束條件，對比的值超出了邊界值，比如下標為length或者下標為-1了
  if (left >= right) return

  // 1.獲取樞紐
  var pivot = this.median(left, right)

  // 2.開始進行交換,保存兩個對比的下標值
  var i = left
  var j = right - 1
  while (true) {
    // 不斷改變i的值
    while (this.array[++i] < pivot) { }
    // 不斷改變j的值
    while (this.array[--j] > pivot) { }
    // i和j表示的是下標值
    if (i < j) {
      this.swap(i, j)
    } else {
      // 如果i>=j了表示已經溢出了，所以直接break
      break
    }
  }

  // 3.將樞紐放在正確的位置
  this.swap(i, right - 1)

  // 4.遞歸調用左邊
  this.quickSortRec(left, i - 1)
  // 5.遞歸調用右邊
  this.quickSortRec(i + 1, right)
}

效率

最壞情況的效率

1、如果每次選擇的樞紐都是最左邊或者最右邊的時候效率最差

2、那麼效率等同於冒泡排序

3、而我們的例子中不會有最壞情況，因為我們選的是三個值的中位值

平均效率

1、快速排序的平均效率是O(N*logN)

2、雖然其他某些演算法的效率也可以達到O(N*logN)，但是快速排序是最好的

註釋是本人加的，可能並不是那麼通俗易懂，如果有產生誤導，可刪除註釋自行調試代碼，如有問題，歡迎評論或者使用郵件與我聯繫