1. 快速排序的原理：
方法其实很简单：分别从初始序列"6 1 2 7 9 3 4 5 10 8"两端开始"探测"。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字"哨兵i"和"哨兵j"。刚开始的时候让哨兵i指向序列的最左边（即i = 1），指向数字6。让哨兵j指向序列的最右边（即j = 10），指向数字8。
首先哨兵j开始出动。因为此处设置的基准数是最左边的数（也就是），所以需要让哨兵 j 先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵 j 停在了数字5面前，哨兵 i 在了数字7面前。
现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：
6 1 2 5 9 3 4 7 10 8
到此，第一次交换结束。接下来开始哨兵 j 继续向左挪动（再友情提醒：每次必须是哨兵j先出发）。他发现了（比基准数6要小，满足要求）之后停了下来。哨兵 i 也继续向右挪动的，他发现了（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：
6 1 2 5 4 3 9 7 10 8
第二次交换结束，"探测"继续。哨兵 j 继续向左挪动，他发现了（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时 哨兵 i 和 哨兵 j 相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和进行交换。交换之后的序列如下：
3 1 2 5 4 6 9 7 10 8
到此第一轮"探测"真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。
OK，解释完毕。现在基准数6已经归位，它正好处在序列的第6位。此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是"3 1 2 5 4"，右边的序列是"9 7 10 8"。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。
- 现在先来处理6左边的序列：
左边的序列是"3 1 2 5 4"。请将这个序列以3为基准数进行调整，使得3左边的数都小于等于3，3右边的数都大于等于3。好了开始动笔吧
如果你模拟的没有错，调整完毕之后的序列的顺序应该是：
2 1 3 5 4
OK，现在3已经归位。
接下来需要处理3左边的序列"2 1"和右边的序列"5 4"。对序列"2 1"以2为基准数进行调整，处理完毕之后的序列为"1 2"，到此2已经归位。序列"1"只有一个数，也不需要进行任何处理。至此我们对序列"2 1"已全部处理完毕，得到序列是"1 2"。序列"5 4"的处理也仿照此方法，最后得到的序列如下：
1 2 3 4 5 6 9 7 10 8
- 对于序列"9 7 10 8"也模拟刚才的过程，直到不可拆分出新的子序列为止。
最终将会得到这样的序列，如下：
1 2 3 4 5 6 7 8 9 10
到此，排序完全结束。细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。
2. 快速排序算法Java实现：
（1）把数组拆分为两个子数组加上一个基准元素: 选取最后一个元素作为基准元素，index变量记录最近一个小于基准元素的元素所在的位置，初始化为start- 1，发现新的小于基准元素的元素，index加1。从第一个元素到倒数第二个元素，依次与基准元素比较，小于基准元素，index加1，交换位置index和当前位置的元素。循环结束之后index+1得到基准元素应该在的位置，交换index+1和最后一个元素。
（2）分别排序[start, index], 和[index+2, end]两个子数组
代码案例示例：
-->1. 先实现一个数组工具类。代码如下：
package com.himi.classisort.util;
public class ArrayUtils {
public static void printArray(int[] array) {
System.out.print("[");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
if (i < array.length - 1) {
System.out.print(", ");
}
}
System.out.println("]");
}
public static void exchangeElements(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
-->2. 快速排序的Java实现以及测试代码如下：
package com.himi.classisort;
import com.himi.classisort.util.ArrayUtils;
public class QuickSortDemo {
public static void main(String[] args) {
int[] array = new int[] {50, 10, 90, 30, 70, 40, 80, 60, 20};
System.out.println("快速排序之前的数组：");
ArrayUtils.printArray(array);
System.out.println();
System.out.println("快速排序之后的数组：");
Quicksort(array);
ArrayUtils.printArray(array);
}
/**
* 对数组array作快速排序
* @param array
*/
public static void Quicksort(int[] array) {
subQuicksort(array, 0, array.length - 1);
}
/**
* 对数组array的子数组序列array[start...end]作快速排序
* @param array
* @param start
* @param end
*/
public static void subQuicksort(int[] array, int start, int end) {
int pivot;
if(start < end) {
//将array[start...end]一分为二，算出枢轴值pivot
pivot = partition(array, start, end);
//对低子数组递归排序
subQuicksort(array, start, pivot-1);
//对高子数组递归排序
subQuicksort(array, pivot+1, end);
}
}
/**
* 交换数组array中的子数组的记录，使枢轴记录到位，并返回其所在位置
* partition作用：
* 将选取的pivotkey不断交换,将比它小的换到它的左边,比它大的换到它的右边
* 同时pivotkey也在不断交换中更改自己的位置，知道完全满足要求为止
*/
private static int partition(int[] array, int start, int end) {
int pivotkey;
//使用子数组的第一个记录作为枢轴记录
pivotkey = array[start];
//从子数组两端交替向中间扫面
while (start < end) {
while (start < end && array[end] >= pivotkey) {
end--;
}
//将比枢轴记录小的记录交换到低端
ArrayUtils.exchangeElements(array, start, end);
while (start < end && array[start] <= pivotkey) {
start++;
}
//将比枢轴记录大的记录交换到高端
ArrayUtils.exchangeElements(array, start, end);
}
//返回枢轴所在的位置
return start;
}
}
运行效果，如下：
