7快速排序

P3232_排序_快速排序1

P3333_排序_快速排序2-原理

P3434_排序_快速排序3-图片讲解

P3535_排序_快速排序4

package test;

import sort.Quick;

import java.util.Arrays;

public class QuickTest {
    public static void main(String[] args) {
        Integer[] a= {6, 1, 2, 7, 9, 3, 4, 5, 8};
        Quick.sort(a);
        System.out.println(Arrays.toString(a));//{1, 2, 3, 4, 5, 6, 7, 8, 9}
    }
}

package sort;

public class Quick {

    /*
      比较v元素是否小于w元素
   */
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
//        如果v比w小，返回1
    }



    /*
   数组元素i和j交换位置
    */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    //对数组内的元素进行排序
//    调用它是对a数组中所有元素进行排序
    public static void sort(Comparable[] a) {
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);
    }

    //对数组a中从索引lo到索引hi之间的元素进行排序
    private static void sort(Comparable[] a, int lo, int hi) {
        //安全性校验
        if (hi<=lo){
            return;
        }

        //需要对数组中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(Comparable[] a, int lo, int hi) {
        //确定分界值
        Comparable key = a[lo];
        //定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left=lo;
        int right=hi+1;//指向最大索引处的下一个位置。

        //切分
        while(true){//因为不知道什么时候停下来，所以用死循环，然后通过条件来停下来。
            //先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止
            while(less(key,a[--right])){
//                如果key比a[]小，执行
//                如果right不等于low，继续循环，继续左移，所以可以实现从右往左扫描
                if (right==lo){
                    break;
                }
            }

            //再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止
            while(less(a[++left],key)){
                if (left==hi){
                    break;
                }
            }
            //判断 left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可
            if (left>=right){
                break;
            }else{
                exch(a,left,right);
            }
        }

        //交换分界值
        exch(a,lo,right);//把第一个元素(low)和右指针元素交换，交换后，right就是分界值

        return right;//返回分界值
    }
}

P3636_排序_快速排序5