那些我们需要掌握的算法，了解一下？---排序

[hulin32]

在说算法前谈谈数据结构，其实好的数据结构算法可能就相当于写好一半了。最基本的数据结构可能应该是队列和栈了。由于这一系列的算法梳理会通过js来表达。所以我们的队列和栈就用js来实现了。而在js中，语言本身就实现了他们。

队列，先进先出

const queue = [];
queue.push(1);
queue.push(2);
queue.shift(); // 1
queue.shift(); // 2

栈，后进先出

const stack = [];
stack.push(1);
stack.push(2);
stack.pop(); // 2
stack.pop(); // 1

相对一些原生没有实现它们的语言来说会容易一些。

好的，开始今天的排序整理吧。

算法4里面讲了:选择排序，插入排序，希尔排序，归并排序，快速排序。

一些通用方法

function less(a, b) {
  return a < b;
}
function exch(arr, i, min) {
  const temp = arr[i];
  arr[i] = arr[min];
  arr[min] = temp;
}

选择排序

选择排序是最简单的排序。首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置。再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

function selectionSort(arr) {
  len = arr.length;
  for (let i = 0; i < len; i++) {
    let min = i;
    for (let j = i + 1; j < len; j++) {
      if (less(arr[j], arr[i])) {
        min = j;
      }
    }
    exch(arr, i, min);
  }
  return arr;
}

插入排序

遍历整个数组，拿当前索引位置的值与前一位置的值做比较，然后交换位置。然后缩小索引，继续之前的操作，直到遍历到最后一个索引。当前索引位置的左边都是排好序的，但它们的最终位置还不确定，为了给更小的元素腾出空间，它们可能会被移动。

function insert_sort(arr) {
  len = arr.length;
  for (let i = 0; i < len; i++) {
    for (let j = i; j > 0 && less(arr[j], arr[j - 1]); j--) {
      exch(arr, j, j - 1);
    }
  }
  return arr;
}

希尔排序

是对插入排序的改进，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

function shellSort(arr) {
  len = arr.length;
  let h = 1;
  while (h < len / 3) {
    h = 3 * h + 1;
  }
  while (h >= 1) {
    for (let i = h; i < len; i++) {
      for (let j = i; j >= h && less(arr[j], arr[j - h]); j -= h) {
        exch(arr, j, j - h);
      }
    }
    h = Math.floor(h / 3);
  }
  return arr;
}

归并排序

将数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。
原地归并的方法

function merge(arr, lo, mid, hi) {
  let i = lo;
  let j = mid + 1;
  const aux = [];
  for (let k = lo; k <= hi; k++) {
    aux[k] = arr[k];
  }
  for (let k = lo; k <= hi; k++) {
    if (i > mid) {
      arr[k] = aux[j++];
    } else if (j > hi) {
      arr[k] = aux[i++];
    } else if (less(aux[j], aux[i])) {
      arr[k] = aux[j++];
    } else {
      arr[k] = aux[i++];
    }
  }

  return arr;
}
// 自顶向下
function topToBottomSort(arr, lo, hi) {
  if (hi <= lo) return;
  const mid = lo + Math.floor((hi - lo) / 2);
  topToBottomSort(arr, lo, mid);
  topToBottomSort(arr, mid + 1, hi);
  return merge(arr, lo, mid, hi);
}
// 自底向上
function bottomToTopSort(arr) {
  const len = arr.length;
  const aux = [];
  for (let sz = 1; sz < arr.length; sz = sz + sz) {
    for (let lo = 0; lo < len - sz; lo += sz + sz) {
      merge(arr, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, len - 1));
    }
  }
  return arr;
}

快速排序

快速排序和归并排序比较类似都采用了分治的思想。

function partition(arr, lo, hi) {
  let i = lo;
  let j = hi + 1;
  const v = arr[lo];
  while (true) {
    while (less(arr[++i], v)) {
      if (i === hi) {
        break;
      }
    }

    while (less(v, arr[--j])) {
      if (j == lo) {
        break;
      }
    }
    if (i >= j) {
      break;
    }
    exch(arr, i, j);
  }
  exch(arr, lo, j);
  return j;
}

function quickSort(arr, lo, hi) {
  if (hi < lo) return;
  const j = partition(arr, lo, hi);
  quickSort(arr, lo, j - 1);
  quickSort(arr, j + 1, hi);
}

在算法4官网上看到一个比较好的算法可视化网站http://sorting.at/, 有兴趣的可以看看