一、大O表示法

大O表示法：

• 在計(jì)算機(jī)中采用粗略的度量來(lái)描述計(jì)算機(jī)算法的效率，這種方法被稱(chēng)為 “大O”表示法
• 在數(shù)據(jù)項(xiàng)個(gè)數(shù)發(fā)生改變時(shí)，算法的效率也會(huì)跟著改變。所以說(shuō)算法A比算法B快兩倍，這樣的比較是沒(méi)有意義的。
• 因此我們通常使用算法的速度隨著數(shù)據(jù)量的變化會(huì)如何變化的方式來(lái)表示算法的效率，大O表示法就是方式之一。

常見(jiàn)的大O表示形式

不同大O形式的時(shí)間復(fù)雜度：

可以看到效率從大到小分別是：O（1）> O（logn）> O（n）> O（nlog(n)）> O（n2）> O（2n）

推導(dǎo)大O表示法的三條規(guī)則：

• 規(guī)則一：用常量1取代運(yùn)行時(shí)間中所有的加法常量。如7 + 8 = 15，用1表示運(yùn)算結(jié)果15，大O表示法表示為O（1）；
• 規(guī)則二：運(yùn)算中只保留最高階項(xiàng)。如N^3 + 3n +1，大O表示法表示為：O（N3）;
• 規(guī)則三：若最高階項(xiàng)的常數(shù)不為1，可將其省略。如4N2，大O表示法表示為：O（N2）;

二、排序算法

這里主要介紹幾種簡(jiǎn)單排序和高級(jí)排序：

• 簡(jiǎn)單排序： 冒泡排序、選擇排序、插入排序；
• 高級(jí)排序： 希爾排序、快速排序；

此處創(chuàng)建一個(gè)列表類(lèi)ArrayList并添加一些屬性和方法，用于存放這些排序方法：

    //創(chuàng)建列表類(lèi)
    function ArrayList() {
      //屬性
      this.array = []

      //方法
      //封裝將數(shù)據(jù)插入到數(shù)組中方法
      ArrayList.prototype.insert = function(item){
        this.array.push(item)
      }

      //toString方法
      ArrayList.prototype.toString = function(){
        return this.array.join('-')
      }

      //交換兩個(gè)位置的數(shù)據(jù)
      ArrayList.prototype.swap = function(m, n){
        let temp  = this.array[m]
        this.array[m] = this.array[n]
        this.array[n] = temp
      }

1.冒泡排序

冒泡排序的思路：

• 對(duì)未排序的各元素從頭到尾依次比較相鄰的兩個(gè)元素大小關(guān)系；
• 如果左邊的人員高，則將兩人交換位置。比如1比2矮，不交換位置；
• 向右移動(dòng)一位，繼續(xù)比較2和3，最后比較 length - 1 和 length - 2這兩個(gè)數(shù)據(jù)；
• 當(dāng)?shù)竭_(dá)最右端時(shí)，最高的人一定被放在了最右邊；
• 按照這個(gè)思路，從最左端重新開(kāi)始時(shí)，只需要走到倒數(shù)第二個(gè)位置即可；

實(shí)現(xiàn)思路：

兩層循環(huán)：

• 外層循環(huán)控制冒泡趟數(shù)：
  • 第一次：j = length - 1，比較到倒數(shù)第一個(gè)位置 ；
  • 第二次：j = length - 2，比較到倒數(shù)第二個(gè)位置 ；
• 內(nèi)層循環(huán)控制每趟比較的次數(shù)：
  • 第一次比較： i = 0，比較 0 和 1 位置的兩個(gè)數(shù)據(jù)；
  • 最后一次比較：i = length - 2,比較length - 2和 length - 1兩個(gè)數(shù)據(jù)；

詳細(xì)過(guò)程如下圖所示：

動(dòng)態(tài)過(guò)程：

代碼實(shí)現(xiàn)：

      //冒泡排序
      ArrayList.prototype.bubblesor = function(){
        //1.獲取數(shù)組的長(zhǎng)度
        let length = this.array.length

        //外層循環(huán)控制冒泡趟數(shù)
        for(let j = length - 1; j >= 0; j--){
          //內(nèi)層循環(huán)控制每趟比較的次數(shù)
          for(let i = 0; i < j; i++){
          if (this.array[i] > this.array[i+1]) {
            //交換兩個(gè)數(shù)據(jù)
            let temp  = this.array[i]
        	this.array[i] = this.array[i+1]
        	this.array[i+1] = temp
          }
        }
        }
      }

