数据结构与算法（Java篇）笔记--快速排序

//排序代码
public class Quick {
    /*
        对数组a中的元素进行排序
    */
    public static void sort(Integer[] a){
        int lo = 0;
        int hi = a.length - 1;
        sort(a, lo, hi);
    }
    /*
        对数组a中从lo到hi的元素进行排序
    */
    public static void sort(Integer[] a, int lo, int hi){
        // 做安全性校验
        if(hi <= lo){
            return;
        }
        //对a数组中，从lo到hi的元素进行切分
        int partition = partition(a, lo, hi);
        //对左边分组中的元素进行排序
        sort(a,lo,partition-1);
        //对右边分组中的元素进行排序
        sort(a,partition+1, hi);
    }
    //对数组a中，从索引lo到索引hi之间的元素进行分组，并返回分组界限对应的索引
    public static int partition(Integer[] a, int lo, int hi){
        Integer key = a[lo];//把最左边的元素当做基准值
        int left = lo;//定义一个左侧指针，初始指向最左边的元素
        int right = hi + 1;//定义一个右侧指针，初始指向最右侧的元素下一个位置
        //进行切分
        while(true){
            //先从右往左扫描，找到一个比基准值小的元素
            while(less(key, a[--right])){//循环停止，证明找到了一个比基准值小的元素
                if(right == lo){
                    break;//已经扫描到最左边了，无需继续扫描
                }
            }
            //再从左往右扫描，找一个比基准值大的元素
            while(less(a[++left], key)){//循环停止，证明找到了一个比基准值大的元素
                if(left == hi){
                    break;//已经扫描到了最右边了，无需继续扫描
                }
            }
            if(left >= right){
                //扫描完了所有元素，结束循环
                break;
            }else{
                //交换left和right索引处的元素
                exch(a,left,right);//right就是切分的界
            }
        }
        //交换最后rigth索引处和基准值所在的索引处的值
        exch(a, lo, right);
        return right; //right就是切分的界限
    }
    /*
    数组元素i和j交换位置
    */
    private static void exch(Integer[] a, int i, int j){
        Integer t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    /*
    比较v元素是否小于w元素
    */
    private static boolean less(Integer v, Integer w){
        return v.compareTo(w) < 0;
    }
}

//测试代码
public class Test {
    public static void main(String[] args) throws Exception {
        Integer[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 8};
        Quick.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}