五种排序

排序可以分为比较排序和非比较排序。比较排序是指在排序过程中，会将所有元素的值进行比较，将小的或者是大的按照一个规律进行“运动”，最终形成一个有序的数组；非比较排序是利用自然数本身递增的特点，记录待排序数组中的元素以及个数，按照自然数进行从小到大输出（该数组存在该自然数一次以上）。

冒泡排序

冒泡排序是比较排序的一种。在两个相邻元素之间进行两两比较，使得比较大的数不断上升到右边，就像是气泡，越往上冒越大，经过每个数字至少冒泡一次的比较，可以使得右边的数从大到小排列。

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;
}

选择排序

选择排序也是比较排序的一种。从数组第一个元素位置开始，每次将剩余最小的元素放到当前的位置上，这样经过数组长度次数的比较与元素选择，就可以将数组从小到大进行排序。

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;
}

插入排序

插入排序也是比较排序的一种。它的原理和平时生活里起扑克牌一样，每次拿到一张牌，将它插入后面比它大，前面比它小的位置上，每张牌都是如此，当牌拿完后，得到的就是一副从小到大的牌。

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;
}

快速排序

快速排序是比较排序的一种。它运用了分治的思想。每次选取数组的第一个作为数字基准，比基准小的排到基准左边，比基准大的，排到基准的右边，这样一来，基准的位置是唯一确定的。然后运用递归，将左边再次作为一个数组进行排序，选取基准，左右分开，不断递归。

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());
}

计数排序

计数排序是非比较排序，它是将所有的数组元素都记录，用数组元素值作为键，元素出现的次数作为值，存储在一个类似于键值对的map类型中，当遍历完后，存储数组中有该值，则将该值从小到大按照次数输出，这样就形成了一个有序的数组。

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;
}