排序

直接插入排序

给出一队无序的元素时，将第一个元素看做是一个有序的队列，而后从第二个元素起，依次与前面的元素进行比较，直到找到一个小于他的值，才插入

希尔排序

缩小增量排序，直接插入排序的改进

将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序

最后一轮的增量一定是1

解决大数据的排序问题

简单选择排序

通过n-i(1 <= i <= n)次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录进行交换，当i = n时所有记录有序排列

本质就是每次选择出最小的元素进行交换

堆排序

1. 构建完全二叉树
2. 构建大根树/小根数
3. 将最根处与最后叶子结点交换，然后继续形成大根/小根
4. 一直重复

适用场景：快速找出最大/最小的前几个

冒泡排序

• 想象一下水下的气泡往上冒的过程

/**
 * 冒泡排序
 */
let arr = [8,3,24,45,33,23,41,54,33,22,7,7,4,9,0,110];
let sortedArr = [];
function chooseSort(arr) {
  if(arr.length == 0) {
    return
  }
  for (let i = 1, len = arr.length; i < len; i++) {
    if (arr[i] <= arr[0]) {
      let temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;
    }
  }
  sortedArr.push(arr.splice(0,1)[0]);
  chooseSort(arr);
}

快速排序（升级版的冒泡排序）

• 选定基准值
• 分区（小于基准值放左边，大于基准值放右边）；
• 对于左边与右边的分区递归进行分区（partition）；
• 第一次轮n次；第二次轮n-1次，，，联想到二叉树，树的高度越低效率就越高

/**
 * 快速排序
 */
console.time(2);
let arr = [8,3,24,45,33,23,41,54,33,22,7,7,4,9,0,110];
function quickSort(arr) {
  if(arr.length < 2) {
    return arr;
  }
  let basic = arr[0];
  let left = [];
  let right = [];
  for(let i = 1, len = arr.length; i < len; i++) {
    if(arr[i] < basic) {
      left.push(arr[i])
    }
    if(arr[i] >= basic) {
      right.push(arr[i])
    }
  }
  return quickSort(left).concat([basic]).concat(quickSort(right));
}
console.log(quickSort(arr));
console.timeEnd(2);

归并排序（分治法）

基数排序

• 快排优化

• 快速选择算法(只是想找排名第K个的元素)

当我们需要快速找到一个元素X，并且使得小于X的元素数量是K-1个时，那X就是我们要查找的排名第K位的元素了，可以用partition;

• 堆排序

• 其它趣味算法

• 红黑树

• 哈希表