當(dāng)n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlog2n)的排序方法：快速排序客给、堆排序或歸并排序序用押。
是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)靶剑，快速排序的平均時(shí)間最短蜻拨；
快速排序采用的思想是分治思想池充。
快速排序是找出一個(gè)元素（理論上可以隨便找一個(gè)）作為基準(zhǔn)(pivot),然后對數(shù)組進(jìn)行分區(qū)操作,使基準(zhǔn)左邊元素的值都不大于基準(zhǔn)值,基準(zhǔn)右邊的元素值都不小于基準(zhǔn)值，如此作為基準(zhǔn)的元素調(diào)整到排序后的正確位置缎讼。遞歸快速排序收夸，將其他n-1個(gè)元素也調(diào)整到排序后的正確位置。最后每個(gè)元素都是在排序后的正確位置血崭，排序完成卧惜。所以快速排序算法的核心算法是分區(qū)操作，即如何調(diào)整基準(zhǔn)的位置以及調(diào)整返回基準(zhǔn)的最終位置以便分治遞歸功氨。
取兩個(gè)指針：低位i和高位j
pivotkey與最高位比較序苏，如果高位大手幢，則不交換值捷凄，高位指針下移j--，直到高位小于pivotkey為止围来，高位賦值給低位跺涤；
再將最低位與pivotkey比較，如果低位小监透，則不交換值桶错，低位指針上移i++，知道低位大于pivotkey為止胀蛮，低位賦值給高位院刁；
這兩個(gè)循環(huán)到低位與高位相遇（相等）時(shí)停止，并將pivotkey賦值給低位粪狼。至此退腥，得到第一次劃分，劃分出的左右兩組分別進(jìn)入劃分（遞歸）再榄，最終得到排序狡刘。
java實(shí)現(xiàn)：
private static void sort(int[] nums, int left, int right){
if(left < right){
int key = nums[left];
int low = left;
int high = right;
while(low < high){
while(low < high && nums[high] >= key){
high--;
}
nums[low] = nums[high];
while(low < high && nums[low] <= key){
low++;
}
nums[high] = nums[low];
}
nums[low] = key;
sort(nums, left, low-1);
sort(nums, low+1, right);
}
}
過程分析：
4,3,5,9,2,1 low=0,high=5,key=4
1,3,5,9,2,1 ? low=2,high=5 ??1,3,5,9,2,5
low=2,high=4? 1,3,2,9,2,5 ?low=3,high=4? 1,3,2,9,9,5
low=3,high=3? 1,3,2,9,9,5 ?1,3,2,9,9,5 ??
low = key 結(jié)束，key賦值給低位：1,3,2,[4],9,5?
[1,3,2] 和[9,5]分別進(jìn)行如上操作：[1,2,3][4][5,9]
快速排序的時(shí)間主要耗費(fèi)在劃分操作上困鸥，對長度為k的區(qū)間進(jìn)行劃分嗅蔬，共需k-1次關(guān)鍵字的比較。
最壞情況是每次劃分選取的基準(zhǔn)都是當(dāng)前無序區(qū)中關(guān)鍵字最小(或最大)的記錄疾就，劃分的結(jié)果是基準(zhǔn)左邊的子區(qū)間為空(或右邊的子區(qū)間為空)澜术，而劃分所得的另一個(gè)非空的子區(qū)間中記錄數(shù)目，僅僅比劃分前的無序區(qū)中記錄個(gè)數(shù)減少一個(gè)猬腰。時(shí)間復(fù)雜度為O(n*n)
在最好情況下鸟废，每次劃分所取的基準(zhǔn)都是當(dāng)前無序區(qū)的"中值"記錄，劃分的結(jié)果是基準(zhǔn)的左漆诽、右兩個(gè)無序子區(qū)間的長度大致相等侮攀÷嘀Γ總的關(guān)鍵字比較次數(shù)：O(nlgn)
盡管快速排序的最壞時(shí)間為O(n2)，但就平均性能而言兰英，它是基于關(guān)鍵字比較的內(nèi)部排序算法中速度最快者撇叁，快速排序亦因此而得名。它的平均時(shí)間復(fù)雜度為O(nlgn)畦贸。
