排序可以分為比較排序和非比較排序。比較排序是指在排序過程中，會將所有元素的值進行比較，將小的或者是大的按照一個規(guī)律進行“運動”，最終形成一個有序的數(shù)組；非比較排序是利用自然數(shù)本身遞增的特點，記錄待排序數(shù)組中的元素以及個數(shù)，按照自然數(shù)進行從小到大輸出（該數(shù)組存在該自然數(shù)一次以上）。

冒泡排序

冒泡排序是比較排序的一種。在兩個相鄰元素之間進行兩兩比較，使得比較大的數(shù)不斷上升到右邊，就像是氣泡，越往上冒越大，經(jīng)過每個數(shù)字至少冒泡一次的比較，可以使得右邊的數(shù)從大到小排列。

Bubble-Sort-3.png

Array.prototype.bubbleSort = function() {
  let len = this.length;
  let count = 0;
  
  if(len<2 || !this) {
    return this;
  }
  
  while(count < len-1) { 
    let swapFlag = false;
    for(var j=0;j<len-1;j++) {
      if(this[j] > this[j+1]) {
        var temp = this[j];
        this[j] = this[j+1];
        this[j+1] = temp;
        swapFlag = true;
      }
    }
    if(!swapFlag) break;
  }
  
  return this;
}

選擇排序

選擇排序也是比較排序的一種。從數(shù)組第一個元素位置開始，每次將剩余最小的元素放到當(dāng)前的位置上，這樣經(jīng)過數(shù)組長度次數(shù)的比較與元素選擇，就可以將數(shù)組從小到大進行排序。

selection sort.png

Array.prototype.selectSort = function() {
  let count = 0;
  
  while(count < this.length) {
    let minNum = this[count];
    let index = count;
    for(let i=count+1; i<this.length;i++) {
      if(this[i] <= minNum) {
        minNum = this[i];
        index = i;
      }
    }

    this[index] = this[count]; 
    this[count] = minNum;   
    count++;
  }
  
  return this;
}

插入排序

插入排序也是比較排序的一種。它的原理和平時生活里起撲克牌一樣，每次拿到一張牌，將它插入后面比它大，前面比它小的位置上，每張牌都是如此，當(dāng)牌拿完后，得到的就是一副從小到大的牌。

insertion-sort-algorithm.jpg

Array.prototype.insertSort = function() {  
  for(let count = 1;count < this.length; count++) {
    let minNum = this[count];
    let temp = count -1;

    while(temp > 0 && this[temp] > minNum) {
      this[temp+1] = this[temp];
      temp--;
    }

    this[temp+1] = minNum;
  }
  
  return this;
}

快速排序

快速排序是比較排序的一種。它運用了分治的思想。每次選取數(shù)組的第一個作為數(shù)字基準(zhǔn)，比基準(zhǔn)小的排到基準(zhǔn)左邊，比基準(zhǔn)大的，排到基準(zhǔn)的右邊，這樣一來，基準(zhǔn)的位置是唯一確定的。然后運用遞歸，將左邊再次作為一個數(shù)組進行排序，選取基準(zhǔn)，左右分開，不斷遞歸。

javascript-quicksort.jpg

Array.prototype.quickSort = function() {
  const len = this.length;
  if(len < 2) return this;
  let basic = this[0], left = [], right = [];
  
  for(let i =1;i<len; i++) {
    if(this[i] <= basic) {
     left.push(this[i]);
    }else {
      right.push(this[i]);
    }
  }
  return left.quickSort().concat(basic, right.quickSort());
}

計數(shù)排序

計數(shù)排序是非比較排序，它是將所有的數(shù)組元素都記錄，用數(shù)組元素值作為鍵，元素出現(xiàn)的次數(shù)作為值，存儲在一個類似于鍵值對的map類型中，當(dāng)遍歷完后，存儲數(shù)組中有該值，則將該值從小到大按照次數(shù)輸出，這樣就形成了一個有序的數(shù)組。

counting_sort_algorithm.png

Array.prototype.countSort = function() {
  const countArr = [];
  for(let i=0;i<this.length;i++) {
    if(countArr[this[i]]) {
      countArr[this[i]]++;
    }else {
      countArr[this[i]] = 1;
    }
  }

  const resultArr = [];
  for(let j =0;j<countArr.length;j++) {
    while(countArr[j]>0) {
      resultArr.push(j);
      countArr[j]--;
    }
  }
  return resultArr;
}