Articles

快速排序(Quick Sort)

快速排序的代码要比前面介绍的堆排序和归并排序都要简洁。快速排序也是一种递归的排序方法。它首先从待排序的数组中找出一个关键元素,一般是第一个或者最后一个元素。然后将数组中大于该元素的放到一边,小于该元素的放到另外一边。然后分别对两边的元素进行递归的快速排序。

template <typename T>
int partition(T a[], int low, int high)
{
    T key = a[high];

    int i = low;
    for (int j = low; j < high; j++)
        if (a[j] < key)
            swap(a[i++], a[j]);

    swap(a[high], a[i]);
    return i;
}

template <typename T>
void quick_sort(T a[], int low, int high)
{
    if (low < high)
    {
        int p = partition(a, low, high);
        quick_sort(a, low, p - 1);
        quick_sort(a, p + 1, high);
    }
}

在最坏的情况下,如果我们选择的关键元素不够好,它总是最大的或者最小的那个元素,那我们需要递归n-1次才行。这样时间复杂度就变成了\( O(n^2) \)。比堆排序和归并排序的最坏情况要坏。但是,这种最坏情况出现的概率是比较低的。所以平均情况下,快速排序的时间复杂度是\( O(nlgn) \)。