前言
数组快速排序（快排）也算是前端面试的经典入门问题了，作为一个前端程序员掌握快排技能也是必须滴~
数组快排是二分法原理的经典应用，不熟悉二分法的同学可以看看胡哥的另一篇文章二分查找的原理及实现。
快排的原理：
- 混乱数组
nums中，选取最中间的midIndex；
- 遍历数组
nums中的每一个元素，与中间值nums[midIndex]比较，如果大则放入右侧数组中right = []，如果小，则放入左侧数组中left = [];
- 针对
left和right数组再次调用排序函数，知道left、right数组长度为空;
- 将结果返回即可: [left的排序结果, nums[midIndex], right的排序结果]。
Up Code ~ 上代码 ~
/** * @method quickSort * @description 数组排序 - 快排、二分法 * @param nums number[] * @returns number[] */ function quickSort(nums: number[]): number[] { // 获取数组的长度 const len = nums.length; // 临界点判断，数组长度为0，直接返回 if (len === 0) { return []; } // 获取nums元素之间的中间索引midIndex const midIndex = Math.floor(len / 2); // 这里是向下取整 // 每次nums的中间值 const midValue = nums[midIndex]; // 定义left，专门接收所有 < midValue 的值 let left: number[] = []; // 定义right，专门接收所有 > midValue 的值 let right: number[] = []; // 遍历nums for (let i = 0; i < len; i++) { // 注意这里的处理 - 中间值直接跳过，后面拼接的时候直接用 if (i === midIndex) continue; // 比midValue大的右挪，放入right if (nums[i] > midValue) { right.push(nums[i]); } // 比midValue小于/等于的左挪，放入left if (nums[i] <= midValue) { left.push(nums[i]); } } // 做优化处理，left、right长度为1时，就没有必要继续向下处理了 if (left.length > 1) { left = quickSort(left); } if (right.length > 1) { right = quickSort(right); } // 拼接数组返回 return [ ...left, midValue, ...right ] }
功能测试：
const nums: number[] = [4, 2, 1, 9, 9, 8, 3, 5, 6, 7]; // 调用 const newNums = quickSort(nums); // 打印结果 console.log(nums); // [4, 2, 1, 9, 9, 8, 3, 5, 6, 7] console.log(newNums); // [1, 2, 3, 4, 5, 6, 7, 8, 9, 9]
快排的算法复杂度
空间复杂度：O(n)O(n)O(n)
时间复杂度：外层for循环O(n)O(n)O(n)，内部递归时都是二分之一处理
O(logn)O(logn)O(logn)，整体的时间复杂度是 O(nlogn)O(nlogn)O(nlogn)
