快速排序（Quicksort）是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序实现步骤：
1. 从待排序元素序列中选取一个数作为基准（一般情况下我们会选取第一个数）。 2. 将比基准大的数全部放在基准右边，将比基准小的数全部放在基准左边。 3. 对左右区间重复执行第一步，第二步，直到每个区间只剩下一个数（递归实现）。
快速排序图文思路：
java代码实现快速排序：
import java.util.Arrays; public class Test { //一趟快速排序 //返回最终low = high 的索引 private static int partition(int[] array, int low, int high) { int tmp = array[low];//将第一个数据作为基准， while (low < high) { //在右边寻找比基准小的数，如果没找到，high-- while (low < high && array[high] >= tmp) { high--; } if (low > high) { break; } else { //如果找到了,将对应high下标的数据放在low下标的位置 array[low] = array[high]; } //在左边寻找比基准大的数据，如果没找到，low++ while (low < high && array[low] <= tmp) { low++; } if (low >= high) { break; } else { //如果找到了,将对应low下标的数据放在high下标的位置 array[high] = array[low]; } } //退出循环的时候基准在相应位置，基准左边的数据都比基准小，右边的数据都比基准大 //将基准放在low或者high的位置（此时low和high相等） array[low] = tmp;//array[high] = tmp; return low; } //一趟快速排序结束，使得对应基准左边的数据都比基准小，右边的数据都比基准大 //递归调用一趟快速排序,对基准两边的数据进行快速排序 //start:对应需要排序的数组最左边 //end:对应需要排序的数组最右边 private static void sort(int[] array, int start, int end) { //par:一趟快速排序得到的基准位置的索引 //对基准两边的数据进行快速排序 int par = partition(array, start, end); if (par > start + 1) { sort(array, start, par - 1); } if (par < end - 1) { sort(array, par + 1, end); } } public static void quickSort(int[] array) { //low:左边的对应的索引 int low = 0; //high:右边的对应的索引 int high = array.length - 1; sort(array, low, high); } public static void main(String[] args) { int[] array = {49, 38, 65, 97, 76, 13, 27, 49}; //输出排序前 System.out.println("排序前： " + Arrays.toString(array)); //进行快速排序 quickSort(array); //输出排序后 System.out.println("排序后： " + Arrays.toString(array)); } }测试用例：[49, 38, 65, 97, 76, 13, 27, 49]
运行结果：
排序前： [49,38,65,97,76,13,27,49] 排序后： [13,27,38,49,49,65,76,97]快速排序的时间复杂度：N*logN。 快速排序的空间复杂度：logN。 快速排序的稳定性：不稳定。
快速排序的优化：由于直接插入排序有个特点：越有序越快。所以在一定区间内使用直接插入排序会提高排序效率。
