基本思想
对任意给定的序列中某个元素R，经过一趟排序后，将原序列分割成2个子序列（P(0),P(1),...P(R-1)）和(P(R+1),...,P(n-1)),其中前一个子序列中的所有元素都小于或等于元素R，后一个子序列中的元素都大于或等于R。
R被称为分割元素，以后只需对这两个子序列分别做快速排序，直到子序列为空或只有一个元素时结束。
解题之法
template <class T>
void QuickSort (T A[], int n){
Qsort(A, 0, n-1);
}
template <class T>
void Qsort (T A[], int left, int right){
int i, j;
if (left < right) {
i = left;
j = right + 1;
do {
do i++;
while (A[i] < A[left]);
do j--;
while (A[j] > A[left]);
if (i < j)
Swap(A[i], A[j]);
}while (i < j);
Swap (A[left], A[j]);
Qsort (A, left, j -1);
Qsort (A, j + 1, right);
}
}
复杂度
O(n*log n) 不稳定
