排序算法之：快速排序详解

/**
 * 快速排序：其核心思想是分而治之，并利用递归来进行排序。
 * 首先，（一般）是把数组最左边的数当为基准数（base），
 * 然后，从最右边（right）往左走，当碰到比基准数小的就停下，接着从最左边（left）往右走，当碰到比基准数大的就停下；  当两边都停下时，两边的数进行交换。
 * 紧接着，我们会发现当left等于right，就是二者相遇了，此时把最左边的基准数（base）和相遇位置的值进行交换。交换后，我们发现基准数左边的数都是小于基准数，右边的数都是大于基准数。
 * 最后，我们把一个集体划分成了若干子集，每个子集分别进行排序，此为分而治之，并利用递归的思想进行最后的排序。
 * 完毕！
 */

package com.wei.demo.Annotation;
 
import java.util.Arrays;
import java.util.Random;
 
/**
 * 快速排序：其核心思想是分而治之，并利用递归来进行排序。
 * 首先，（一般）是把数组最左边的数当为基准数（base），
 * 然后，从最右边（right）往左走，当碰到比基准数小的就停下，接着从最左边（left）往右走，当碰到比基准数大的就停下；
 *      此时最有两边都停下，然后两者进行交换。
 * 其次，我们会发现当left等于right，就是二者相遇了，此时把最左边的基准数（base）和相遇位置进行交换。
 *       此时我们发现交换后，基准数左边的都是小于基准数，右边都是大于基准数。
 * 最后，我们知道，我们把一个集体划分成了若干子集，每个子集分别进行排序，此为分而治之，并利用递归的思想进行最后的排序。
 * 完毕！
 */
public class QuickSort {
    public static void main(String[] args) {
 
//        int[] arr = {1,3,2,6,5,9,7,22,66,99,11,999,888};
//        quickSorts(arr,0,arr.length-1);
//        System.out.println(Arrays.toString(arr));
 
        //我们可以多弄一点数字，看一下所用时间
        int[] arr=new int[1000000];
        Random random=new Random();
        //给数组元素赋值
        for (int i = 0; i < arr.length; i++) {
            //生成随机数
            int num = random.nextInt();
            arr[i] = num;
 
        }
 
        //排序之前记录时间
        long start = System.currentTimeMillis();//获取当前系统时间
  System.out.println("开始执行时间："+start);
        //排序
        quickSorts(arr,0,arr.length-1);
        //排序之后的记录时间
        long end = System.currentTimeMillis();
        System.out.println("执行完后的时间："+end);
        System.out.println("总共耗时："+(end-start));
 
 
    }
 
    /**
     * 快速排序方法
     * @param arr 数组
     * @param left 数组最左边的位置
     * @param right 数组最右边的位置
     */
    public static void quickSorts(int[] arr,int left,int right){
        //left始终是小于right的，否则出错。
        if (left > right) {
            return ;
        }
        //定义基准数，按照刚才说的，一般是最左边的为base
        int base = arr[left];
        //然后定义从右边往左走的j变量；从左往右走的i变量
        int i = left;
        int j = right;
 
        //首先是第一轮交换，出现基数左边都小于基数，右边都大于基数
        while(i != j){//当i=j时，在中间相遇了，跳出循环，说明要交换基准数。不相等就一直走
            //当i不等于j时，先从数组右边开始，找比基准数小的就停下
            while(arr[j] > base && i < j){
                j--;//没有比基准数小的就往左走，有的haul就停止循环
            }
 
            //现在是从左往右，有比基准数大的就停止循环进行交换
           while (arr[i] < base && i < j){
                i++;
            }
 
            //当走到这里的时候，应该是i和j都停下来了，然后进行交换，实质是把小的放在左边，大的放在右边。
            if (i < j) {
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
        //当走到这里的时候，已经跳出循环了，说明i=j了，二者相遇了，
        // 所以要和一开始设定的最左边的基准数进行交换
        int temp1 = arr[i];
        arr[i] = base;
        base = temp1;
 
 
        //到这里，我们就可以看到基准数左边的数字都是小于基准数的，基准数右边的都是大于基准数的。
        //相当于基准数左边的可以重新看成一个集合，基准数右边的可以看成新的集合
        //所以分别利用递归的思想进行调用
        quickSorts(arr,left,i-1);//基准数左边的集合
        quickSorts(arr,j+1,right);//基准数右边的集合
    }
}