快速排序在面试题中经常被问，总结一下。
快速排序的思想是对冒泡排序的改进，并且使用了递归，它通过把待排序元素划分成左右两个子数组减少比较次数。它的核心算法是求分解值所在的索引。
接下来我讲一下如何求索引值partition。

通常指定待排序数组的索引 0 处的元素为 key，使用索引 left 和 right 遍历待排序区间，待排序区间是 [lo,hi]，left初始化为 lo，right初始化为 hi+1，分别从右往左遍历找到比 key 小的元素，然后从左往右遍历，找到比 key 大的元素，判断此时 left 是否大于等于 right，如果是，就结束当前循环，否则就交换这两个索引处的元素，当循环结束，交换 key 和索引 right 处的元素，返回索引 right。这个返回值就是 partition。

得到 partition 后，就可以递归调用当前的排序方法对左子组排序，在对右子组排序，由于是递归调用，所以最终所有元素都会有序。