快速排序在面试题中经常被问，总结一下。快速排序的思想是对冒泡排序的改进，并且使用了递归，它通过把待排序元素划分成左右两个子数组减少比较次数。它的核心算法是求分解值所在的索引。接下来我讲一下如何求索引值partition。 通常指定待排序数组的索引0处的元素为key，使用索引left和right遍历待排序区间，待排序区间是[lo,hi]，left初始化为lo，right初始化为hi+1，分别从右往左遍历找到比key小的元素，然后从左往右遍历，找到比key大的元素，判断此时left是否大于等于right，如果是，就结束当前循环，否则就交换这两个索引处的元素，当循环结束，交换key和索引right处...