排序算法

冒泡排序

相邻的两个元素依次比较，小的放在左边。

选择排序

从未排序序列中找到最大（小）值存放到已排序序列末尾。

插入排序

从已排序序列中找到小于或等于当前数的位置并插到其后。

希尔排序

归并排序

归并排序（merge sort）是创建在归并操作上的一种有效的排序算法。归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

递归方式

此方式不改变原数组。

function merge( left, right ) {
  const arr = [];

  const ll = left.length;
  const rl = right.length;

  let li = 0;
  let ri = 0;

  while ( li < ll && ri < rl ) {
    if ( left[li] <= right[ri] ) {
      arr.push(left[li++]);
    }
    else {
      arr.push(right[ri++]);
    }
  }

  while ( li < ll ) {
    arr.push(left[li++]);
  }

  while ( ri < rl ) {
    arr.push(right[ri++]);
  }

  return arr;
}

function mergeSort( arr ) {
  const len = arr.length;

  if ( len < 2 ) {
    return arr;
  }

  const mid = Math.floor(len / 2);

  return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
}

快速排序