摘要：今天我們來討論的問題有兩個如何用實現(xiàn)選擇排序冒泡排序插入排序快速排序歸并排序堆排序?qū)ι傻娜f個隨機(jī)數(shù)進(jìn)行排序，各個排序算法的性能分析?？焖倥判蚩焖倥判蛩惴ɑ旧鲜敲嬖嚤乜寂判蛩惴ǎ彩莻髀勛詈糜玫乃惴?。

今天我們來討論的問題有兩個：

如何用JavaScript實現(xiàn)選擇排序、冒泡排序、插入排序、快速排序、歸并排序、堆排序；

對生成的10萬個隨機(jī)數(shù)進(jìn)行排序，各個排序算法的性能分析。

這里我們?nèi)坑脭?shù)組來存儲數(shù)據(jù)，首先創(chuàng)建一個類ArrayList。
其中屬性的說明如下：

array空數(shù)組--->用以存放數(shù)據(jù)

insert()方法--->往array中插入數(shù)據(jù)

swapItemInArray(n,m)方法--->將array中第n個元素和第m個元素交換位置

toString()方法--->將array數(shù)組轉(zhuǎn)換為字符串

originSort()方法--->JavaScript原生排序算法實現(xiàn)，在之后的性能比較中，我們會用到它

function ArrayList(){
  var array = []
  this.insert = function(item){
    array.push(item)
  }
  this.swapItemInArray = function(n,m){
    let temp = array[n]
    array[n] = array[m]
    array[m] = temp
  }
  this.toString = function(){
    return array.join()
  }
  this.originSort = function(){
    array.sort(function(a,b){
      return a-b
    })
  }
}

先來實現(xiàn)最簡單的選擇排序。
其思路是：對于有N個數(shù)字的數(shù)組，進(jìn)行N輪排序，在每一輪中，將最大的數(shù)找出，放到末尾。下一輪的時候再找出次大的數(shù)放到倒數(shù)第二位。
我們來為ArrayList類添加如下方法

  this.selectSort = function(){
    var self = this
    var len = array.length
    var maxIndex
    for (var i = 0; i < len; i++) {
      maxIndex = 0   //初始化最大數(shù)的位置
      for (var j = 0; j < len - i; j++) {
        if (array[maxIndex] < array[j]) {  //每一次都和之前的最大數(shù)比較
          maxIndex = j    //如果大于之前的最大數(shù)，則紀(jì)錄當(dāng)前數(shù)為最大數(shù)
        }
      }
      //第i輪結(jié)束后，將最大數(shù)放到數(shù)組倒數(shù)第i個
      self.swapItemInArray(maxIndex,len-i-1)  
    }
  }

選擇排序是不是太簡單了？接下來我們就來實現(xiàn)冒泡排序。
思路：對于有N個數(shù)字的數(shù)組，進(jìn)行N輪排序，在每一輪中，從前往后以此比較兩兩相鄰的數(shù)字，每次比較后，都把大的往后放，一輪下來，最大的數(shù)會被推到數(shù)組最后。

  this.bubbleSort = function(){
    var self = this
    var len = array.length
    for (var i = 0; i < len; i++) {     //數(shù)組長度要遍歷的趟數(shù)
     //第i趟之后，后面i個元素都不用比較
      for (var j = 0; j < len - 1 - i; j++) {     
        if (array[j]>array[j+1]) {  //兩兩相鄰進(jìn)行比較
          self.swapItemInArray(j,j+1)  //將較大的數(shù)字放到后面
        }
      }
    }
  }

插入排序的實現(xiàn)思路如下：
對于有N個數(shù)字的數(shù)組，進(jìn)行N輪排序

第一輪 將第2個數(shù)字與第1個數(shù)字比較，如果第2個數(shù)字小，則與1交換

第二輪 將第3個數(shù)字與第2個數(shù)字比較
如果第3個數(shù)字小，則與第2個數(shù)字交換，再用第2個數(shù)字與第1個數(shù)字比較，將小的放前面。

第i輪 第1個到第i-1個數(shù)字已經(jīng)全是從小到大排列了，第i個數(shù)字與前面的數(shù)字依次比較并交換位置，使得第1個數(shù)字，到第i個數(shù)字也是從小到達(dá)排列。