測(cè)試代碼：

    //測(cè)試類(lèi)
    let list = new ArrayList()

    //插入元素
    list.insert(66)
    list.insert(88)
    list.insert(12)
    list.insert(87)
    list.insert(100)
    list.insert(5)
    list.insert(566)
    list.insert(23)
    
    //驗(yàn)證冒泡排序
    list.bubblesor()
    console.log(list);

測(cè)試結(jié)果：

冒泡排序的效率：

• 上面所講的對(duì)于7個(gè)數(shù)據(jù)項(xiàng)，比較次數(shù)為：6 + 5 + 4 + 3 + 2 + 1;
• 對(duì)于N個(gè)數(shù)據(jù)項(xiàng)，比較次數(shù)為：(N - 1) + (N - 2) + (N - 3) + … + 1 = N * (N - 1) / 2；如果兩次比較交換一次，那么交換次數(shù)為：N * (N - 1) / 4；
• 使用大O表示法表示比較次數(shù)和交換次數(shù)分別為：O（ N * (N - 1) / 2）和O（ N * (N - 1) / 4），根據(jù)大O表示法的三條規(guī)則都化簡(jiǎn)為：O（N^2）;

2.選擇排序

選擇排序改進(jìn)了冒泡排序：

• 將交換次數(shù)由O（N^2）減小到O（N）；
• 但是比較次數(shù)依然是O（N^2）；

選擇排序的思路：

• 選定第一個(gè)索引的位置比如1，然后依次和后面的元素依次進(jìn)行比較；
• 如果后面的元素，小于索引1位置的元素，則交換位置到索引1處；
• 經(jīng)過(guò)一輪的比較之后，可以確定一開(kāi)始指定的索引1位置的元素是最小的；
• 隨后使用同樣的方法除索引1意外逐個(gè)比較剩下的元素即可；
• 可以看出選擇排序，第一輪會(huì)選出最小值，第二輪會(huì)選出第二小的值，直到完成排序。

實(shí)現(xiàn)思路：

兩層循環(huán)：

• 外層循環(huán)控制指定的索引：
  • 第一次：j = 0，指定第一個(gè)元素 ；
  • 最后一次：j = length - 1，指定最后一個(gè)元素 ；
• 內(nèi)層循環(huán)負(fù)責(zé)將指定索引（i）的元素與剩下（i - 1）的元素進(jìn)行比較；

動(dòng)態(tài)過(guò)程：

代碼實(shí)現(xiàn)：

      //選擇排序
      ArrayList.prototype.selectionSort = function(){
        //1.獲取數(shù)組的長(zhǎng)度
        let length = this.array.length

        //2.外層循環(huán)：從0開(kāi)始獲取元素
        for(let j = 0; j < length - 1; j++){
          let min = j
          //內(nèi)層循環(huán)：從i+1位置開(kāi)始，和后面的元素進(jìn)行比較
        for(let i = min + 1; i < length; i++){
          if (this.array[min] > this.array[i]) {
            min = i
          }
        }
        this.swap(min, j)
        }
      }

測(cè)試代碼：

    //測(cè)試類(lèi)
    let list = new ArrayList()

    //插入元素
    list.insert(66)
    list.insert(88)
    list.insert(12)
    list.insert(87)
    list.insert(100)
    list.insert(5)
    list.insert(566)
    list.insert(23)
    
    //驗(yàn)證選擇排序
    list.selectionSort()
    console.log(list);

測(cè)試結(jié)果：

選擇排序的效率：

• 選擇排序的比較次數(shù)為：N * (N - 1) / 2，用大O表示法表示為：O（N^2）;
• 選擇排序的交換次數(shù)為：(N - 1) / 2，用大O表示法表示為：O（N）;
• 所以選擇排序的效率高于冒泡排序；

3.插入排序

插入排序是簡(jiǎn)單排序中效率最高的一種排序。

插入排序的思路：

• 插入排序思想的核心是局部有序。如圖所示，X左邊的人稱(chēng)為局部有序；
• 首先指定一數(shù)據(jù)X（從第一個(gè)數(shù)據(jù)開(kāi)始），并將數(shù)據(jù)X的左邊變成局部有序狀態(tài)；
• 隨后將X右移一位，再次達(dá)到局部有序之后，繼續(xù)右移一位，重復(fù)前面的操作直至X移至最后一個(gè)元素。

插入排序的詳細(xì)過(guò)程：

動(dòng)態(tài)過(guò)程：

