java版排序算法之快速排序

快速排序的思想

快速排序是通过切分的方式将大数组切分为左右两个子数组，分别对两个子数组进行递归的切分，当左右两个子数组都有序时整个数组便有序了。

代码实现

public class QuickSort{
    public static void sort(Comparable[] a){
        sort(a, 0, a.length-1);
    }
    public static  void sort(Comparable[] a, int low, int high){
        if(low >= high){return;}
        int j = partition(a，low, high); //切分元素
        sort(a, low, j);
        sort(a, j+1, high);
    }
}

partition方法

代码中最主要的部分为partition方法的实现，它提供了将数组中下标为low的元素放在正确的位置，即partition方法实现了a[low]左边的元素都比它小，右边的元素都比它大，每调用一次partition方法都可以将数组中的一个元素排定顺序。

partition代码实现

public static int partition(Comparable[] a, int low, int high){
    int i=low, j=high+1;
    Comparable val = a[low];
    while(true){
        //less方法用于判断第一个参数是否小于第二个参数
        while(less(a[++i], val) if(i == high) break;
        while(less(val, a[--j])) if(j == low) break;
        if(i >= j) break;
        exch(a, i, j);
    }
    exch(a, low, j); //交换数组a中下标为low和j的元素位置
    return j;
}