代碼如下

  this.insertSort = function(){ 
    var self = this
    var len = array.length
    for (var i = 0; i < len; i++) {
      for (var j = i; j>0; j--) {
        if (array[j]
上面幾種排序的實現(xiàn)是不是很小兒科呢？下面的就要稍微復(fù)雜點(diǎn)了。
快速排序
快速排序算法基本上是面試必考排序算法，也是傳聞最好用的算法。
不過實現(xiàn)起來可一點(diǎn)都不容易，至少對我來說是這樣。
算法思想
本質(zhì)上快速排排序是一種分治算法的實際應(yīng)用。
按照下圖所示，對于左邊的原始數(shù)集合，（隨便地）取一個數(shù)（稱其為主元），比如取65為主元，則65則將原來的集合劃分為了A集合和B集合，A中所有的數(shù)字都小于65，B中所有的數(shù)字都大于65。
然后。
之后再對A集合和B集合采取相同方式的劃分。
最后就分為了從小到大排列的眾多小集合。

實現(xiàn)思路
對于有N個數(shù)字的數(shù)組，進(jìn)行大約logN輪的排序。
若每次都能劃分為兩等份，則效率最高。如果選擇的那個數(shù)將數(shù)組劃分為了1、N-1長度的兩個數(shù)組則效率會非常低。
因此，主元的選擇非常關(guān)鍵。不能用JavaScript中所提供的Math.random()獲得主元，由該函數(shù)生成隨機(jī)數(shù)代價昂貴。
根據(jù)相關(guān)資料，一個比較好的方法為：取首項、中間項、末尾項中的中值作為劃分基準(zhǔn)。
主元的具體實現(xiàn)函數(shù)如下
它傳入三個參數(shù)，數(shù)組本身、首項索引、尾項索引。
在查找中值的時候，順便將三個值分別排列成，首項最小、中位數(shù)中等、尾項最大。
為了方便后續(xù)的劃分，將主元和倒數(shù)第二個數(shù)進(jìn)行交換（由于尾項已經(jīng)大于中值，因此不必對其進(jìn)行操作，故主元放到倒數(shù)第二個）
    function findPivot(arr,left,right){//主元取中位數(shù)
      var center = Math.floor((left+right)/2)
      if (arr[left] > arr[center]) {
        self.swapItemInArray(left,center)
      }
      if (arr[left] > arr[right]) {
        self.swapItemInArray(left,right)
      }
      if (arr[center] > arr[right]) {
        self.swapItemInArray(center,right)
      }
      self.swapItemInArray(center,right-1)//主元被藏在倒數(shù)第二個
      return arr[right-1]
    }
每趟如何劃分?
以下圖為例，“9”為主元，我們把它放在最后一個。
這里設(shè)置i和j兩個指針（JavaScript中則是數(shù)組下標(biāo)），i指向首項“2”，j指向倒數(shù)第2個數(shù)字“7”。
讓i指針往右邊移動，遇到>=主元“9”的項時停下來
讓j指針往左邊移動，遇到<=主元“9”的項時停下來
交換i和j所指的值，并且i右移一位，j左移一位
i指針和j指針繼續(xù)移動比較交換
當(dāng)i與j發(fā)生交錯時，本趟劃分結(jié)束，把主元與i所指的“6”進(jìn)行交換（即把主元放回原位）。此時數(shù)組被劃分為了兩個[0,...,j]、[i+1,...,last]。[0,...,j]中的所有元素都小于主元，[i+1,...,last]中所有元素都大于主元。
對劃分出來的兩個子數(shù)組繼續(xù)進(jìn)行下一步劃分。

具體函數(shù)實現(xiàn)如下，由于數(shù)組長度太小時采用快速排序效率較低，因而當(dāng)數(shù)組長度太小時，我們改用插入排序。
    function partition(arr,left,right){ //分割操作
      var pivot = findPivot(arr,left,right) //找到主元
      var length = right - left
      if (length>cutoff) { //當(dāng)劃分組沒有小于閾值時，繼續(xù)采用快速排序
        var i = left
        var j = right - 2 
        while(i<=j){ //i和j沒有交錯
          while(arr[i]pivot){
            j--
          }
          if (i<=j) {
            self.swapItemInArray(i,j)
            i++
            j--
          }
        }
        self.swapItemInArray(i,right-1)  //結(jié)束后將主元放回原位
        if (left
快速排序的完整代碼
  this.quickSort = function(){
    var self = this
    var cutoff = 3

    function partition(arr,left,right){ //分割操作
      var pivot = findPivot(arr,left,right)
      var length = right - left
      if (length>cutoff) {
        var i = left
        var j = right - 2
        while(i<=j){
          while(arr[i]pivot){
            j--
          }
          if (i<=j) {
            self.swapItemInArray(i,j)
            i++
            j--
          }
        }
        self.swapItemInArray(i,right-1)
        if (left arr[center]) {
        self.swapItemInArray(left,center)
      }
      if (arr[left] > arr[right]) {
        self.swapItemInArray(left,right)
      }
      if (arr[center] > arr[right]) {
        self.swapItemInArray(center,right)
      }
      self.swapItemInArray(center,right-1)//主元被藏在倒數(shù)第二個
      return arr[right-1]
    }
    function insertSort(left,right){ //當(dāng)分塊足夠小的時候，用插入排序
      var len = right - left
      for (var i = 0; i <= len; i++) {
        for (var j = i; j > 0; j--) {
          if (array[j]
歸并排序
與快速排序的“在劃分中排序”不同，歸并排序的基本思想是先將長度為N的數(shù)組劃分為N個長度為1的數(shù)組，然后兩兩合并，在合并的時候排序。

如何在兩個子數(shù)組歸并的時候排序
如下圖，對于A數(shù)組和B數(shù)組，設(shè)置指針Aptr和指針Bptr，它們的初始位置都在倆數(shù)組的首部。
將Aptr和Bptr所指的數(shù)對比，將小的數(shù)放到C數(shù)組中。
比如Aptr所指“1”，Bptr所指“2”，Aptr所指的“1”小，則將“1”放入到C中，Aptr后移，Bptr不動。
再對比Aptr所指的“13”和Bptr所指的“2”，“2”較小，將其推入到C中，Bptr右移，Aptr不動。
反復(fù)重復(fù)上述操作，如果最后一個數(shù)組A空，另一個數(shù)組B還有剩余元素，則依次將數(shù)組B的剩余元素全部放到C中。
至此完成依次歸并操作。

代碼實現(xiàn)為
     function merge(arr1,arr2){
      var i = 0
      var j = 0
      var tempArr = []
      while(i
歸并排序的完整代碼如下，我們這里采用遞歸來實現(xiàn)劃分
  this.mergeSort = function(){
     function merge(arr1,arr2){
      var i = 0
      var j = 0
      var tempArr = []
      while(i
堆排序
最大堆是什么
最大堆是一個完全二叉樹。
但它還滿足，任意一個節(jié)點(diǎn)，它的值大于左子樹中的任意元素的值，也大于右子樹中的任意元素值。
該節(jié)點(diǎn)的左子樹元素的值和右子樹元素的值的大小沒有要求。

堆的數(shù)組表示
當(dāng)我們用數(shù)組(從0開始)來表示一個堆的時候，第i個元素的左子元素為第(2*i+1)個元素，右子元素為第(2i*2)個元素。
堆排序的大致思想
將數(shù)組按最大堆的方式排列，比如排列為[a,b,c,d]
將一個最大堆的根（a）和最后一個元素（d）交換，
把數(shù)組中除了最后一個數(shù)（a）以外的元素[d,b,c]重新調(diào)整為最大堆。
對[d,b,c]重復(fù)上述操作

如何創(chuàng)建最大堆
把所有元素插入到數(shù)組array（設(shè)長度為N）中后，從索引為(Math.floor(N/2) - 1)的元素開始，依次向前地將它和它的子樹調(diào)整為最大堆。
如下圖，先將子樹①調(diào)整為最大堆 ----> 調(diào)整子樹②為最大堆 ----> 調(diào)整整個樹③為最大堆

最大堆創(chuàng)建的代碼如下
    function createMaxHeap(){  //創(chuàng)建最大堆
      var len = array.length
      var startIndex = Math.floor(len/2) - 1 //從這個節(jié)點(diǎn)開始，將其子樹調(diào)整為最大堆
      for (var i = startIndex; i >= 0; i--) {
        compareChildAndAdjust(i)
      }
    }
    function compareChildAndAdjust(i,lastIndex){
      var bigChildIndex = findBigInChildren(i,lastIndex)
      if (bigChildIndex==false) {  //當(dāng)找到的子節(jié)點(diǎn)返回為false時，表示沒有子節(jié)點(diǎn)應(yīng)當(dāng)結(jié)束
        return
      }
      var parent = array[i]
      var bigChild = array[bigChildIndex]
      if (parent >= bigChild) {
        return
      }else{
        self.swapItemInArray(i,bigChildIndex)
        compareChildAndAdjust(bigChildIndex,lastIndex)//調(diào)整后要對子樹調(diào)整
      }
    }
    function findBigInChildren(i,lastIndex){
      var leftChild = array[2*i+1] //i節(jié)點(diǎn)的左子節(jié)點(diǎn)
      var rightChild = array[2*i+2] //i節(jié)點(diǎn)的右子節(jié)點(diǎn)
      if (lastIndex) {
        if (2*i+1 >= lastIndex) {
          return false
        }
        if (!(2*i+1 >= lastIndex) && (2*i+2 >= lastIndex)) {
          return 2*i+1
        }
      }
      if (!leftChild) {
        return false
      }
      if ( leftChild && !rightChild) {
        return 2*i+1
      }
      if (leftChild>rightChild) {
        return 2*i+1
      }else{
        return 2*i+2
      }
    }
堆排序的完整代碼如下
  this.heapSort = function(){
    var self = this
    createMaxHeap()
    swapMaxWithLast()
    function swapMaxWithLast(){
      var lastIndex = array.length - 1
      for (var i = lastIndex; i > 0; i--) {
        self.swapItemInArray(0,i)  //將根節(jié)點(diǎn)與最后一個節(jié)點(diǎn)交換
        //從根節(jié)點(diǎn)開始，與其子節(jié)點(diǎn)比較并重新形成最大堆
        //傳入的第二個參數(shù)表示，向下比較的時候，比到第i個節(jié)點(diǎn)之前停下來
        compareChildAndAdjust(0,i)  
      }
    }
    function createMaxHeap(){  //創(chuàng)建最大堆
      var len = array.length
      var startIndex = Math.floor(len/2) - 1 //從這個節(jié)點(diǎn)開始，將其子樹調(diào)整為最大堆

      for (var i = startIndex; i >= 0; i--) {
        compareChildAndAdjust(i)
      }
    }
    function compareChildAndAdjust(i,lastIndex){
      var bigChildIndex = findBigInChildren(i,lastIndex)
      if (bigChildIndex==false) {  //當(dāng)找到的子節(jié)點(diǎn)返回為false時，表示沒有子節(jié)點(diǎn)應(yīng)當(dāng)結(jié)束
        return
      }
      var parent = array[i]
      var bigChild = array[bigChildIndex]
      if (parent >= bigChild) {
        return
      }else{
        self.swapItemInArray(i,bigChildIndex)
        compareChildAndAdjust(bigChildIndex,lastIndex)//調(diào)整后要對子樹調(diào)整
      }
    }
    function findBigInChildren(i,lastIndex){
      var leftChild = array[2*i+1] //i節(jié)點(diǎn)的左子節(jié)點(diǎn)
      var rightChild = array[2*i+2] //i節(jié)點(diǎn)的右子節(jié)點(diǎn)
      if (lastIndex) {
        if (2*i+1 >= lastIndex) {
          return false
        }
        if (!(2*i+1 >= lastIndex) && (2*i+2 >= lastIndex)) {
          return 2*i+1
        }
      }
      if (!leftChild) {
        return false
      }
      if ( leftChild && !rightChild) {
        return 2*i+1
      }
      if (leftChild>rightChild) {
        return 2*i+1
      }else{
        return 2*i+2
      }
    }
  }
各種排序的速度性能
首先用一個函數(shù)來隨機(jī)生成10萬個數(shù)
    function createNonSortedArray(size){
      var array = new ArrayList()
      for (var i = size; i > 0; i--) {
        let num = Math.floor(1 + Math.random()*99)
        array.insert(num)
      }
      return array
    }
    var arr = createNonSortedArray(100000)
    //console.log(arr.toString()) //打印查看生成結(jié)果
接下來采用如下函數(shù)來計算排序時間
var start = (new Date).getTime()
//在這里調(diào)用arr的各種排序方法
//如 arr.quickSort()
var end = (new Date).getTime()
console.log(end-start)  //打印查看生成結(jié)果
//console.log(arr.toString()) //打印查看排序結(jié)果
數(shù)據(jù)結(jié)果如下

冒泡排序耗時26000ms左右

選擇排序耗時5800ms左右

插入排序耗時10600ms左右

歸并排序耗時80-100ms

快速排序
   cutoff==5--->30-50ms
   cutoff==10 --->30-60ms
   cutoff==50 ---->40-50ms
   cutoff==3效果不錯--->30-50ms，30ms出現(xiàn)的機(jī)會很多
   cutoff==0時（即不在分割長度短的時候轉(zhuǎn)為插入排序），效果依然不錯，30-50ms，30ms出現(xiàn)的很多

堆排序耗時120-140ms

JavaScript提供的原生排序耗時55-70ms


結(jié)論

快速排序效率最高，cutoff取3效果最好（沒有懸念）

原生排序竟然是第二快的排序算法！諸位同學(xué)參加筆試的時候，在沒有指明必須要用哪種排序算法的情況下，如果需要排個序，還是用原生的yourArr.sort(function(a,b){return a-b})吧，畢竟不易錯還特別快！


關(guān)于數(shù)據(jù)結(jié)構(gòu)和排序算法的學(xué)習(xí)建議
如果想了解數(shù)據(jù)結(jié)構(gòu)和排序算法的基礎(chǔ)理論知識，推薦中國大學(xué)mooc浙江大學(xué)陳越老師主講的《數(shù)據(jù)結(jié)構(gòu)》。該課程采用C語言講解，但仍然可以系統(tǒng)地學(xué)習(xí)到數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)思路。
你要是覺得本文文字描述難以理解，去聽或看該課程的動態(tài)圖片講解應(yīng)該會豁然開朗。
參考資料
《數(shù)據(jù)結(jié)構(gòu)》(第2版)，陳越，高等教育出版社
《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》[巴西]Loiane Groner，中國工信出版集團(tuán)，人民郵電出版社