排序算法

选择排序

Array.prototype.selection_sort = function() {
  let min;
  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;
      }
    }
    // 不用临时变量交换两个值
    if (min !== i) {
      this[min] = this[min] ^ this[i];
      this[i] = this[min] ^ this[i];
      this[min] = this[min] ^ this[i];
    }
  }
  return this;
};

快速排序

function quicksort(array) {
  if (array.length <= 1) {
    return array
  }
  let pivot = array[0]
  let left = []
  let right = []
  for (let i = 1; i < array.length; i++) {
    array[i] < pivot ? left.push(array[i]) : right.push(array[i])
  }
  return quicksort(left).concat(pivot, quicksort(right))
}

归并排序

function merge(left, right) {
  let result = [];
  while (left.length > 0 && right.length > 0) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  return result.concat(left).concat(right);
}

//拆分
function mergeSort(arr) {
  if (arr.length == 1) {
    return arr;
  }
  let mid = Math.floor(arr.length / 2);
  let left_arr = arr.slice(0, mid);
  let right_arr = arr.slice(mid);

  return merge(mergeSort(left_arr), mergeSort(right_arr));
}