[算法导论] 快速排序

2019-11-21

学习《算法导论》快速排序,需要重温数学知识,算法实现和推导是一个数学建模过程。测试源码在 (github)


1. 原理

对于包含 n 个数的输入数组来说,快速排序是一种最坏情况时间复杂度为 $O(n^2)$ 的排序算法。虽然最坏情况的时间复杂度很差,但是快排通常是实际排序应用中最好的选择,因为它平均性能非常好,它的期望实际复杂度是 $O(nlgn)$,而且 $O(nlgn)$ 中隐含的常数因子非常小,另外它还能够进行原址排序,甚至在虚存环境中也能很好地工作。

详细内容请参考《算法导论》第三版,第二部分,第七章:快速排序


2. 实现

根据数组哨兵的选择,有两种递归方式实现。

  • 以数组末位数值为哨兵排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int Partition(int array[], int start, int end) {
    int low = start - 1;
    int high = low + 1;
    int key = array[end];

    for (; high < end; high++) {
        if (array[high] <= key) {
            low++;
            if (high > low) {
                int temp = array[low];
                array[low] = array[high];
                array[high] = temp;
            }
        }
    }

    // 如果是有序数组,会出现左边都是最小的情况,要置换 partition 需要判断数据。
    int partition = low + 1;
    if (array[partition] > key) {
        int temp = array[partition];
        array[partition] = array[end];
        array[end] = temp;
    }

    return partition;
}

void qsort_end(int array[], int start, int end) {
    if (start < 0 || end <=0 || start >= end) {
        return;
    }

    int partition = Partition(array, start, end);
    if (partition >= 0) {
        qsort_end(array, start, partition - 1);
        qsort_end(array, partition + 1, end);
    }
}
  • 以数组中间数值为哨兵排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void qsort_mid(int array[], int start, int end) {
    if (start >= end) {
        return;
    }

    int high = end;
    int low = start;
    int key = array[(unsigned int)(start + end) / 2];

    while (low < high) {
        // 左边向右查找比 key 大的
        while (array[low] < key && low < end) {
            low++;
        }

        // 右边向左查找比 key 小的
        while (array[high] > key && high > start) {
            high--;
        }

        if (low <= high) {
            int temp = array[low];
            array[low] = array[high];
            array[high] = temp;
            low++;
            high--;
        }
    }

    qsort_mid(array, start, high);
    qsort_mid(array, low, end);
}

3. 时间复杂度推导

  • 最优情况下的时间复杂度

快速排序涉及到递归调用, 递归算法的时间复杂度公式: $T[n]=aT[\frac{n}{b}] + f(n)$ 数组共有 $n$个数值,最优的情况是每次取到的元素(哨兵)刚好平分整个数组。 此时的时间复杂度公式为:$T(n)= 2T[\frac{n}{2}] + f(n)$

结果递归树(《算法导论》2.3.2 分析分治算法


第一次递归: $T(n)= 2T[\frac{n}{2}] + f(n)$


第二次递归:令 $n = \frac{n}{2}$ , $T[\frac{n}{2}] = 2 {2T[\frac{n}{4}] + (\frac{n}{2})} + n = 2^2T[\frac{n}{(2^2)}] + 2n$


第三次递归:令 $n = \frac{n}{(2^2)}$ $T[\frac{n}{2^2}] = 2^2{2T[\frac{n}{2^3}] + \frac{n}{2^2}}+2n = 2^3T[\frac{n}{2^3}]+3n$


第 $m$次递归:令 $n = \frac{n}{2^{\left (m-1) \right.}}$ $T[\frac{n}{2^{\left(m-1)\right.}}] = 2^mT[1]+mn$


公式一直往下迭代,当最后数组不能再平分时,最后到$T[1]$,说明公式迭代完成($T[1]$是常量)也就是: $\frac{n}{2^{\left (m-1) \right.}} = 1$

$n = 2^{\left (m-1) \right.}$ ==> ( $n = 2^m$ ) ==> ( $m = log_2n$ )

当 $m = log_2n$ 时

$T[\frac{n}{2^{\left(m-1)\right.}}] = 2^mT[1]+mn = n + nlog_2n$

$n$ 为元素个数,当 $n \geq 2$ 时

$n + nlog_2n = n(1+log_2n) ==> nlog_2n ==> nlgn$


4. 参考