104. 快速排序

基本思想

对任意给定的序列中某个元素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) 不稳定