内容来自《Offer来了》
快速排序（Quick Sort）是对冒泡排序的一种改进，通过一趟排序将要排序的数据序列分成独立的两部分，，其中一部分的所有数据比另一部分的所有数据都要小，然后按此方法对两部分数据分别进行快速排序，整个排序过程递归进行，最终使整个数据序列变成有序的数据序列。
快速排序算法的原理是：选择一个关键值作为基准值（一般选择第1个元素为基准元素），将比基准值大的都放在右边的序列中，将比基准值小的都放在左边的序列中。具体的循环过程如下。
（1）从后向前比较，用基准值和最后一个值进行比较。如果比基准值小，则交换位置；如果比基准值大，则继续比较下一个值，直到找到第1个比基准值小的值才交换位置。
（2）在从后向前找到第1个比基准值小的值并交换位置后，从前向后开始比较。如果有比基准值大的，则交换位置；如果没有，则继续比较下一个，直到找到第1个比基准值大的值才交换位置。
（3）重复执行以上过程，直到从前向后比较的索引大于等于从后向前比较的索引，则结束一次循环。这时对于基准值来说，左右两边都是有序的数据序列。
（4）重复循环以上过程，分别比较左右两边的序列，直到整个数据序列有序。
如图5-5所示是对数组[6,9,5,7,8]进行快速排序。先以第1个元素6为基准值，从数组的最后一位从后向前比较（比较顺序为：8>6、7>6、5<6），找到第1个比6小的数据5，然后进行第1次位置交换，即将数据6（索引为0）和数据5（索引为2）交换位置，之后基准值6位于索引2处；接着从前向后比较（比较顺序为：5<6、9>6），找到第1个比6大的数据9，然后进行第2次位置交换，即将数据6（索引为2）和数据9（索引为1）交换位置，交换后6位于索引1处；这时高位和低位都在6处，第一次递归完成。在第一次递归完成后，基准值6前面的数据都比6小，基准值6后面的数据都比6大。重复执行上述过程，直到整个数组有序。
5.4.2 快速排序算法的Java实现
快速排序算法的Java实现如下：