排序算法主要针对的是数组，所以，在开始学习之前，我们先自己新建一种数据结构来方便我们的学习。

function ArrayData () {
  let ret = []
  this.times = 0  // 统计执行次数
  this.push = (item) => {
    ret.push(item)
  }
  this.toString = () => {
    return ret.join()
  }
}

const arr = [34, 11, 45, 22, 31, 99, 68, 54]

比较相邻两个数的大小，如果前面的数大于后面，则交换这两个数的位置。要排序n个数字，需要经历n-1次的遍历。

按照字面要求，我们写出来的代码是这样的

function ArrayData () {
    // ......
    this.bubbleSort = function () {
        let length = ret.length;
        for (let i = 0; i  ret[j + 1]) {
              [ret[j], ret[j + 1]] = [ret[j + 1], ret[j]]
            }
          }
        }
    }
}

let tmp = new ArrayData()
arr.forEach((item) => {
    tmp.push(item)
})
tmp.bubbleSort()
console.log(tmp.times)    //  56

显然这种简单粗暴的排序方式有很大的提升空间，比如，我们可以检测每次排序，如果顺序已经排列成功，就没必要执行之后的循环了。

function ArrayData () {
    // ......
    this.bubbleSort = function () {
        let length = ret.length;
        for (let i = 0; i  ret[j + 1]) {
              [ret[j], ret[j + 1]] = [ret[j + 1], ret[j]]
              change = true
            }
          }
          if (!change) {
            break
          }
        }
    }
}

let tmp = new ArrayData()
arr.forEach((item) => {
    tmp.push(item)
})
tmp.bubbleSort()
console.log(tmp.times)    //  21

其实还是有优化的空间的。举个例子，假设一共8个数，第一轮循环，会把最大的数冒泡排到第8位，第二轮循环，会把第二大的数排到第7位，所以，本轮循坏其实没必要考虑最后一位了。同理，下一轮循环就不需要考虑后两位。改进后的代码如下:

function ArrayData () {
    // ......
    this.bubbleSort = function () {
        let length = ret.length;
        for (let i = 0; i  ret[j + 1]) {
              [ret[j], ret[j + 1]] = [ret[j + 1], ret[j]]
              change = true
            }
          }
          if (!change) {
            break
          }
        }
    }
}

let tmp = new ArrayData()
arr.forEach((item) => {
    tmp.push(item)
})
tmp.bubbleSort()
console.log(tmp.times)    //  18

遍历数组，找出最小的数排在第一位，第二轮循环找出第二小的数放在第二位，以此类推。

function ArrayData () {
    // ......
  this.selectionSort = function () {
    let length = ret.length
    for (let i = 0; i  {
    tmp.push(item)
})
tmp.selectionSort()

把数组分成前后两部分，前面的一部分是排好序的，然后分别把后面一部分的数字插入到前面排好序的数组中。所以，刚开始时设定第一个元素为排好序的部分，分别把后面的数字插入进来。

function ArrayData () {
    // ......
  this.insertSort = function () {
    let length = ret.length
    let j
    for (let i = 1; i = 0 && ret[j] > currentNumber; j--) {
        ret[j + 1] = ret[j] 
      }
      ret[j + 1] = currentNumber 
    }
  }
}

let tmp = new ArrayData()
arr.forEach((item) => {
    tmp.push(item)
})
tmp.insertSort()

选一个数作为基准数，遍历数列，把比它
放到他前面，比他小的放到他后面，然后再对基准数前后的数列递归上述操作，直到数列长度为1。

function ArrayData () {
    // ......
    this.quickSort = function () {
        quick(ret, 0, ret.length - 1);

        function quick(array, left, right) {
          let index
          if (array.length > 1) {
            index = partition(array, left, right)
            if (left  index) {
              quick(array, index, right)
            }
          }
          return array
        }

        function partition(array, left, right) {
          let pivot = array[Math.floor((right + left) / 2)],
            i = left,
            j = right;
          while (i  pivot) {
              j--
            }
            if (i  {
  tmp.push(item)
})
tmp.quickSort()

一句话实现快速排序。选择第一个元素作为参考元素，利用filter把数组分成大于参考元素和小于参考元素的两个数组，并对这两个数组递归调用快排函数。

function quickSort(arr) {
  return arr.length  item  item > arr[0])))
}

希尔排序是把数组按下标的一定增量分组，对每组进行插入排，随着增量逐渐减少，每个数组的长度越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

function ArrayData () {
    // ......
  this.shellSort = function () {
    let length = ret.length
    for (let step = Math.floor(length / 2); step > 0; step = Math.floor(step / 2)) {
      for (let i = 0; i = 0 && ret[j] > currentNumber; j -= step) {
          ret[j + step] = ret[j]
        }
        ret[j + step] = currentNumber
      }
    }
  }
}

let tmp = new ArrayData()
arr.forEach((item) => {
  tmp.push(item)
})
tmp.shellSort()

归并排序采用分治的思想，将已有序的子序列合并，得到完全有序的序列。所以我们把数列分割成不超过两个元素的数组，然后将其合并。

function ArrayData () {
    // ......
  this.mergeSort = function () {
    ret = mergeSortFun(ret)

    function mergeSortFun(arr) {
      let length = arr.length
      if (length  {
  tmp.push(item)
})
tmp.mergeSort()