视频理解
快排思想：
- 选定Pivot中心轴大于Pivot的放到Pivot右边小于Pivot的放到Pivot左边分别对Pivot的左右子序列重复以上操作（直到序列长度为 1）
阮一峰版本：https://www.cnblogs.com/hjx-blog/articles/9183453.html
选取数组中间位置为 pivot，两个容器 left=[]，right=[]。遍历数组，把小于 pivot 的放到 left 容器中；把大于 pivot 的放到 right 容器中哦。
基线条件：
当数组长度≤1，结束递归
递归操作：
- 找到 pivot从数组中删除pivot遍历数组，把小于pivot的放到left，大于pivot的放到right拼接 left，pivot，right
**返回值：**拼接后的数组
let arr = [49,38,65,97,76,13,27,49];
function quicksort(arr){
if(arr.length<=1) return arr;
let pivotIndex = Math.floor(arr.length/2);
let pivot = arr.splice(pivotIndex,1)[0];
let [left,right] = [[],[]];
for(let i=0;i
时间复杂度：应该也是 O(NlogN)
空间复杂度：O(N)。每次都要开辟 left，right 两个空间。
问题：生产环境中，每次都要开辟额外的内存空间，不可。
注意：arr.spice(从哪个索引开始删,删几个,替换1,替换2,....)
arr.spice() 方法会改变原数组
返回值是被删除的元素组成的数组！
快排面试版本：
function quickSort(arr,left,right){
if(left>=right) return;//递归的基线条件
let i=left,j=right;
pivot = arr[left];
while(i=pivot){//j从右向左寻找比pivot小的数
j--
}
while(i
时间复杂度：O(NlogN)。空间复杂度：原地交换，O(1)
快排复杂度
最优：O(NlogN)。每次取到的元素刚好可以平分整个数组。 参考：
时间复杂度：
T
[
n
]
=
2
T
[
n
/
2
]
+
f
(
n
)
T[n] = 2T[n/2] + f(n)
T[n]=2T[n/2]+f(n)
T[n/2] - 平分后，子数组所花费的时间复杂度；f(n) - 平分这个数组所花费的时间
第一次递归：
T
[
n
]
=
2
T
[
n
/
2
]
+
n
T[n] = 2T[n/2] + n
T[n]=2T[n/2]+n
第二次递归：
T
[
n
]
=
2
∗
2
(
T
[
n
/
4
]
+
n
/
2
)
+
f
(
n
)
T[n] = 2*2(T[n/4]+n/2) + f(n)
T[n]=2∗2(T[n/4]+n/2)+f(n) =
2
2
T
[
n
/
2
2
]
+
2
n
2^2T[n/{2^2}]+2n
22T[n/22]+2n
第三次递归：
2
3
T
[
n
/
2
3
]
+
3
n
2^3T[n/{2^3} ] + 3n
23T[n/23]+3n
第 m 次递归：
2
m
T
[
n
/
2
m
]
+
m
n
2^mT[n/{2^m} ] + mn
2mT[n/2m]+mn
到 T(1) 不能再分。所以
n
/
2
m
=
1
n/{2^m} =1
n/2m=1
m
=
l
o
g
n
m=logn
m=logn
T[n] = 2^m T[1] + mn ；其中m = logn;
= nT[1] + nlogn = n + nlogn；根据曲线图，nlogn 远大于 n，所以取 nlogn
最差：
O
(
N
2
)
O(N^2)
O(N2)。每次取到的 pivot 是数组中最大/最小那个元素。这种情况就是冒泡排序了，每次只能排好一个元素的顺序。
