day09-附属-快速排序（扩展）

代码
package test;

import java.util.Random;

public class QuickSort {

    public static void main(String[] args) {
        //定义一个数组
        int[] arr = new int[100000];
        Random random = new Random();
        //给数组元素赋值
        for (int i = 0; i < arr.length; i++) {
            //生成随机数
            arr[i] = random.nextInt();//如果不传递参数，随机数的范围是int范围
        }
        
        //排序之前记录时间
        long start = System.currentTimeMillis();//获取当前操作系统的时间，以毫秒值表示的
        //排序
        quickSort(arr, 0, arr.length - 1);
        //排序之后记录时间
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }
    
    public static void quickSort(int[] arr, int left, int right) {//left表示从左边哪个开始排，right表示排到哪个位置，left表示左边的索引位置，right表示右边的索引位置，left不能比right大
        //进行判断，如果左边索引比右边索引大，是不合法的，直接使用return结束这个方法
        if(left > right) {
            return;
        }
        //定义变量保存基准数
        int base = arr[left];
        //定义变量i，指向最左边
        int i = left;
        //定义变量j，指向最右边
        int j = right;
        
        //当i和j不相遇的时候，在循环中进行检索
        while( i != j) {
            //由j从右往左检索比基准数小的，如果检索到比基准数小的就停下
            //如果检索到比基准数大的或相等的，就继续检索
            while(arr[j] >= base && i < j) {
                j--; //j从右往左移动
            }
            //i从左往右检索
            while(arr[i] <= base && i < j) {
                i++; //i从左往右移动
            }
            
            //代码走到这，i停下了，j也停下了，然后交换i和j位置的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //如果上面while循环的条件不成立，会跳出这个循环，往下执行。
        //如果这个条件不成立，说明i和j相遇了
        //如果i和j相遇了，就交换基准数这个元素和相遇位置的元素。
        //把相遇位置的元素赋值给给基准数这个位置的元素
        arr[left] = arr[i];
        //把基准数赋值给相遇位置的元素
        arr[i] = base;
        
        //基准数在这里就归位了，左边的数字都比他小，右边的数字都比他大
        //排基准数的左边
        quickSort(arr, left, i - 1);
        //排基准数的右边
        quickSort(arr, j + 1, right);
        
    }
}
day09-附属-快速排序（扩展）

相关推荐
