JavaScript 快速排序
快速排序
快速排序的基本思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据 都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码实现：
function quickSort(array, start, end) {
let length = array.length;
// 如果不是数组或者数组长度小于等于1，直接返回，不需要排序
if (!Array.isArray(array) || length <= 1 || start >= end) return;
let index = partition(array, start, end); // 将数组划分为两部分，并返回右部分的第一个元素的索引值
quickSort(array, start, index - 1); // 递归排序左半部分
quickSort(array, index + 1, end); // 递归排序右半部分
}
function partition(array, start, end) {
let pivot = array[start]; // 取第一个值为枢纽值，获取枢纽值的大小
// 当 start 等于 end 指针时结束循环
while (start < end) {
// 当 end 指针指向的值大等于枢纽值时，end 指针向前移动
while (array[end] >= pivot && start < end) {
end--;
}
// 将比枢纽值小的值交换到 start 位置
array[start] = array[end];
// 移动 start 值，当 start 指针指向的值小于枢纽值时，start 指针向后移动
while (array[start] < pivot && start < end) {
start++;
}
// 将比枢纽值大的值交换到 end 位置，进入下一次循环
array[end] = array[start];
}
// 将枢纽值交换到中间点
array[start] = pivot;
// 返回中间索引值
return start;
}
这一种方法是填空法，首先将第一个位置的数作为枢纽值，然后 end 指针向前移动，当遇到比枢纽值小的值或者 end 值 等于 start 值的时候停止，然后将这个值填入 start 的位置，然后 start 指针向后移动，当遇到比枢纽值大的值或者 start 值等于 end 值的时候停止，然后将这个值填入 end 的位置。反复循环这个过程，直到 start 的值等于 end 的 值为止。将一开始保留的枢纽值填入这个位置，此时枢纽值左边的值都比枢纽值小，枢纽值右边的值都比枢纽值大。然后在递 归左右两边的的序列。
当每次换分的结果为含 ⌊n/2⌋和 ⌈n/2⌉−1 个元素时，最好情况发生，此时递归的次数为 logn，然后每次划分的时间复杂 度为 O(n)，所以最优的时间复杂度为 O(nlogn)。一般来说只要每次换分都是常比例的划分，时间复杂度都为 O(nlogn)。
当每次换分的结果为 n-1 和 0 个元素时，最坏情况发生。划分操作的时间复杂度为 O(n)，递归的次数为 n-1，所以最坏 的时间复杂度为 O(n²)。所以当排序序列有序的时候，快速排序有可能被转换为冒泡排序。
快速排序的空间复杂度取决于递归的深度，所以最好的时候为 O(logn)，最坏的时候为 O(n)。
快速排序的平均时间复杂度为 O(nlogn) ，最坏时间复杂度为 O(n²) ，空间复杂度为 O(logn) ，不是稳定排序。
详细资料可以参考： 《图解排序算法(五)之快速排序——三数取中法》 《关于快速排序的四种写法》 《快速排序的时间和空间复杂度》 《快速排序最好，最坏，平均复杂度分析》 《快速排序算法的递归深度》
更多面试题
如果你想了解更多的前端面试题，可以查看本站的WEB前端面试题 ,这里基本包涵了市场上的所有前端方面的面试题，也有一些大公司的面试图，可以让你面试更加顺利。
| 面试题 | ||
|---|---|---|
| HTML | CSS | JavaScript |
| jQuery | Vue.js | React |
| 算法 | HTTP | Babel |
| BootStrap | Electron | Gulp |
| Node.js | 前端经验相关 | 前端综合 |
| Webpack | 微信小程序 | - |
这些题库还在更新中，如果你有不错的面试题库欢迎分享给我，我整理后放上来；人人为我，我为人人，互帮互助，共同提高，祝大家都拿到心仪的Offer！
