简述
快速排序是属于交换排序的一种（冒泡排序也是）。是冒泡排序的一种改进。是不稳定的一种算法，因为假如出现了同样的数字，无法确定同样的数字出现的位置是否跟预测中的一样。比如，[2, 4, 5, 3, 7, 3]，排序后是[2, 3, 3, 4, 5, 7]，无法确保第一个3是原来的第一个位置上的3。
时间复杂度：
平均情况：O（n㏒₂n）
最坏情况：O（n²）
最好情况：O（n㏒₂n）
空间复杂度：O（n㏒₂n）
快速排序伪代码
quickSort(A, left, right)
if right < left
then
j = sort(A, left, right);
quickSort(A, left, j - 1);
quickSort(A, j-1, right);
end
sort(A, left, right)
x = a[left];
i = left;
j = right;
while (i < j)
do
while (j > i and A[j] >= x)
do
j--
A[i] = A[j];
while (i < j and A[i] <= x)
do
i++
A[j] = A[i];
A[j] = x;
return j;
算法的关键点在于，设置基准数（x），然后在一定范围内，将范围正确划分为小于基准数，基准数，大于基准数，这三部分，然后当范围足够小的时候，就是一个正确的排序的集合了。
const arr = [2, 5, 3, 8, 1, 7, 4, 9, 6, 0];
const quickSort = (arr) => {
const sort = (arr, left, right) => {
if (left >= right) {
return
}
let i = left, j = right;
let base = arr[i];
console.log(arr);
while(i < j) {
while ( j > i && arr[j] >= base) {
j--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= base) {
i++;
}
arr[j] = arr[i];
}
arr[j] = base;
sort(arr, left, j-1);
sort(arr, j+1, right);
};
let newArr = arr.slice();
sort(newArr, 0, newArr.length - 1)
};
quickSort(arr);
我们来分析一下:
while(i < j) 第一次循环，i = 0，j = 9， base = 2
//arr
[2, 5, 3, 8, 1, 7, 4, 9, 6, 0]
// while( j > i && arr[j] >= base)，结果是
[0, 5, 3, 8, 1, 7, 4, 9, 6, 0]
// arr[j]的结果赋予arr[i]，i = 0, j = 9, base = 2
// while (i < j && arr[i] <= base)，结果是
[0, 5, 3, 8, 1, 7, 4, 9, 6, 5]
// arr[i]的结果赋予arr[j], i = 1, j = 9, base = 2
while(i < j) 第二次循环，i = 1，j = 9， base = 2
// 上一次结果的arr
[0, 5, 3, 8, 1, 7, 4, 9, 6, 5]
// while( j > i && arr[j] >= base)，结果是
[0, 1, 3, 8, 1, 7, 4, 9, 6, 5]
// arr[j]的结果赋予arr[i]， i = 1, j = 4, base = 2
// while (i < j && arr[i] <= base)，结果是
[0, 1, 3, 8, 3, 7, 4, 9, 6, 5]
// arr[i]的结果赋予arr[j], i = 2, j = 4, base = 2
while(i < j) 第三次循环，i = 2，j = 4， base = 2
// 上一次结果的arr
[0, 1, 3, 8, 3, 7, 4, 9, 6, 5]
// while( j > i && arr[j] >= base)，结果是
[0, 1, 3, 8, 3, 7, 4, 9, 6, 5]
// arr[j]的结果赋予arr[i]， i = 2, j = 2, base = 2
// while (i < j && arr[i] <= base)，结果是
[0, 1, 3, 8, 3, 7, 4, 9, 6, 5]
// arr[i]的结果赋予arr[j], i = 2, j = 2, base = 2
// i > j 条件不成立， while(i < j) 循环结束
// 将arr[j]的值恢复为基准值，arr[j] = base
[0, 1, 2, 8, 3, 7, 4, 9, 6, 5]
所以第一次sort执行完毕，已经得到了已2为基准值的符合条件（小于基准值，基准值，大于基准值）的数组了，只需要将基准值左边跟基准值右边也递归一下，就能得到有序的数组了。判断结束的条件是left >= right。
如果基准值选到最小值，那么相当于一个长度为数组长度的冒泡排序操作，如果每一次都选到最小值，那么它的时间复杂度相当于冒泡排序，其实也就是冒泡排序，因为始终没有成功地进行分治，也就相当于总是整体地排序。同理，选到最大值也是一样。
