時間複雜度
平均情況：O(nlgn)
最壞情況：O(n*n)，發生在當數據已經是排序狀態時快排算法的基本原理
1、從數據中選取一個值a[i]作為參考
2、以a[i] 為參考，將數據分成2部分：P1、P2，P1中的數據全部≤a[i]，P2中的數據全部＞a[i]，數據變為｛｛P1｝｛a[i]｝｛P2｝｝
3、將P1、P2重複上述步驟，直到各部分中只剩1個數據
4、數據完成升序排列
基本示例：
原始數據：
｛3，9，8，5，2，1，6｝
第1步：選取第1個數據：3
第2步：將數據分成2部分，左邊≤3，右邊大於>3：
｛2，1｝ ｛3｝ ｛9，8，5，6｝
第3步：將各部分重複以上步驟，直到每部分只剩1個數據：
｛2，1｝ => ｛1｝ ｛2｝ ｛9，8，5，6｝ => ｛8，5，6｝ ｛9｝=> ｛5，6｝ ｛8｝ ｛9｝=> ｛5｝ ｛6｝ ｛8｝ ｛9｝
第4步：數據完成升序排列：
｛1｝ ｛2｝ ｛3｝ ｛5｝ ｛6｝ ｛8｝ ｛9｝
程序中數據通常保存在數組中，以int類型的數組為例，可以將上面的步驟寫成一個quickSort函數原型：
quickSort(int begin, int end) { //begin為數組的第一個數據的索引值，end為數組的最後一個數據的索引值+1 //如果只有1個數據或0個數據，則程序返回if( begin == end || begin == (end-1) ) return; int p = in[begin];//p為選擇的參考數據，選擇第一個數據int a = begin +1; //a作為2部分數據分界線的索引值int b = a;//b為待比較的數據的索引值for( ; b < end; b++) {//將數組中的各個數據依次與參考數據進行比較if( in[b] < p) { //如果該數據<參考數據則將其移動到左邊if(a == b){a++; continue;} //如果該數據已經在左邊則不動int temp = in[a];//將數據移動到左邊in[a] = in[b]; in[b] = temp; a++;//將分界線右移} } in[begin] = in[a-1];//講參考值移動到2組數據中間in[a-1] = p; if( a-1 > begin){ // 如果左邊有數據則將其重複上述步驟quickSort(begin, a); } if( end-1 > a ) {// 如果右邊有數據則將其重複上述步驟quickSort(a, end); } return; // 如果無數據返回}算法優化
上面這個快速排序算法可以說是最基本的快速排序，因為它並沒有考慮任何輸入數據。但是，我們很容易發現這個算法的缺陷：這就是在我們輸入數據基本有序甚至完全有序的時候，這算法退化為冒泡排序，不再是O(nn)，而是O(n^2)了。
究其根源，在於我們的代碼實現中，每次只從數組第一個開始取。如果我們採用“三者取中”，即arr[low],arr[high],arr[（low+high）/2]三者的中值作為樞軸記錄，則可以大大提高快速排序在最壞情況下的性能。但是，我們仍然無法將它在數組有序情形下的性能提高到O(n)。還有一些方法可以不同程度地提高快速排序在最壞情況下的時間性能。
此外，快速排序需要一個遞歸棧，通常情況下這個棧不會很深，為log(n)級別。但是，如果每次劃分的兩個數組長度嚴重失衡，則為最壞情況，棧的深度將增加到O(n)。此時，由棧空間帶來的空間複雜度不可忽略。如果加上額外變量的開銷，這裡甚至可能達到恐怖的O(n^2)空間複雜度。所以，快速排序的最差空間複雜度不是一個定值，甚至可能不在一個級別。
為了解決這個問題，我們可以在每次劃分後比較兩端的長度，並先對短的序列進行排序（目的是先結束這些棧以釋放空間），可以將最大深度降回到O(n)級別。
這裡提出對快速排序的3點優化思路：
對於小數組，可以採用插入排序，避免遞歸調用。例如，當if(hi <= lo + M)時，就可以轉到插入排序。
採用子數組的一部分元素的中位數來切分數組。這樣做得到的切分更好，但代價是需要計算中位數。
如果數組中含有大量的重複元素，可以採用三向切分。將數組切分為三部分，分別對應於小於、等於和大於切分元素的數組元素。代碼實現如下：
private static void sort1(int[] a, int lo, int hi) { if (hi <= lo) return; int lt = lo, i = lo + 1, gt = hi; int v = a[lo]; while (i <= gt) { if (a[i] < v) { swap(a, lt++, i++); } else if (a[i] > v) { swap(a, i, gt--); } else { i++; } sort(a, lo, lt - 1); sort(a, gt + 1, hi); }}