快速排序

快速排序是应用了分治法策略的一种排序算法。

快排的C实现:

void quicksort(int *n, int len)
{
    int i, j=0;

    if (len<2) return;

    for (i=1; i<len; i++) {
        if (*(n+i) < *n) {
            swap(n+i, n+ ++j);
        }
    }
    swap(n, n+j);

    if (j>1) quicksort(n, j);
    if (j<len-2) quicksort(n+j+1, len-j-1);
}

快速排序的平均时间复杂度为\(n \lg n\) (准确的说为\(2n \ln n = 1.39 n \log_2 n\) , 来自维基), 最差情况下的时间复杂度为\(O(n^2)\) , 占用空间的复杂度最优为\(O(\lg n)\) , 最差为\(O(n)\) . 快速排序是不稳定的。

comments powered by Disqus