快速排序思想
最开始找出一个基准值，通过一趟排序将待排序的序列分割成独立的两个部分，前面的这一部分元素都比基准值小，后面这一部分的元素都比基准值大。然后分别再对两个部分的序列进行排序，以达到整个序列有序。
一个例子让你完全掌握快速排序
我们给定一个无序数组。定义临时变量temp存放基准值，定义左标志位定位至数组第一个元素，定义右标志位定位至数组最后一个元素。我们假定左标志位为基准值。
首先我们把左标志位的元素值5放入临时变量temp中。
然后比较基准值5与右标志位元素值8。右标志位的值大于基准值，满足排序条件，左移右标志位，继续与基准值比较。
右标志位元素4小于基准值5，把右标志位的值4赋予左标志位。
赋值后数组排序情况。
接下来右移左标志位，左标志位的值7与基准值5进行比较，左标志位的值7大于基准值5。
把左标志位的值7赋值给右标志位。
赋值后数组排序情况。
继续更改右标志位，左移右标志位，基准值5与右标志位1进行比较，右标志位的值1小于基准值5，把右标志位的值赋值给左标志位。
左标志位右移一位，基准值5与左标志位的值9进行比较，左标志位的值9大于基准值5。
把左标志位的值9赋值给右标志位。
右标志位左移一位，右标志位的值3与基准值5进行比较。
右标志位的值3小于基准值5，把右标志位的值赋值给左标志位。
左标志位右移一位，左标志位的值2与基准值5进行比较，左标志位的值2比基准值5小，符合排序条件，左标志位右移一位。
左标志位的值6继续与基准值5进行比较，左标志位的值6大于基准值5，把左标志位的值6赋值给右标志位。
右标志位左移一位，恰好左右标志位重合。
直接把基准值5赋值给左标志位。
可以看到在基准值5的左边部分，元素的数值都比基准值小，在基准值右边部分，元素的数值都比基准值大，我们已经把数组进行了初步排序。接下来继续重复对独立的左右部分采取同样的方法排序，即可把整个数组排序完毕。
快速排序算法
1. 定义临时变量存放基准值，定义左右标志位分别指向待排序序列开头和结尾元素，默认把左标志位的元素值作为基准值。
2. 循环遍历。右标志位的元素值与基准值进行比较，如果右标志位的元素值大于等于基准值，则左移右标志位，进行下一次比较；如果右标志位的元素值小于基准值，则说明此元素应该放到序列左半部分，把此值填入左标志位。
3. 循环遍历。左标志位的元素值与基准值进行比较，如果左标志位的元素值小于等于基准值，则右移左标志位，进行下一次比较；如果左标志位的元素值大于基准值，则说明此元素应该放到序列右半部分，把此值填入右标志位。
4. 当左右标志位指向同一个元素，则说明左半部分所有元素都比基准值小，右半部分所有元素都比基准值大。把基准值填入标志位，完成初步排序。
5. 对左右两个独立的部分分别重复上述过程，最后完成整个序列的排序。
## Java版快速排序代码
public void quickSort(int array[], int left, int right) {
// 当左边界小于右边界时执行循环
if (left < right) {
// 定义指针i、j和temp存放基准值
int i = left, j = right, temp = array[left];
// 当左标志位小于右标志位时
while (i < j) {
// 如果i没有越界 并且 右标志位的元素值大于等于基准值
while (i < j && array[j] >= temp)
// 说明右标志位的元素符合排序要求，左移右标志位
j--;
// 如果i没有越界 并且 右标志位的元素值小于基准值
if (i < j) {
// 把右标志位的元素值赋给左标志位
array[i] = array[j];
// 左标志位右移一位
i++;
}
// 如果i没有越界 并且 左标志位的元素值小于基准值
while (i < j && array[i] < temp)
// 说明左标志位的元素符合排序要求，右移左标志位
i++;
// 如果i没有越界 并且 左标志位的元素值大于等于基准值
if (i < j) {
// 把左标志位的元素值赋给右标志位
array[j] = array[i];
// 右标志位左移一位
j--;
}
}
// 把基准值放入序列
array[i] = temp;
// 对左半部分递归调用快速排序函数进行排序
quickSort(array, left, i - 1);
// 对右半部分递归调用快速排序函数进行排序
quickSort(array, i + 1, right);
}
}