基本思想

對任意給定的序列中某個(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)定