面试——快速排序总结

优点：
增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较少的从后面直接移动到前面，减少了总的比较次数与移动交换次数

缺点：
最坏复杂度为O(n2)
不稳定

时间复杂度：
最好：O(nlog2n)
平均：O(nlog2n)
最坏：O(n2)

最好情况：
每次划分都把当前数组划分为长度相等的两个子数组
最坏情况：
每次划分都只让数组中的元素少1，此时复杂度为O(n2)

空间复杂度：
递归log2n次，每次消耗栈空间为常数，故空间复杂度为O(log2n)

稳定性：
当中枢元素与其他元素交换时可能会把前面元素的稳定性打乱，所以是不稳定的

优化：
1、随机下标或三数取中作为枢轴元素
2、划分的数组变小到一定程度时，改用插入排序