快速排序的基本原理

指定一个数作为参照，将数组中小于等于该数的数置于左侧，大于该数的数置于右侧。随后对左右侧的数字进行同样的排序，递归直到整个数据变得有序。

实现方法

public class MySort {

    public static <T extends Comparable> void quickSort(T[] a) {
        __quickSort(a, 0, a.length-1);
    }

    private static <T extends Comparable> void __quickSort(T[] a, int start, int end) {
        if(start >= end)
            return;
        int i = start, j = end;
        T key = a[start];
        while (i < j) {

            while(i < j && a[j].compareTo(key) > 0){
                j--;
            }
            a[i] = a[j];
            while(i < j && a[i].compareTo(key) <= 0){
                i++;
            }
            a[j] = a[i];
        }
        a[i] = key;
        __quickSort(a, start, i-1);
        __quickSort(a, i+1, end);
    }
}