数组排序常见方式

冒泡排序

基本思路：将数组的每一项与后一项进行比较，如果前一项大于后一项就交换两者位置。

//冒泡排序
Array.prototype.bubleSort = function () {
  for (let i = this.length - 1; i >= 0; i--) {
    for (let j = 0; j < i; j++) {
      if (this[j] > this[j + 1]) {
          //交换函数
        swap.call(this, j, j + 1);
      }
    }
  }
};

优化版:

Array.prototype.bubleSort = function () {
  for (let i = this.length - 1; i >= 0; i--) {
  let b = false;
    for (let j = 0; j < i; j++) {
      if (this[j] > this[j + 1]) {
          //交换函数
        b = true;
        swap.call(this, j, j + 1);
      }
    }
  if(!b) return;//表示已经是有序的了，不用再交换
  }
};

选择排序

基本思路：从头开始，设置第一个数为最小数，保存其索引，将该数与后面的数进行比较，找到比该数更小的数就更新保存的索引，第一遍遍历完后，就交换第一个数与保存的索引数的位置。第二次从第二个数开始。遍历后交换第二数与最小数的索引对应数的位置。

Array.prototype.selectionSort = function () {
  let min = 0;
  for (let i = 0; i < this.length - 1; i++) {
    //初始最小数索引  
    min = i;
    for (let j = i + 1; j < this.length; j++) {
      if (this[min] > this[j]) {
        //更新最小数索引
        min = j;
      }
    }
    //遍历完后就交换索引  
    swap.call(this, i, min);
  }
};

插入排序

基本思路：首先将第一个元素看作有序，取出其后面一位的元素保存，将保存的元素与前面的有序元素比较，如果小于前面的有序元素就将前面的元素后移，如果移动后前面没有元素或者遇到了比自己小的元素就记录当前索引，并将保存的元素插入到这里，依次类推。

Array.prototype.insertSort = function () {
  let temp, j;
  for (let i = 1; i < this.length; i++) {
    //记录要将temp插入的位置
    temp = this[i];
    j = i;
    while (this[j - 1] > temp && j > 0) {
      this[j] = this[j - 1];
      j--;
    }
    this[j] = temp;
  }
};

图例：

第一次：将4与前面的6比较，小于将6向后移动，然后到头后将保存的4插入到第一个位置。

第二次：保存了2这个数，将这个数与前面的4，6这两个有序数进行比较，都小，就向后移动，到头后将2插入到第一个位置。
以此类推遍历。

希尔排序

思路与插入排序一样，可以把普通的插入排序看作间隔为1的希尔排序，希尔排序是每次遍历都会以不同的间隔进行插入排序，比如这里按照数组的1/2，1/4等来进行分组排序。

Array.prototype.hillSort = function () {
  let temp, j;
  const length = this.length;
  //增量
  let gap = Math.floor(length / 2);
  while (gap >= 1) {
    for (let i = gap; i < length; i += gap) {
      temp = this[i];
      j = i;
      while (this[j - gap] > temp && j > gap - 1) {
        this[j] = this[j - gap];
        j -= gap;
      }
      this[j] = temp;
    }
    gap = Math.floor(gap / 2);
  }
};

快速排序

基本思路：
首先找到一个枢纽，一般该枢纽获取方式是取数组的第一个，中间，最后一个数，取这三个数的中位数。

Array.prototype.quickSort = function (left, right) {
  //结束条件
  if (left >= right) return;
  //获取枢纽
  let pivot = this.media(left, right);
  let i = left;
  let j = right - 1;
  //交换操作
  while (i < j) {
    while (this[i] < pivot) {
      i++;
    }
    while (this[j] >= pivot) {
      j--;
    }
    //找到位置后交换
    if (i < j) {
      swap.call(this, i, j);
    }
  }
  //将枢纽  放置再正确的位置，之后枢纽左边都是小于枢纽的，枢纽右边都是大于枢纽的 
  swap.call(this, i, right - 1);
  //对枢纽左右边进行递归操作
  this.quickSort(left, i - 1);
  this.quickSort(i + 1, right);
};
//找枢纽位置函数
Array.prototype.media = function (left, right) {
  const center = Math.floor((left + right) / 2);
  if (this[left] > this[center]) {
    swap.call(this, left, center);
  }
  if (this[center] > this[right]) {
    swap.call(this, center, right);
  }
  if (this[left] > this[center]) {
    swap.call(this, left, center);
  }
  swap.call(this, center, right - 1);
  return this[right - 1];
};

图例：