1. 根本思维
疾速排序的根本思维是基于分治法的。
- 在待排序数组中选取一个元素作为基准，假如以第一个元素为基准。
- 每趟排序都能确定基准的地位。找到基准在数组中最终寄存的地位。右边是所有比该元素小的值，左边是所有比该元素大的值。
- 而后再别离对右边和左边两局部递归排序。直到每局部只有一个元素时进行排序。
实用场景
只实用于 程序构造 （也就是数组），不能对链式构造排序。
工夫复杂度
均匀复杂度：O(nlogn)，最好复杂度：O(nlogn)，最坏复杂度：O(n^2)。
空间复杂度
空间复杂度 ：O(logn)
2. 代码实现（java）
public void sort(int[] array) { quickSort(array, 0, array.length - 1);}// 对区间是[low, high]的数组进行排序，一轮排完之后，确定了第一个元素的地位public void quickSort(int[] array, int low, int high) { if (low >= high) return; // 终止条件 // 找到第一个元素（阈值）在最终的排序数组中的地位 // 将区间 [0,len-1] 之间按阈值划分为 <阈值， >阈值 两局部 int pos = getPosition(array, low, high); quickSort(array, low, pos - 1); // 对 <阈值 的局部排序 quickSort(array, pos + 1, high); // 对 >阈值 的局部排序}public int getPosition(int[] array, int low, int high) { int tmp = array[low]; // 以第一个元素作为基准 while (low < high) { // 从后向前找到比基准小的数 while (low < high && array[high] >= tmp) high--; array[low] = array[high]; // 把array[high]移到后面 // 从前向后找到比基准大的数 while (low < high && array[low] <= tmp) low++; array[high] = array[low]; // 把array[low]移到前面 } array[low] = tmp; // 把基准放在最终的地位上 return low; // 返回最终的地位}3. 代码阐明
1）quickSort() 中会有两个参数 low 和 high ？？
因为在排序过程中，排序的数组的起始地位和终止地位是变动，而不是 0 到 (array.length-1) 不变的。
2）quickSort 终止条件为什么是 low >= high ，而不是 low > high ？？
当 low == high 时，表明，此时数组中只有一个元素。数组中只有一个元素时，它在最终排好序的数组中
地位是和以后地位一样的，不须要进行排序。
3）在 getPosition() 中为什么是 while (low < high) ，而不是 while (low <= high) ？？
当 low == high 时，也就是找到了基准最终在排好序的数组中的地位。所以，须要跳出循环，把最终地位返回。