前端面试题

外观

常见排序怎么选？ ​

数据量小或几乎有序时，插入排序简单。需要稳定的 O(n log n) 用归并。平均很快、可以原地划分用快排。面试里把复杂度、稳不稳定、要不要额外空间说全，再写一种实现。

原理 ​

冒泡：相邻比较，把大的往后换，最坏 O(n²)，稳定。选择：每轮选最小的放到前面，不稳定，因为交换可能打乱相等元素的相对顺序。插入：把当前元素插进前面的有序区，几乎有序时很快，稳定。

归并：分成两半分别排序再合并。时间始终 O(n log n)，需要 O(n) 临时空间，稳定。

快排：选一个基准，分成小于和大于两边，再递归。平均 O(n log n)，最坏 O(n²)。随机基准或三分可以降低最坏情况的概率。不稳定。

js
function quickSort(list) {
  if (list.length < 2) return list.slice()
  const pivot = list[Math.floor(list.length / 2)]
  const left = list.filter((n) => n < pivot)
  const mid = list.filter((n) => n === pivot)
  const right = list.filter((n) => n > pivot)
  return [...quickSort(left), ...mid, ...quickSort(right)]
}

这份写法清楚，但过滤会多占空间，也不是原地快排。要求原地时再用左右指针交换。

JavaScript 引擎的 sort 不是某一种教科书算法，也不保证数字的默认顺序。比较函数要返回数字，并且保持一致，否则排序结果未定义。

追问 ​

稳定是什么意思？

相等元素排序后相对顺序不变。多关键字排序会先按次关键字排，再按主关键字做一次稳定排序。

前端什么时候自己写排序？

业务排序用 Array.prototype.sort。面试写快排或归并，是为了证明会分治。大列表的渲染成本通常大于排序成本。

易错点 ​

  • 默认 sort 把数字当字符串，[10, 2] 会排成 [10, 2]。
  • 快排基准固定取第一个，有序数组退化成 O(n²)。
  • 比较函数返回布尔值。sort 要的是负数、零或正数。

相关 ​