[数据结构与算法]java快速排序

快速排序

基本原理：

? 1.首先设定一个分解值，通过该分解值将数组分成左右两部分；

? 2.将大于或等于分解值的数据放到数组的右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

? 3.然后，左边和右边数据可以独立排序，对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，依次右侧类似于左侧。重复上述过程。可以看出这是一个递归定义。

切分原理：

? 把一个数组切分成两个子数组的基本思想

? 1.找一个基准值，用两个指针分别指向数组的头部和尾部。

? 2.先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；

? 3.再从头部向尾部开始搜索一个比基准值大的值，搜索到即停止，并记录指针的位置；

? 4.交换当前左边指针和右边指针的位置

? 5.重复2,3,4步骤

public class Quick {
//    对a数组进行排序
    public static void sort(Comparable[] a){
    int lo=0;
    int hi=a.length-1;
    sort(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);//递归调用排序右子组的元素
    }
//    数组分界的方法
    public static int partition(Comparable[] a,int lo,int hi){
//        确定分界值
        Comparable 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;
                }
            }
//            判断left>=right,如果是，则扫描结束，即交换元素即可
            if (left>=right){
                   break;
            }else {
                exch(a,left,right);
            }
        }
        exch(a,lo,right);//交换分界值
        return -1;
    }
    private static Boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
}