快速排序
题目
用 Javascript 实现快速排序，并说明时间复杂度。
思路
快速排序是基础算法之一，算法思路是固定的
- 找到中间位置 midValue
- 遍历数组，小于 midValue 放在 left ，大于 midValue 放在 right
- 继续递归，concat 拼接
splice 和 slice
代码实现时，获取 midValue 可以通过 splice 和 slice 两种方式
理论分析，slice 要优于 splice ，因为 splice 会修改原数组。
但实际性能测试发现两者接近。
但是，即便如此还是倾向于选择 slice —— 因为它不会改动原数组，类似于函数式编程
性能分析
快速排序 时间复杂度 O(n*logn) —— 有遍历，有二分
普通的排序算法（如冒泡排序）时间复杂度时 O(n^2)
答案
使用 slice 方案，参考 quick-sort.ts
划重点
- 排序算法（基本功）
- 二分法的时间复杂度
- 注意数组的操作（
splicevsslice）