代碼實(shí)現(xiàn)：

      //插入排序
      ArrayList.prototype.insertionSort = function(){
        //1.獲取數(shù)組的長(zhǎng)度
        let length = this.array.length

        //2.外層循環(huán):從第二個(gè)數(shù)據(jù)開(kāi)始，向左邊的已經(jīng)局部有序數(shù)據(jù)進(jìn)行插入
        for(let i = 1; i < length; i++){
          //3.內(nèi)層循環(huán)：獲取i位置的元素，使用while循環(huán)(重點(diǎn))與左邊的局部有序數(shù)據(jù)依次進(jìn)行比較
          let temp = this.array[i]
          let j = i
          while(this.array[j - 1] > temp && j > 0){
            this.array[j] = this.array[j - 1]//大的數(shù)據(jù)右移
            j--
          }
          //4.while循環(huán)結(jié)束后，index = j左邊的數(shù)據(jù)變?yōu)榫植坑行蚯襛rray[j]最大。此時(shí)將array[j]重置為排序前的數(shù)據(jù)array[i]，方便下一次for循環(huán)
          this.array[j] = temp
        }
      }

測(cè)試代碼：

   //測(cè)試類(lèi)
    let list = new ArrayList()

    //插入元素
    list.insert(66)
    list.insert(88)
    list.insert(12)
    list.insert(87)
    list.insert(100)
    list.insert(5)
    list.insert(566)
    list.insert(23)
    // console.log(list);

    //驗(yàn)證插入排序
    list.insertionSort()
    console.log(list);

測(cè)試結(jié)果：

插入排序的效率：

• 比較次數(shù)： 第一趟時(shí)，需要的最大次數(shù)為1；第二次最大為2；以此類(lèi)推，最后一趟最大為N-1；所以，插入排序的總比較次數(shù)為N * (N - 1) / 2；但是，實(shí)際上每趟發(fā)現(xiàn)插入點(diǎn)之前，平均只有全體數(shù)據(jù)項(xiàng)的一半需要進(jìn)行比較，所以比較次數(shù)為：N * (N - 1) / 4；
• 交換次數(shù)：指定第一個(gè)數(shù)據(jù)為X時(shí)交換0次，指定第二個(gè)數(shù)據(jù)為X最多需要交換1次，以此類(lèi)推，指定第N個(gè)數(shù)據(jù)為X時(shí)最多需要交換N - 1次，所以一共需要交換N * (N - 1) / 2次，平局次數(shù)為N * (N - 1) / 2；
• 雖然用大O表示法表示插入排序的效率也是O（N^2），但是插入排序整體操作次數(shù)更少，因此，在簡(jiǎn)單排序中，插入排序效率最高；

4.希爾排序

希爾排序是插入排序的一種高效的改進(jìn)版，效率比插入排序要高。

希爾排序的歷史背景：

• 希爾排序按其設(shè)計(jì)者希爾（Donald Shell）的名字命名，該算法由1959年公布；
• 希爾算法首次突破了計(jì)算機(jī)界一直認(rèn)為的**算法的時(shí)間復(fù)雜度都是O（N^2）**的大關(guān)，為了紀(jì)念該算法里程碑式

的意義，用Shell來(lái)命名該算法；

插入排序的問(wèn)題：

• 假設(shè)一個(gè)很小的數(shù)據(jù)項(xiàng)在很靠近右端的位置上，這里本應(yīng)該是較大的數(shù)據(jù)項(xiàng)的位置；
• 將這個(gè)小數(shù)據(jù)項(xiàng)移動(dòng)到左邊的正確位置，所有的中間數(shù)據(jù)項(xiàng)都必須向右移動(dòng)一位，這樣效率非常低；
• 如果通過(guò)某種方式，不需要一個(gè)個(gè)移動(dòng)所有中間的數(shù)據(jù)項(xiàng)，就能把較小的數(shù)據(jù)項(xiàng)移到左邊，那么這個(gè)算法的執(zhí)行速度就會(huì)有很大的改進(jìn)。

希爾排序的實(shí)現(xiàn)思路：

• 希爾排序主要通過(guò)對(duì)數(shù)據(jù)進(jìn)行分組實(shí)現(xiàn)快速排序；
• 根據(jù)設(shè)定的增量（gap）將數(shù)據(jù)分為gap個(gè)組（組數(shù)等于gap），再在每個(gè)分組中進(jìn)行局部排序；

假如有數(shù)組有10個(gè)數(shù)據(jù)，第1個(gè)數(shù)據(jù)為黑色，增量為5。那么第二個(gè)為黑色的數(shù)據(jù)index=5，第3個(gè)數(shù)據(jù)為黑色的數(shù)據(jù)index = 10（不存在）。所以黑色的數(shù)據(jù)每組只有2個(gè)，10 / 2 = 5一共可分5組，即組數(shù)等于增量gap。

