常用排序算法

冒泡排序

1. 依次比较相邻的两个数，如果第一个比第二个小，不变。如果第一个比第二个大，调换顺序。一轮下来，最后一个是最大的数
2. 对除了最后一个之外的数重复第一步，直到只剩一个数

这种方式通过多次迭代数组来完成操作，不管是平均还是最坏的情况，都是具有二次时间复杂度。
尽管这个方式简单，但是在实际应用中，大多数情况下不切实际的：时间复杂度过高。

function bubbleSort(arr) {
  var len = arr.length;
  var i, j;
  for (i = 0; i < len; i++) {
    for (j = 0; j < len-i-1; j++) {  
      if (arr[j] > arr[j + 1]) // 两两之间进行比较
        swap(arr, j, j + 1);
    }
  }
  return arr;
}
function swap(arr, i, j) {
  [arr[i], arr[j]] = [arr[j], arr[i]]
}

选择排序

1. 找出最小的数，和第一个交换位置
2. 在剩下的数中，找出最二小的数，放在第二个
3. 依次类推，排出顺序

选择排序在所有的情况下都具有二次时间复杂度。

function selectionSort(arr) {
  var len = arr.length;
  var i, j, xmin;
  for(i = 0; i < len; i++) {
    xmin = i;   // 将当前值设为最小值
    for (j = i + 1; j < len; j++) {
      if(arr[j] < arr[xmin])
        xmin = j;  // 在后面找到更小的值
    }
    if(i != xmin)
      swap(arr, i, xmin) //将找到的更小值进行交换
  }
  return arr;
}

插入排序

1. 把数组分为[已排序]和[未排序]两部分,第一个数为[已排序]，其余为[未排序]
2. 从[未排序]抽出第一个数，和[已排序]部分比较，插入到合适的位置

该算法在平均和最坏的情况下具有二次时间复杂度。

function insertSort(arr) {
  var len = arr.length;
  var i, j, val;
  for (i = 0; i < len; i++) {
    val = arr[i];
    for (j = i - 1; j >= 0; j--) {
      if (arr[j] < val) break; // 找到可以放的位置即跳出
      arr[j + 1] = arr[j];
    }
    arr[j + 1 ] = val;
  }
  return arr;
}

归并排序

1. 不断将数组对半分，直到每个数组只有一个
2. 将分出来的部分重新合并
3. 合并的时候按顺序排列

function merge(left, right) {
  var res = [],
    i = 0,
    j = 0;
  // 合并两个数组（按照从小到大的顺序）
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      res.push(left[i++]);
    } else {
      res.push(right[j++]);
    }
  }
  // 数组拼接
  return res.concat(left.slice(i)).concat(right.slice(j));
}
function mergeSort(arr) {
  var len = arr.length;
  var i, j;
  // 不断拆分至只有一个数
  if(len <= 1) return arr;
  var mid = Math.floor(len/2);
  var left = arr.slice(0,mid),
    right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

快速排序

1. 以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边
2. 再按此方法对这两部分数据分别进行快速排序（递归进行）
3. 不能再分后退出递归，并重新将数组合并

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  const index = Math.floor(arr.length / 2)
  const temp = arr.splice(index, 1)[0]
  let left = []
  let right = []
  arr.forEach(item => {
    item <= temp ? left.push(item) : right.push(item)
  })
  return quickSort(left).concat([temp], quickSort(right))
}