二. 传统技法：排序

几种排序算法：冒泡 快排 归并 堆排序（堆排序被用在优先级算法上，在 react 的调度里就用的这个）。

1. 冒泡排序

  1. function sort_bubble(list) {
  2.     for (let j = list.length; j > 0; j --) {
  3.         for (let i = 0; i < j; i++) { // 每一轮都能把最大数移动到最右端
  4.             let tmp;
  5.             if (list[i] > list[i + 1])  {
  6.                 tmp = list[i];
  7.                 list[i] = list[i + 1];
  8.                 list[i + 1] = tmp;
  9.             }
  10.         }
  11.     }
  12.     return list;
  13. }
  15. console.log('排序结果：', sort_bubble(l));

缺点：无脑循环，即使顺序已经出来了，但仍然要排。

2. 快速排序

-> 据说是 冒泡的改进版

  1. function sort_fast(list) {
  2.     if (list.length <= 1) {
  3.         return list;
  4.     }
  5.     let pivot = list[list.length - 1];
  6.     let leftArr = [];
  7.     let rightArr = [];
  8.     for (let i = 0; i < list.length - 1; i ++) {
  9.         let tmp = list[i];
  10.         if (tmp < pivot) {
  11.             leftArr.push(tmp);
  12.         } else {
  13.             rightArr.push(tmp);
  14.         }
  15.     }
  16.     leftArr = sort_fast(leftArr);
  17.     rightArr = sort_fast(rightArr);
  19.     return [...leftArr, pivot, ...rightArr];
  20. }
  22. console.log('快速排序结果：', sort_fast(l));

关于快速和冒泡的论述：http://data.biancheng.net/view/117.html

3. 归并排序

尽早看视频的时候，听到对分治思想的阐述：英文是 divide and conque, 中文为分而治之！突然就想起来要怎么来写归并排序了。
归并排序的想法事实上非常的大胆，不同于一般算法过程，是一步一步的，我们要分为两个层次去看问题：
第一步，假设算法已经写完，直接调用虚拟api 实现整体架构；第二步实现那虚拟api，这里面虚拟 api 有两个：
sort 和 mergeSortedArrs 都是，实际过程我们先写哪个，答案是一起写完。

  1. // 归并排序 -> 分治思想的集合
  2. let arr = [4, 4, 5, 6, 1, 2];
  3. function sort(arr) {
  4.     if (arr.length <= 1) {
  5.         return arr;
  6.     }
  7.     let mid = arr.length >>> 1;
  8.     return mergeSortedArrs(sort(arr.slice(0, mid)), sort(arr.slice(mid))); // 分治思想的体现
  9. }
  10. function mergeSortedArrs(arr1, arr2) {
  11.     let result = [];
  12.     if (arr1.length === 0) {
  13.         result = arr2.slice(0);
  14.     }
  15.     if (arr2.length === 0) {
  16.         result = arr1.slice(0);
  17.     }
  19.     let i = 0;
  20.     let j = 0;
  21.     while((i < arr1.length) || (j < arr2.length)) {
  22.         if (i >= arr1.length) {
  23.             result = result.concat(arr2.slice(j));
  24.             break; // 这是 while 循环的出口
  25.         } else if (j >= arr2.length) {
  26.             result = result.concat(arr1.slice(i));
  27.             break; // 这是 while 循环的出口
  28.         }
  29.         let item1 = arr1[i];
  30.         let item2 = arr2[j];
  31.         if (item1 < item2) {
  32.             result.push(item1);
  33.             i++;
  34.         } else {
  35.             result.push(item2);
  36.             j++
  37.         }
  38.     }
  39.     return result;
  40. }
  42. // console.log('合并有序数组：', mergeSortedArrs([1,2,10], [4,5,6]));
  43. console.log('归并排序：', sort([8, 9, 1, 3, 10, 17]));