TIP

js几种排序方法

快速排序

取数组中的一个值，相比较，比它小的放在一个数组，比它大的放在一个数组，重复以上操作。

  function fastSort(arr) {
      const l = arr.length;
      if(l < 2) return arr;
      const arr1 = [],
          arr2 = [];
      const x = arr.splice(Math.floor(l/2),1);
      arr.forEach(item => {
        if(item > x) {
          arr2.push(item);
        } else {
          arr1.push(item);
        }
      })
      // 递归
      return fastSort(arr1).concat(x, fastSort(arr2));
    }

冒泡排序

从数组第一个值开始，与后面的值一一比较，前面的值大于后面的值，两者就交换位置。

  function bubbleSort(arr) {
    let l = arr.length;
    if(l <= 1) return arr;
    for(let i=0; i<l; i++) {
      // 一轮 最大值就排到最后去了
      for(let j=0; j<l-i-1; j++) {
        if(arr[j] > arr[j+1]) {
          let temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;
        }
      }
    } 
    return arr;
  }

选择排序

从第一个开始在后续元素中选出最小值，与其替换，一轮就排好一个

function selectSort(arr) {
  // 没有排序过的起始下标
  let minIndex = 0;
  for(let i=0; i< arr.length-1; i++) {
    // 最小值下标
    minIndex = i;
    for(let j=i+1; j<arr.length; j++) {
      if(arr[j] < arr[i]) {
        minIndex = j;
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
  return arr;
}

插入排序

从第一个元素开始，默认为已经被排序 取出下一个元素，在已经排序的序列中，从后往前，扫描，直到找到小于或等于该元素的位置

function insertSort(arr) {
  const len = arr.length;
  for(let i=1; i<len; i++) {
    let temp = arr[i];
    let j = i - 1; // 往前就是已排序的序列
    // j+1就是i
    while(j>=0 && arr[j] > temp) {
      [arr[j+1], arr[j]] = [arr[j], arr[j+1]];
      j--;
    }
  }
  return arr;
}

归并排序

function mergeSort(arr) {
  if(arr.length < 2) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  const merge = function(leftArr, rightArr) {
    let resultArr = [];
    while(leftArr.length && rightArr.length) {
      resultArr.push(leftArr[0] < rightArr[0] ? leftArr.shift() : rightArr.shift());
    }
    return [...resultArr, ...leftArr, ...rightArr];
  }
  return merge(mergeSort(left), mergeSort(right));
}