演算法

大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*2i+1,或者是4^i-32i+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)，但是快速排序是最好的

注釋是本人加的，可能并不是那么通俗易懂，如果有產生誤導，可洗掉注釋自行除錯代碼，如有問題，歡迎評論或者使用郵件與我聯系

標籤：JavaScript

上一篇：TypeScript Jest 除錯

下一篇：jQuery入門