1.png
    2.png
    3.png
    4.png
    5.png

    代码

    1. package test;
    3. import java.util.Random;
    5. public class QuickSort {
    7.     public static void main(String[] args) {
    8.         //定义一个数组
    9.         int[] arr = new int[100000];
    10.         Random random = new Random();
    11.         //给数组元素赋值
    12.         for (int i = 0; i < arr.length; i++) {
    13.             //生成随机数
    14.             arr[i] = random.nextInt();//如果不传递参数，随机数的范围是int范围
    15.         }
    17.         //排序之前记录时间
    18.         long start = System.currentTimeMillis();//获取当前操作系统的时间，以毫秒值表示的
    19.         //排序
    20.         quickSort(arr, 0, arr.length - 1);
    21.         //排序之后记录时间
    22.         long end = System.currentTimeMillis();
    23.         System.out.println(end - start);
    24.     }
    26.     public static void quickSort(int[] arr, int left, int right) {//left表示从左边哪个开始排，right表示排到哪个位置，left表示左边的索引位置，right表示右边的索引位置，left不能比right大
    27.         //进行判断，如果左边索引比右边索引大，是不合法的，直接使用return结束这个方法
    28.         if(left > right) {
    29.             return;
    30.         }
    31.         //定义变量保存基准数
    32.         int base = arr[left];
    33.         //定义变量i，指向最左边
    34.         int i = left;
    35.         //定义变量j，指向最右边
    36.         int j = right;
    38.         //当i和j不相遇的时候，在循环中进行检索
    39.         while( i != j) {
    40.             //由j从右往左检索比基准数小的，如果检索到比基准数小的就停下
    41.             //如果检索到比基准数大的或相等的，就继续检索
    42.             while(arr[j] >= base && i < j) {
    43.                 j--; //j从右往左移动
    44.             }
    45.             //i从左往右检索
    46.             while(arr[i] <= base && i < j) {
    47.                 i++; //i从左往右移动
    48.             }
    50.             //代码走到这，i停下了，j也停下了，然后交换i和j位置的元素
    51.             int temp = arr[i];
    52.             arr[i] = arr[j];
    53.             arr[j] = temp;
    54.         }
    55.         //如果上面while循环的条件不成立，会跳出这个循环，往下执行。
    56.         //如果这个条件不成立，说明i和j相遇了
    57.         //如果i和j相遇了，就交换基准数这个元素和相遇位置的元素。
    58.         //把相遇位置的元素赋值给给基准数这个位置的元素
    59.         arr[left] = arr[i];
    60.         //把基准数赋值给相遇位置的元素
    61.         arr[i] = base;
    63.         //基准数在这里就归位了，左边的数字都比他小，右边的数字都比他大
    64.         //排基准数的左边
    65.         quickSort(arr, left, i - 1);
    66.         //排基准数的右边
    67.         quickSort(arr, j + 1, right);
    69.     }
    70. }