• 排序之后，減小增量，繼續(xù)分組，再次進(jìn)行局部排序，直到增量gap=1為止。隨后只需進(jìn)行微調(diào)就可完成數(shù)組的排序；

具體過(guò)程如下：

• 排序之前的，儲(chǔ)存10個(gè)數(shù)據(jù)的原始數(shù)組為：

• 設(shè)初始增量gap = length / 2 = 5，即數(shù)組被分為了5組，如圖所示分別為：[8, 3]、[9, 5]、[1, 4]、[7, 6]、[2, 0]：

• 隨后分別在每組中對(duì)數(shù)據(jù)進(jìn)行局部排序，5組的順序如圖所示，變?yōu)椋篬3, 8]、[5, 9]、[1, 4]、[6, 7]、[0, 2]：

• 然后縮小增量gap = 5 / 2 = 2，即數(shù)組被分為了2組，如圖所示分別為：[3，1，0，9，7]、[5，6，8，4，2]：

• 隨后分別在每組中對(duì)數(shù)據(jù)進(jìn)行局部排序，兩組的順序如圖所示，變?yōu)椋篬0，1，3，7，9]、[2，4，5，6，8]：

• 然后然后縮小增量gap = 2 / 1 = 1，即數(shù)組被分為了1組，如圖所示為：[0，2，1，4，3，5，7，6，9，8]：

• 最后只需要對(duì)該組數(shù)據(jù)進(jìn)行插入排序即可完成整個(gè)數(shù)組的排序：

動(dòng)態(tài)過(guò)程：

圖中d表示增量gap。

增量的選擇：

• 原稿中希爾建議的初始間距為N / 2，比如對(duì)于N = 100的數(shù)組，增量序列為：50，25，12，6，3，1，可以發(fā)現(xiàn)不能整除時(shí)向下取整。
• Hibbard增量序列： 增量序列算法為：2^k - 1，即1，3，5，7… …等；這種情況的最壞復(fù)雜度為 O（N3/2）* ,平均復(fù)雜度為*O（N5/4） 但未被證明；
• Sedgewcik增量序列：

以下代碼實(shí)現(xiàn)中采用希爾排序原稿中建議的增量即N / 2 。

代碼實(shí)現(xiàn)：

      //希爾排序
      ArrayList.prototype.shellSort = function(){
        //1.獲取數(shù)組的長(zhǎng)度
        let length = this.array.length

        //2.初始化增量
        let gap = Math.floor(length / 2)

        //3.第一層循環(huán)：while循環(huán)(使gap不斷減小)
        while(gap >= 1 ){
          //4.第二層循環(huán)：以gap為增量，進(jìn)行分組，對(duì)分組進(jìn)行插入排序
          //重點(diǎn)為：將index = gap作為選中的第一個(gè)數(shù)據(jù)
          for(let i = gap; i < length; i++){
            let temp = this.array[i]
            let j = i
            //5.第三層循環(huán):尋找正確的插入位置
            while(this.array[j - gap] > temp && j > gap - 1){
              this.array[j] = this.array[j - gap]
              j -= gap
            }
          //6.將j位置的元素設(shè)置為temp
          this.array[j] = temp
          }

          gap = Math.floor(gap / 2)
        }
      }

這里解釋一下上述代碼中的三層循環(huán)：

• 第一層循環(huán)： while循環(huán)，控制gap遞減到1；
• 第二層循環(huán)： 分別取出根據(jù)g增量gap分成的gap組數(shù)據(jù)：將index = gap的數(shù)據(jù)作為選中的第一個(gè)數(shù)據(jù)，如下圖所示，gap=5，則index = gap的數(shù)據(jù)為3，index = gap - 1的數(shù)據(jù)為8，兩個(gè)數(shù)據(jù)為一組。隨后gap不斷加1右移，直到gap < length，此時(shí)實(shí)現(xiàn)了將數(shù)組分為5組。

• 第三層循環(huán)： 對(duì)每一組數(shù)據(jù)進(jìn)行插入排序；

測(cè)試代碼：

   //測(cè)試類(lèi)
    let list = new ArrayList()

    //插入元素
    list.insert(66)
    list.insert(88)
    list.insert(12)
    list.insert(87)
    list.insert(100)
    list.insert(5)
    list.insert(566)
    list.insert(23)
    // console.log(list);

    //驗(yàn)證希爾排序
    list.shellSort()
    console.log(list);

