关于前端:前端排序简介

前言

首先分享下最近面试某鹅厂时遇到的一道题

// 输出正整数 n
// 输入一个最大值为 n 的无反复且乱序的正整数数组
// generateShuffledArray(5) => [1, 3, 5, 4, 2] or [2, 1, 4, 5, 3] 等等 

这种问题天然难不倒我😏，一行代码就搞定了

function generateShuffledArray(n) {return Array.from({ length: n}, (v, i) => i + 1).sort(() => Math.random() - 0.5);
};

过后感觉本人写的还挺优雅的，起初在某次机缘巧合下看到篇文章，大抵意思是通过这种 Math.random 写法的乱序形式是不稳固的，于是我本人尝试统计了下：

为了不便后果展现，这里应用数字 3 随机 10000 次演示

let result = {}
for (let i = 0; i < 1e4; i++) {const key = generateShuffledArray(3);
  result[key] ? result[key]++ : result[key] = 1;
}
console.table(result)

通过后果能够看到，的确有较大的概率会使下面写到的从新排序办法生效，大佬们诚不欺我。
查看 Chrome 的 V8 源码 得悉，sort 外部应用了一种插入排序和疾速排序的混合排序，当数组长度小于等于 10 时，应用插入排序就会失去上图中的后果（后续具体讲到插入排序再剖析 why）。

排序算法

因为前端对排序算法的要求不是很高，很多排序场景从设计上来说也不应该由前端实现，所以本文只举例最常见的冒泡排序还有 V8 中用到的插入排序和疾速排序这三种。

所有排序过程图片均来自网络，若有侵权请评论分割删除

冒泡排序

思维

相邻数据两两比拟，把较大的数据放到前面，就如同是气泡缓缓的浮出了水面一样。

图解

实现

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {for (let j = 0; j < len - 1 - i; j++) {if (arr[j] > arr[j+1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]]
    }
  }
  return arr;
}

插入排序

从第二个数据开始顺次插入到之前的有序数组中，就像打扑克一样将每次拿到的牌插入到正确的地位。

图解

实现

function insertionSort(arr) {for (let i = 1; i < arr.length; i++) {const target = arr[i];
    let j = i - 1
    for (; j >= 0; j--) {if (target < arr[j]) arr[j+1] = arr[j];
      else break;
    }
    arr[j+1] = target;
  }
  return arr;
}

为何在 Chrome 中偏向于应用插入排序而不是冒泡排序？它们的工夫复杂度都是 O(n²)，而且也都是稳固的。
因为插入排序是拿数据和有序数组比照，一旦满足条件不再持续比拟，而且冒泡排序每次都须要两头变量去交互数据。

疾速排序

思维

任意选取一个数据（示图中选用数组的第一个数，代码中选用数组的两头数）作为要害数据，而后将所有比它小的数都放到它后面，所有比它大的数都放到它前面，之后再递归排序两边的数据。

图解

实现

function quickSort(arr) {if (arr.length < 2) return arr;
  const pivotIndex = arr.length >> 1;
  const pivot = arr.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];
  for (const item of arr) {if (item < pivot) left.push(item);
    else right.push(item);
  }
  return [...quickSort(left), pivot, ...quickSort(right)];
};

如果认真看过上述源码的同学会发现，在 V8 中为了让算法工夫复杂度更贴近 O(nlogn)，选取要害数据时多做了一步，将头、中、尾三个数先比拟获得中位数，应用这个中位数作为要害数据。
因为疾速排序的最糟状况就是每次都将最大值或最小值作为要害数据，这样的话使得递归调用栈被拉到最长的 O(n)。

论断

看懂了上述的插入排序算法后，最后的问题也能迎刃而解了，最初一个数据在往前插入时有 50% 的概率是不动的，这也验证了截图里的后果（数字 3 在最初一位的概率高达 50%）。

graph TD
    A[1, 2, 3] -->|50%| B(1, 2, 3)
    A[1, 2, 3] -->|50%| C(2, 1, 3)
    B[1, 2, 3] -->|50%| D(1, 2, 3)
    B[1, 2, 3] -->|50%| E(1, 3, 2)
    C[2, 1, 3] -->|50%| F(2, 1, 3)
    C[2, 1, 3] -->|50%| G(2, 3, 1)
    D[1, 2, 3] -->|50%| H(1, 2, 3)
    D[1, 2, 3] -->|50%| I(2, 1, 3)
    E[1, 3, 2] -->|50%| J(1, 3, 2)
    E[1, 3, 2] -->|50%| K(3, 1, 2)
    F[2, 1, 3] -->|50%| L(2, 1, 3)
    F[2, 1, 3] -->|50%| M(1, 2, 3)
    G[2, 3, 1] -->|50%| N(2, 3, 1)
    G[2, 3, 1] -->|50%| O(3, 2, 1)

这里的推论与截图中理论后果有些出入，是因为 Chrome 在 70+ 版本 对排序算法有过改良，应用了二分插入排序。

引申

个别状况下用最后的写法就糊弄过来了，不会细究也不肯定能意识到这些小细节，如果想实现真正的 shuffle 算法其实也很简略，间接贴代码吧：

function generateShuffledArray(n) {const arr = Array.from({ length: n}, (v, i) => i + 1);
  const _arr = [];
  while (arr.length) {_arr.push(arr.splice(arr.length * Math.random(), 1)[0]);
  }
  return _arr;
};