快速排序

快速排序应用广泛。长度为N的数组和运行时间成正比NlogN

快速排序思想

快速排序是一种分治排序的思想。它讲一个数组分成两个子数组，将两部分独立排序

  package com.snail.basic;

public class Quick
{

    public static void sort(Comparable[] a){
        // 将数组打乱 StdRandom.shuffle(a)
        sort(a,0,a.length-1);
    }
    public static void sort(Comparable[] a, int low, int high){
        if(high<=low) return;
        int j = partnation(a,low,high);
        sort(a,low,j-1);
        sort(a,j+1,high);
    }
    public static int partnation(Comparable[] a,int low,int high){
        int i = low;
        int j = high;
        Comparable v = a[low];

        while (true){
            // 找出比他小的
            while (less(a[++i],v)){
                if(i == high) break;
            }
            // 找出比他大的
            while (less(v,a[--j])){
                if(j == low) break;
            }
            if(i>=j) break;
            exch(a,i,j);
        }
        // 请注意这个步骤
        exch(a,low,j);
        return j;
    }
    public static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    public static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i];
        a[j]=a[i];
        a[i]=t;
    }

}

partition 让数组具备三个条件

1. 对于某个j，a[j]是已经排定的
2. a[0]~a[j] 之间的元素小于a[j],
3. a[j]~a[a.length-1]之间的元素都大于a[j]