排序算法

  /* 排序算法必备的调换方法 */
  function swap (array, a, b) {
    let swapValue = array[a];
    array[a] = array[b];
    array[b] = swapValue;
  }


  /* 冒泡排序 循环每次进行交换 */
  Array.prototype.bubbleSort = function () {
    let array = this;
    let length = array.length;
    for (let i = 0; i < length; i ++) {
      for (let j = 0; j < length - 1 - j; j ++) {
        if (array[i] > array[j + 1]) {
          swap(array, i , j + 1);
        }
      }
    }
  };


  /* 选择排序，每次选出最小值并放在第一位 */
  Array.prototype.selectionSort = function () {
    let array = this;
    let length = array.length, indexMin;
    // 默认第二项为最小项
    // 每次循环如果有项小于最小项则进行调换位置。
    // 每次将最小项调换到前面位置
    for (let i = 0; i < length - 1; i ++) {
      indexMin = 1;
      for (let j = i; j < length; j ++) {
        if (array[indexMin] > array[j]) {
          indexMin = j;
        }
      }
      if (i !== indexMin) {
        swap(array, i, indexMin);
      }
    }
  };


  /* 插入排序，将数组毎一项和前面的项进行对比，如果前面项比较大，便插入到前面项前  */
  Array.prototype.insertSort = function () {
    let array = this;
    let length = array.length, j, temp;
    for (let i = 0; i < length; i ++) {
      j = i;
      temp = array[i];
      // 第一项默认为有序
      // 前面项与当前项进行对比，如果当前项小于前面项中的一项，那么前面项的下标自增
      // 当前项插入到前面项中
      while (j > 0 && array[j - 1] > temp) {
        array[j] = array[j - 1];
        j --;
      }
      array[j] = temp;
    }
  };


  /* 归并排序，用得是分治算法，将大数组拆分成小数组 */
  Array.prototype.mergeSort = function () {
    let array = this;
    let merge = function (left, right) {
      let result = [], il = 0, ir = 0;
      // 拆分到最终之后每个数组只有一项，
      // 也就是说数组是有序的，
      // 这个时候再用新的空数组来添加他们。添加之后的数组也是有序的
      while (il < left.length && ir < right.length) {
        // 因为left和right都是有序的数组，所以这里可以直接根据下标来判断进行添加
        if (left[il] < right[ir]) {
          result.push(left[il ++])
        } else {
          result.push(right[ir ++])
        }
      }
      while (il < left.length) {
        result.push(left[il ++]);
      }
      while (ir < right.length) {
        result.push(right[ir ++]);
      }

      return result;
    };


    // 分治算法，将数组拆分成两项
    let mergeSortRec = function (array) {
      let length = array.length;
      if (length === 1) {
        return array;
      }
      // 寻找中点，拆分左右两个数组
      let mid = Math.floor(length / 2),
      left = array.slice(0, mid),
      right = array.slice(mid, length);
      // 左边或者右边继续拆分， 这里使用递归。
      return merge(mergeSortRec(left), mergeSortRec(right));
    };

    return mergeSortRec(array);
  };


  /* 快速排序。寻找基点拆分数组。然后再找基点拆分数组，直至每个数组只剩一个元素 */
  /* 最常用的排序算法，js内置sort在谷歌中就是用它实现的 */
  Array.prototype.quickSort = function () {
    let array = this;
    let partition = function (array, left, right) {
      let pivot = array[Math.floor((left + right) / 2 )],
      i = left,
      j = right;

      while (i <= j) {
        // 寻找左边大于基点值
        while (array[i] < pivot) {
          i++;
        }
        // 寻找右边大于基点值
        while (array[j] > pivot) {
          j --;
        }
        // 第一个小于基点和第一个大于基点的值进行交换，直至到比较到基点为止
        if (i <= j) {
          swap(array, i, j);
          i ++;
          j --;
        }
      }
      return i;
    };
    let quick = function (array, left, right) {
      let index;

      if (array.length <= 1) {
        return array;
      }
      // 这个时候传入的是整个数组
      index = partition(array, left, right);
      // index - 1 是为了去除基点， 然后排序基点左边， 递归至只剩每个数组只剩一个
      if (left < index - 1) {
        quick(array, left, index - 1);
      }
      // 排序基点右边，递归至只剩每个数组只剩一个
      if (index < right) {
        quick(array, index, right);
      }
    };
    return quick(array, 0, array.length - 1)
  };


  /* 堆排序 */
  Array.prototype.heapSort = function () {
    let array = this, heapSize = array.length;

    let buildHeap = function (array) {
      let heapSize = array.length;
      for (let i = Math.floor(heapSize / 2); i >= 0; i--) {
        heapify(array, heapSize, 0);
      }
    };

    let heapify = function (array, heapSize, i) {
      let left = i * 2 + 1,
      right = i * 2 + 2,
      largest = i;

      if (left < heapSize && array[left] > array[largest]) {
        largest = left;
      }
      if (right < heapSize && array[right] > array[largest]) {
        largest = right;
      }

      if (!largest !== i) {
        swap(array, i, largest);
        heapify(array, heapSize, largest);
      }

    };

    buildHeap(array);

    while (heapSize > 0) {
      heapSize --;
      swap(array, 0, heapSize);
      heapify(array, heapSize, 0);
    }

  };

  let arr =  [85, 24, 63, 45, 17, 31, 96, 50];
  console.log(arr.insertSort());