快速排序的时间复杂度为 O(n2)
排序流程
1、首先设定一个分界值（比如数组最中间的元素），通过该分界值将数组分成左右两部分。
2、将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。
3、对左侧和右侧的数据按1和2的逻辑不断执行，直至排序完成。
代码范例 1 — 使用 splice
/** * 快速排序（使用 splice） * @param arr 原数组 * @returns 排序的数组 */ function quickSort1(arr) { let length = arr.length if (length <= 1) return arr const midIndex = Math.floor(length / 2) // 中间的 index const midValue = arr.splice(midIndex, 1)[0] // 中间的值。splice 会修改数组 const left = [] const right = [] // 注意这里使用 arr.length ，arr 被修改了 for (let i = 0; i < arr.length; i++) { const n = arr[i] if (n < midValue) { // 小于 midValue ，则放在左侧 left.push(n) } else { // 大于等于 midValue ，则放在右侧 right.push(n) } } return quickSort1(left).concat( [midValue], quickSort1(right) ) }
代码范例 2 — 使用 slice
/** * 快速排序（使用 slice） * @param arr 原数组 * @returns 排序的数组 */ function quickSort2(arr) { const length = arr.length if (length <= 1) return arr const midIndex = Math.floor(length / 2) // 中间的 index const midValue = arr.slice(midIndex, midIndex + 1)[0] // 中间的值。注意，使用 slice，原数组没有改动 const left = [] const right = [] for (let i = 0; i < length; i++) { if (i !== midIndex) { const n = arr[i] if (n < midValue) { // 小于 midValue ，则放在左侧 left.push(n) } else { // 大于等于 midValue ，则放在右侧 right.push(n) } } } return quickSort2(left).concat( [midValue], quickSort2(right) ) }
