快速排序（基础版）
面试官：聊聊快速排序
快速排序，顾名思义，是一种排序速度非常快的排序方法，该算法之所以非常快，是因为高度优化的内部循环，该算法在实际应用中非常广泛。今天我们聊聊快速排序
排序思想
师傅，我听说山下的李公子武术高超，战无不胜，你知道他制胜的秘诀吗
一尘
慧能
快，天下武功，唯快不破
慧能
算法中也常常将速度列为非常重要的一个指标，排序算法中的快速排序也是因为它的快而出名
哦？什么是快速排序
一尘
慧能
快速排序是一种采用分治思想，在实践中通常运行较快一种排序算法，它的思路如下
对于一个无序数组（排序前先将数组随机打乱）
首先，任意选取一个元素（这里选择数组第一个元素），该元素称为中轴元素
然后将大于或者等于中轴元素的元素放在右边，小于或者等于中轴元素的元素放在左边
上面两个过程（选元素和调整位置）称为分割（partition）
然后对左右两个子数组分别按照同样的方法进行分割操作（递归进行）
一直递归分割到子数组只有一个或零个元素为止，此时整个数组有序
子数组是相对而言的
那这个分割操作是怎么进行的呢？
一尘
慧能
分割操作是快速排序的核心，有许多版本，今天给你先说一种常见的
首先，用两个变量 i 和 j 从数组两边开始向中间扫描，i 向右走，j 往左走
i 初始化为第一个元素的下标，j 初始化为最后一个元素的下标加 1
i 往右走，直到遇见比中轴元素大的（或等于）元素停止移动，j 向左走，直到遇到比中轴元素小的（或等于）的元素停止移动
此时，如果 i < j 则交换 i、j 所指向的元素
上图或等于是因为 i 指向的元素或 j 指向的元素可能与中轴元素相等
然后继续向右向左走，直到 i >= j 整个扫描停止
此时 i 对应元素的左边（不包含arr[i]）必定小于或等于5,j 对应元素的右边（不包含arr[j]）必定大于或等于5
交换中轴元素 5 与 arr[j]
分割完成
排序代码
哦，原来快排是这样的，终于对快排不陌生了
一尘
慧能
快排非常重要，写写快排代码练练手吧
这个...，一尘仔细想了一下，其实也不那么难
对数组arr[low...high]进行快速排序
首先进行分割操作，返回中轴元素下标 j，然后对左数组arr[low...j-1] 和 右数组arr[j+1...high]分别递归进行排序
什么时候递归终止？当然是数组大小为小于等于1（0或1）时
一尘很快写出了quickSort的代码
然后就是分割操作了，把上面的分割过程实现一下
i == high 和 j == low 这两个条件防止i、j 越界
一尘
一尘解释道
时间复杂度
慧能
看来编码能力提高了，那你分析一下时间复杂度吧
这个。。。，我试试
一尘
最坏情况
对于规模为N的数组
如果数组有序的话，此时是最坏情况，因为每次递归右子数组规模只比原数组减一，这样递归次数就会很多
每次分割后，数组都会被划分一个大小为0的子数组和原数组大小减一的子数组
设规模为排序规模为N的数组所花费的时间为T（N）
那么T（N）应该等于分割时所花的时间加上左右子数组所花的时间，而分割时会遍历整个数组，所花的时间为O（N）
则可以得到T(N)=T(0)+T(N-1)+O(N)
处理数组大小为0或1所花费的时间为：
T(0) = T(1) = 1
现在只需要算出T（N）即可
排序前先将数组随机打乱就是防止输入为有序数组而导致排序效率低下，随机打乱将这种可能性（有序）降为极低
最好情况
最好情况就是每次选到一个中轴元素刚好位于中间，此时两个子数组刚好是原数组的一半，那么
T（N）= 2*T（N/2）+O(N)
logN个等式推导请看：归并排序
平均情况
平均时间复杂度分析比较困难，分割操作后中轴元素会落在哪里（排序好的位置）？会落在数组的任意位置。假设是等概率落在了数组的任意位置
此时时间复杂度就是将所有可能情况加起来除以N
由数学归纳法可得：
T(N)=O(NlogN)
具体证明过程就不在此证明了，感兴趣的伙伴可参考《数据结构与算法分析》一书或其他资料
慧能
恩恩，不错
师傅，我看快排时间复杂度也是O(nlogn),并且最坏情况下可能为O（n^2）,为什么说它块呢？
一尘
慧能
快排之所以块，就是因为它高度优化的内部循环（分割），它既不像归并那样需要辅助数组来回复制元素，也不像堆排序无法利用缓存并且有许多无用的比较，并且最坏情况可以采用一些方法避免
哦，原来这样
一尘
关于时间复杂度可看：
稳定性
慧能
最后一个问题：稳定性
不是稳定的，因为在整个扫描结束时，中轴元素与arr[j]发生交换的时候，可能破坏稳定性
一尘
慧能
看来对快排基本的思路理解的不错
哦，好的
一尘
慧能
走，为师带你去学学李公子的武功
