QuickSort

public static void quickSort(int[] a,int left,int right){
	int l = left;
    int r = right;
    while(l<r){
        int tar = a[l]; //Ñ¡Ò»¸ö»ù×¼
        while(l<r && a[r]> tar){//´ÓÓұ߿ªÊ¼£¬ÕÒÒ»¸öСÓÚtarµÄ
            r --;
        }
        if(l<r){//ÕÒµ½ÁË£¬·Åµ½µ±Ç°
            a[l++] = a[r];
        }
        while(l<r && a[l] < tar){//´Ó×ó±ß¿ªÊ¼£¬ÕÒÒ»¸ö´óÓÚtarµÄ
            l ++;
        }
        if(l< r){//ÕÒµ½ÁË£¬·Åµ½ÓÒÃæ
            a[r--] = a[l];
        }
    }
    a[r] = tar;
    quickSort(a,left,l-1);//µÝ¹é×ó±ß
    quickSort(a,l+1,right);//µÝ¹éÓÒ±ß
}

¶ÔÓÚT(n) = aT(n/b) + f(n):
f(n) < n^(logba) ,Ôò T(n) = O(n^(logba))
f(n) = n^(logba) ,Ôò T(n) = O(n^(logba) * logn)
f(n) > n^(logba) ,Ôò T(n) = O(f(n))