大家好，我是IT修真院武漢分院第八期的學員莊引，一枚正直純潔善良的WEB前端程序員。
今天給大家分享一下，修真院官網(wǎng)JS任務(wù)11，深度思考中的知識點——常見的幾種排序方法？
1.背景介紹
在計算機科學與數(shù)學中，一個排序算法（英語：Sorting algorithm）是一種能將一串資料依照特定排序方式進行排列的一種算法。 最常用到的排序方式是數(shù)值順序以及字典順序。有效的排序算法在一些算法（例如搜尋算法與合并算法）中是重要的， 如此這些算法才能得到正確解答。 排序算法也用在處理文字資料以及產(chǎn)生人類可讀的輸出結(jié)果。 基本上，排序算法的輸出必須遵守下列兩個原則：
輸出結(jié)果為遞增序列（遞增是針對所需的排序順序而言）
輸出結(jié)果是原輸入的一種排列、或是重組
雖然排序算法是一個簡單的問題，但是從計算機科學發(fā)展以來，在此問題上已經(jīng)有大量的研究。 更多的新算法仍在不斷的被發(fā)明。
2.知識剖析
查找和排序算法是算法的入門知識，其經(jīng)典思想可以用于很多算法當中。因為其實現(xiàn)代碼較短，應(yīng)用較常見。 所以在面試中經(jīng)常會問到排序算法及其相關(guān)的問題。但萬變不離其宗，只要熟悉了思想，靈活運用也不是難事。 一般在面試中最?？嫉氖强焖倥判蚝蜌w并排序，并且經(jīng)常有面試官要求現(xiàn)場寫出這兩種排序的代碼。 對這兩種排序的代碼一定要信手拈來才行。還有插入排序、冒泡排序、堆排序、基數(shù)排序、桶排序等。
常見的幾種算法：
①冒泡算法
②選擇排序
③插入排序
④快速排序
3.常見問題
問題一:各種排序算法用JavaScript 如何實現(xiàn)?
問題二:各種排序算法的優(yōu)劣及其應(yīng)用?
4.解決方案
問題一:各種排序算法用JavaScript 如何實現(xiàn)?
問題二:各種排序算法的優(yōu)劣及其應(yīng)用?
4.解決方案
冒泡排序
冒泡排序（英語：Bubble Sort）是一種簡單的排序算法。它重復地走訪過要排序的數(shù)列，一次比較兩個元素， 如果他們的順序錯誤就把他們交換過來。走訪數(shù)列的工作是重復地進行直到?jīng)]有元素再需要交換， 也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢"浮"到數(shù)列的頂端。
冒泡排序演算法的運作如下：
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
針對所有的元素重復以上的步驟，除了最后一個。
持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
代碼實現(xiàn):

Array.prototype.bubbleSort = function () {
  var i, j, temp;
  for (i = 0; i < this.length - 1; i++)
      for (j = 0; j < this.length - 1 - i; j++)
          if (this[j] > this[j + 1]) {
              temp = this[j];
              this[j] = this[j + 1];
              this[j + 1] = temp;
          }
  return this;
};

var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70];//定義一個數(shù)組
num.bubbleSort();//數(shù)組調(diào)用冒泡排序算法

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理如下。 首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀?然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。 選擇排序的思想其實和冒泡排序有點類似，都是在一次排序后把最小的元素放到最前面。但是過程不同， 冒泡排序是通過相鄰的比較和交換。而選擇排序是通過對整體的選擇。

Array.prototype.selectionSort = function() {
   var i, j, min;
   var temp;
   for (i = 0; i < this.length - 1; i++) {
       min = i;
       for (j = i + 1; j < this.length; j++)
           if (this[min] > this[j])
               min = j;
       temp = this[min];
       this[min] = this[i];
       this[i] = temp;
   }
   return this;
};
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]; //定義一個數(shù)組
num.selectionSort(); //數(shù)組定義選擇排序算法

插入排序（英語：Insertion Sort）是一種簡單直觀的排序算法。它的 工作原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)， 在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。插入排序在實現(xiàn)上，通常采用in-place排序 （即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位， 為最新元素提供插入空間。
1.從第一個元素開始，該元素可以認為已經(jīng)被排序
2.取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
3.如果該元素（已排序）大于新元素，將該元素移到下一位置
4.將新元素插入到該位置后

Array.prototype.insertionSort = function () {
  for (var i = 1; i < this.length; i++) {
      var temp = this[i];
      var j = i - 1;
      //如果將賦值放到下一行的for循環(huán)內(nèi), 會導致在第13行出現(xiàn)j未聲明的錯誤
      for (; j >= 0 && this[j] > temp; j--) {
          this[j + 1] = this[j];
      }
      this[j + 1] = temp;
  }
  return this;
}
var num = [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70]; //定義一個數(shù)組

num.insertionSort(); //數(shù)組調(diào)用插入排序算法

快速排序
快速排序（英語：Quicksort），又稱劃分交換排序（partition-exchange sort）， 一種排序算法， 最早由東尼·霍爾提出。在平均狀況下，排序n個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較， 但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n)演算法更快， 因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來。 快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
步驟為：
從數(shù)列中挑出一個元素，稱為"基準"（pivot），
重新排序數(shù)列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（相同的數(shù)可以到任一邊）。在這個分割結(jié)束之后，該基準就處于數(shù)列的中間位置。這個稱為分割（partition）操作。
遞歸地（recursively）把小于基準值元素的子數(shù)列和大于基準值元素的子數(shù)列排序。
遞歸到最底部時，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個演算法一定會結(jié)束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。

Array.prototype.quickSort = function () {
   var len = this.length;
   if (len <= 1)
       return this.slice(0);
   var left = [];
   var right = [];
   var mid = [this[0]];
   for (var i = 1; i < len; i++)
       if (this[i] < mid[0])
           left.push(this[i]);
       else
           right.push(this[i]);
   return left.quickSort().concat(mid.concat(right.quickSort()));
};

var arr = [5, 3, 7, 4, 1, 9, 8, 6, 2];
arr = arr.quickSort();

5.編碼實戰(zhàn)
6.擴展思考
各種排序算法的時間復雜度和空間復雜度
算法優(yōu)劣評價術(shù)語
穩(wěn)定性:
穩(wěn)定：如果 a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面；
不穩(wěn)定：如果 a 原本在 b 的前面，而 a = b，排序之后 a 可能會出現(xiàn)在 b 的后面；
排序方式:
內(nèi)排序：所有排序操作都在內(nèi)存中完成，占用常數(shù)內(nèi)存，不占用額外內(nèi)存。
外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤中，而排序通過磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進行，占用額外內(nèi)存。
復雜度:
時間復雜度: 一個算法執(zhí)行所耗費的時間。
空間復雜度: 運行完一個程序所需內(nèi)存的大小。

7.參考文獻
參考一：JavaScript 排序算法匯總
8.更多討論
還有那些經(jīng)典排序算法?
常用的排序算法？_騰訊視頻
PPT鏈接：常用的排序算法

技能樹.IT修真院
“我們相信人人都可以成為一個工程師，現(xiàn)在開始，找個師兄，帶你入門，掌控自己學習的節(jié)奏，學習的路上不再迷?！薄?br> 這里是技能樹.IT修真院，成千上萬的師兄在這里找到了自己的學習路線，學習透明化，成長可見化，師兄1對1免費指導?？靵砼c我一起學習吧 ！
http://www.jnshu.com/login/1/86157900