基本思想
任取待排元素序列中的某個元素（例如第一個元素）作為基准，按照該元素的排序碼大小，將整個元素序列劃分為左右兩個子序列：左側子序列中所有元素的排序碼都小於基准元素的排序碼，右側子序列中所有元素的排序碼都大於或等於基准元素的排序碼，基准元素則排在這兩個子序列中間（這也是該元素最終安放的位置）。然後分別對這兩個子序列重復進行上述方法，直到所有的元素都排在相應的位置上為止。
代碼
private void quickSort(int[] a, int left, int right) {
if (left < right) {
int pivotpos = partition(a, left, right);
quickSort(a, left, pivotpos - 1);
quickSort(a, pivotpos + 1, right);
}
}
private int partition(int[] a, int low, int high) {
int temp = a[low];
while (low < high) {
while (low < high && temp <= a[high])
high--;
a[low] = a[high];
while (low < high && temp >= a[low])
low++;
a[high] = a[low];
}
a[low] = temp;
return low;
}
性能分析
快速排序的平均時間復雜度為O(nlog2n) 。就平均時間復雜度而言，快速排序是所有內部排序方法中最好的一個。由於快速排序是遞歸的，需要有一個棧存放每層遞歸調用時的指針和參數，最大遞歸調用層次與遞歸樹的深度一致，理想情況為⌈log2(n+1)⌉ 。因此，要求存儲開銷為O(log2n) 。但是，我們每次都選用序列的第一個元素作為比較的基准元素。這樣的選擇簡單但並不理想。在最壞的情況下，即待排序元素已經有序的情況下，其遞歸數成為單支樹，每次劃分只得到一個比上一次少一個元素的子序列。其排序速度退化到簡單排序的水平，比直接插入排序還要慢。占用附加存儲（即棧）將達到O(n) 。另外，基本的快速排序算法，對於n較大的平均情況而言，快速排序是“快速”的，但是當n很小時，這種排序方法往往比其他簡單排序方法還要慢。