public class A01QuickSort {

 　　public static void main(String[] args) {

 　　　　A01QuickSort quickSort = new A01QuickSort();

 　　　　// 测试快排的效率：

 　　　　//    int number = 1000000;

 　　　　//    int[] array = new int[number];

 　　　　//    for (int i = 0; i < array.length; i++) {

 　　　　//    array[i] = new Random().nextInt(number);

 　　　　//    }

 　　　　//配合后面的元素输出，测试快排是否排序准确：

 　　　　int[] array = new int[] {181,181,187,181};

 　　　　System.out.println("数组准备完毕~");

 　　　　long start = System.currentTimeMillis();

 　　　　quickSort.quickSort(array, 0, array.length - 1);

 　　　　long end = System.currentTimeMillis();

 　　　　System.out.println("quickSort 用时：" + (end - start));// 测试结果： 元素为5万个时：11毫秒。50万：66毫秒。100万：136毫秒

 　　　　//遍历输出数组元素：

 　　　　quickSort.traverseArray(array);

 　　}

 　　/**

 　　* 快排的实现

 　　* @param target

 　　* @param left

 　　* @param right

 　　*/

 　　public void quickSort(int[] target, int left, int right) {

 　　　　if (left >= right) {

 　　　　　　return;

 　　　　}

 　　　　int pivot = target[left];// 基准点

 　　　　int temp;

 　　　　int i = left;

 　　　　int j = right;//为什么要声明i和j，因为后面做迭代的时候还需要用到最初的left和right

 　　　　while (i < j) {//验证array数组至少有2个元素，才要做排序

 　　　　　　/**

 　　　　　　* 提问：

 　　　　　　* 为什么是 while里的判断，为什么是 “target[j] >= pivot”，而不是“target[j] > pivot”？？？

 　　　　　　* 答: 数组[181,181,187,181]，分别用上面两种while去测试：

 　　　　　　*    如果是">="时，因为 181 >= 181 成立，所以right就会从右往左移；

 　　　　　　*    如果是">"时，因为 181 > 181 成立，所以right就不会左移。

 　　　　　　* 重点！！！right或left，必须有一方得是移动的！！！否则程序就会进入死循环！！！

 　　　　　　*/

 　　　　　　// 如果right一直都大于或等于pivot，则继续走，直到找到比pivot小的：

 　　　　　　while (target[j] >= pivot && i < j) {

 　　　　　　　　j--;

 　　　　　　}

 　　　　　　// 如果left一直都小于等于pivot，则继续走，直到找到比pivot大的：

 　　　　　　while (target[i] <= pivot && i < j) {

 　　　　　　　　i++;

 　　　　　　}

 　　　　　　// 此时right < pivot, left > pivot，将i和j做交换：

 　　　　　　if (i < j) {//这里做判断是为了right到了left位置时，不用再将执行下面这三行代码了：

 　　　　　　　　temp = target[i];

 　　　　　　　　target[i] = target[j];

 　　　　　　　　target[j] = temp;

 　　　　　　}

 　　　　}

 　　　　// left和right相遇了：

 　　　　// ①将相遇点的元素和pivot做交换：

 　　　　target[left] = target[j];

 　　　　target[j] = pivot;

 　　　　// ②基准点两边的元素的分别再做排序：

 　　　　quickSort(target, left, j - 1);

 　　　　quickSort(target, j + 1, right);

 　　}

 　　//遍历数组

 　　public void traverseArray(int[] array) {

 　　　　for(int element : array) {

 　　　　　　System.out.println(element);

 　　　　}

 　　}

 }