基本思想
對任意給定的序列中某個(gè)元素R，經(jīng)過一趟排序后巧勤，將原序列分割成2個(gè)子序列（P(0),P(1),...P(R-1)）和(P(R+1),...,P(n-1)),其中前一個(gè)子序列中的所有元素都小于或等于元素R，后一個(gè)子序列中的元素都大于或等于R。
R被稱為分割元素永高，以后只需對這兩個(gè)子序列分別做快速排序隧土，直到子序列為空或只有一個(gè)元素時(shí)結(jié)束。
解題之法
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);
}
}
復(fù)雜度
O(n*log n) 不穩(wěn)定