測(cè)試結(jié)果：

希爾排序的效率：

• 希爾排序的效率和增量有直接關(guān)系，即使使用原稿中的增量效率都高于簡(jiǎn)單排序。

5.快速排序

快速排序的介紹：

• 快速排序可以說(shuō)是目前所有排序算法中，最快的一種排序算法。當(dāng)然，沒(méi)有任何一種算法是在任意情況下都是最優(yōu)的。但是，大多數(shù)情況下快速排序是比較好的選擇。
• 快速排序其實(shí)是冒泡排序的升級(jí)版；

快速排序的核心思想是分而治之，先選出一個(gè)數(shù)據(jù)（比如65），將比其小的數(shù)據(jù)都放在它的左邊，將比它大的數(shù)據(jù)都放在它的右邊。這個(gè)數(shù)據(jù)稱(chēng)為樞紐

和冒泡排序的不同：

• 我們選擇的65可以一次性將它放在最正確的位置，之后就不需要做任何移動(dòng)；
• 而冒泡排序即使已經(jīng)找到最大值，也需要繼續(xù)移動(dòng)最大值，直到將它移動(dòng)到最右邊；

快速排序的樞紐：

• 第一種方案： 直接選擇第一個(gè)元素作為樞紐。但是，當(dāng)?shù)谝粋€(gè)元素就是最小值的情況下，效率不高；
• 第二種方案： 使用隨機(jī)數(shù)。隨機(jī)數(shù)本身十分消耗性能，不推薦；
• 優(yōu)秀的解決方法：取index為頭、中、位的三個(gè)數(shù)據(jù)排序后的中位數(shù)；如下圖所示，按下標(biāo)值取出的三個(gè)數(shù)據(jù)為：92，31，0，經(jīng)排序后變?yōu)椋?，31，92，取其中的中位數(shù)31作為樞紐（當(dāng)（length-1）/2不整除時(shí)可向下或向上取整）：

實(shí)現(xiàn)樞紐選擇：

//交換兩個(gè)位置的數(shù)據(jù)
let swap = function(arr, m, n){
    let temp  = arr[m]
    arr[m] = arr[n]
    arr[n] = temp
}

//快速排序
//1.選擇樞紐
let median = function(arr){
  //1.取出中間的位置
  let center = Math.floor(arr.length / 2)
  let right = arr.length - 1 
  let left = 0

  //2.判斷大小并進(jìn)行交換
  if (arr[left] > arr[center]) {
    swap(arr, left, center)
  }
  if (arr[center] > arr[right]){
    swap(arr, center, right)
  }
  if (arr[left] > arr[right]) {
    swap(arr, left, right)
  }
  //3.返回樞紐
  return center
}

數(shù)組經(jīng)過(guò)獲取樞紐函數(shù)操作之后，選出的3個(gè)下標(biāo)值對(duì)應(yīng)的數(shù)據(jù)位置變?yōu)椋?/p>

動(dòng)態(tài)過(guò)程：

快速排序代碼實(shí)現(xiàn)：

//2.快速排序
let QuickSort = function(arr){
  if (arr.length == 0) {
    return []
  }
  let center = median(arr)
  let c = arr.splice(center, 1)
  let l = []
  let r = []

  for (let i = 0; i < arr.length; i++) {
      if (arr[i] < c) {
        l.push(arr[i])
      }else{
        r.push(arr[i])
      }        
  }
  return QuickSort(l).concat(c, QuickSort(r))
}

算法的巧妙之處在于通過(guò):

QuickSort(l).concat(c, QuickSort(r))

遞歸調(diào)用QuickSort函數(shù)實(shí)現(xiàn)了樞紐Center左邊數(shù)據(jù)l和右邊數(shù)據(jù)r的排序；

測(cè)試代碼：

let arr = [0, 13, 81, 43, 31, 27, 56, 92]
console.log(QuickSort(arr));

測(cè)試結(jié)果

快速排序的效率：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-783849.html

• 快速排序最壞情況下的效率：每次選擇的樞紐都是最左邊或最右邊的數(shù)據(jù)，此時(shí)效率等同于冒泡排序，時(shí)間復(fù)雜度為O（n2）?？筛鶕?jù)不同的樞紐選擇避免這一情況；
• 快速排序的平均效率：為O（N*logN），雖然其他算法效率也可達(dá)到O（N*logN），但是其中快速排序是最好的。

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】JavaScript實(shí)現(xiàn)排序算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！