决策树模型和75排序

把时间花在有意义的地方

在研究算法的过程中，先从理论上给出一类算法在时间和空间上可以优化的上限，往往可以帮助我们认识哪些地方可以优化，哪些地方怎么优化是徒劳，从而将时间用在有价值的地方，而不是做没有意义的尝试。把时间花在有意义的事情上面，这正是我们研究算法的目的和意义所在。

CB排序算法

通过比较—交换来进行的排序算法叫做比较式排序算法，或者CB排序算法（Comparison-Based Sorting Algorithm）。CB排序算法最坏情况的时间复杂度下界为

其中为待排序的元素个数，并假设元素各不相同。证明这一结论的一般方法是决策树模型，信息论是另外一种可取的方法。

决策树模型

简单地说，决策树是一棵完全二叉树，其描述的算法过程通常对应一组选择过程：利用某种选择算法，从根节点开始，不断地选择当前节点的一个子节点来作为结果节点，直到到达叶子节点为止。所到达的叶子节点便是这一系列决策的结果。

CB排序算法的一次实际执行对应于从对应的决策树的根节点行进到某个叶节点的过程，其所需的比较（选择）次数为经过的路径的长度。最坏情况下，算法需要从决策树的根节点行进到其最深的叶节点。因此，一个CB排序算法在其最坏情况下所需的比较次数，就等于其决策树的高度。

显然，用任何正确的确定型CB排序算法（排序过程不包含随机过程，排序结果对只与输入的初始序列有关）对个元素的集合的种可能排列进行排序，排序的结果肯定是唯一的，并因初始状态的不同而走到决策树上不同的叶节点。因此，出现在叶节点上的种状态对应了个元素的初始索引的全部可能排列，而不同状态之间在元素顺序上并没有什么不同。由于根节需要能够接受所有可能的排列，在给定具体序列之前，我们不能对根节点下任何判断，只能作假设，并针对每种假设做相应的处理。正是因为初始状态包含太多的不确定性，所以我们对其进行扫描、比较、交换，使其不断趋于有序。

一图胜千言

一棵三个元素的排序树

我们看某一排序算法对一棵个互异的元素的决策树，有个叶节点，心里要明白，排序后这个叶节点上的元素序列其实是一样的，只是不同的叶节点对应着不同的初始顺序，所以通过不同的交换步骤而得来。上图显示了对三个元素进快速排序的决策树，每一次决策都根据某两个数的大小关系选择性地交换它们的顺序，叶节点上的数字是排序后的有序序列中的数字在初始序列中的索引。

CB排序算法最坏情况的下界

上面已经说明，所有可能结果的总数，即决策树的叶节点数。决策树是一棵完全二叉树，因为每一次比较，都要从一棵树上分裂出两棵子树。现在我们来证明，具有个叶节点的二叉树，其高度至少为。

这一证明可以间接地通过证明“高度为的二叉树最多有个叶节点”来完成。

证明：

直接计算法：

我们将具有两个儿子节点的节点叫做满节点（full node），将具有一个儿子节点的节点叫做单节点（single node）。可以证明，在一棵非空二叉树中，叶节点的个数为满节点的个数加。

考虑一棵具有个节点的树，设为树中满节点个数，为叶节点个数，为具有一个儿子节点的节点个数。

因为每个节点有两个儿子指针，故个节点总的儿子指针个数为。

除根节点外，树中每个节点都唯一地被一个儿子指针指向，故在个节点的个儿子指针中，只有个指向了有意义的地址，另外个为空指针，由个叶节点的个空指针和个单节点的个空指针组成。

根据以上阐述，满足的关系为。

。

在一个叶节点上增加一个节点，叶节点的个数不变，相反，非叶节点的个数增加了。所以，节点个数固定后，只有在树中不含单节点的情况下，叶占比才能最大，叶个数才能达到最多。

此时，树中只有满节点和叶节点，满足. 由于，所以。因为树中只有满节点和叶节点，所以必为奇数。

一棵高度为的二叉树，具有最多个节点，因此最多具有

个叶节点。

证毕。

归纳假设法：

如果，则最多存在个叶节点，满足。若不为，假设对如高度为的树，具有最多的叶节点数。现在，让我们我们给增加层，得到一棵层的二叉树。有多少个叶节点，只需计算一下中空指针的个数便知（这里的空指针只针对儿子指针而言）。这里不采取计算的策略，上面直接计算法证明中已经说明，只有在中不含有单节点的情况下，的叶节点的个数才能取到最大值。所以必是一棵完全二叉树（尽管不必完美），它的空指针全部位于叶节点上，空指针数目为，所以高度为的二叉树，其叶节点个数为。

证毕。

排序算法的下界

个元素一共有种不同的排列方式（假设这个元素互异），这要求决策树具有个叶节点；而每一次比较，决策树就会产生两个分支，所以排序算法的决策树一般是二叉树。

对N个元素进行排序，需要的比较次数为

所以，所有基于比较的排序算法的时间复杂度的下界为。具体说来，对个元素的序列进行比较排序，无论采用什么算法，都至少需要次比较才能完成。

这里便引出了题目中的问题——如何只使用7次比较对5个数进行排序，题目姑且将之命名为75排序。因为对5个元素进行排序至少需要次比较，而且你不能对输入的序列怀有任何的假设，也就是说，你必须保证你的算法能对5个元素的120种排列均作出正确的排序，所以75排序问题是颇有一点难度的。

75排序问题

75排序问题，即仅用7次比较来对5个数排序的问题。这是使用最少比较次数进行排序的一次实践。
假设给定一个包含5个元素的任意序列：，下面我们来探讨一下如何使它变得有序。

1. 开始的时候，每个元素都是等价的，因为比较在所难免，所以不妨先选两组（4个）数进行比较。
   为简单起见，我们让和比较并交换（如果需要的话），使得，并以表示有序的序列，这将消耗一次比较的机会。同理我们将和比较并在必要时交换位置，从而得到的有序排列。
   这时，我们消耗掉了两次比较的机会，得到。

2. 比较和并做一些操作使得前三个数有序。这样做的目的是后面要进行二分插入排序。
   比较和将有两种结果：

   • 如果，那么这时已知的最长的有序序列是，我们将要进行一些操作使得有序序列变为，以便接下来进行二分插入排序。解决方法便是，和交换，和交换，然后再将和交换。注意，这种情况下，我们已知，所以最后将插入时只需将其插入前三个数，而无需考虑第四个数（可能是和）因为它必定大于。
   • 否则，，但是我们并不知道和的大小关系，所以将和交换位置，以使得前三个数有序。这里，同上面的情况一样，和的大小关系是已知的，所以最后将插入时只需考虑前三个数，而无需考虑第四个数。

3. 第2步虽然进行了许多操作，实际上只进行了1次比较，所以到目前为之，我们一共使用了3次比较的机会，还剩4次比较的机会。
   接下来是将插入前三个元素，因为前三个元素是有序的，所以我们使用二分插入的方法，每次插入需要2次比较。
   将最后一个数插入有序序列，得到有序序列，此时还剩下2次比较机会，由于第2步的缘故，我们已知最后一个数一定不是最大的，所以也将其二分插入到有序序列中，从而得到有序序列。 于是便完成了对5个数的任意排列的排序。

整个算法亦可用伪代码来描述，不过下面给出了C语言的描述，以及枚举5个数的全排列来对算法进行测试。

代码实现

///////////////////////////////
// running with Tinycc or Gcc//
///////////////////////////////
#include <stdio.h>

#define swap(a, b) ({ \
    typeof(a) tmp = a; a = b; b = tmp; })
#define cmpSwap(i, j) \
    if (A[i] > A[j]) swap(A[i], A[j])

// 将第5个元素以二分搜索的方式插入前三个元素中
#define insert_A4_into_A012()       \
{                                   \
    int pos;                        \
    if (A[4] < A[1]) {              \
        if (A[4] < A[0])            \
            pos = 0;                \
        else                        \
            pos = 1;                \
    }                               \
    else {                          \
        if (A[4] < A[2])            \
            pos = 2;                \
        else                        \
            pos = 3;                \
        }                           \
        int a4 = A[4];              \
    for (int i = 4; i > pos; --i)   \
        A[i] = A[i - 1];            \
    A[pos] = a4;                    \
}

// Sort 5 elements with only 7 comparisons
void sort5e7c(int *A)
{
    cmpSwap(0, 1);
    cmpSwap(2, 3);

    if (A[1] > A[3]) {
        int temp = A[0];
        A[0] = A[2];
        A[2] = A[1];
        A[1] = A[3];
        A[3] = temp;
    }
    else
        swap(A[2], A[3]);
    // insert A[4] into A[0, 1, 2], so that A[3] -> A[4]
    insert_A4_into_A012();
    // insert A[4] into A[0, 1, 2]
    insert_A4_into_A012();

}

有序性判断

int issorted(int *A, int len)
{
    for (int i = 0; i < len - 1; ++i)
        if (A[i] > A[i + 1])
            return 0;
    return 1;
}

测试算法的正确性

void full_permutation(int *A, int *B, void sort(int *), int begin, int end, int len);

void test_sort_algo(void sort(int *), int len)
{
    int A[len], B[len];
    for (int i = 0; i < len; ++i)
        A[i] = i + 1;
    // 对全排列进行测试
    full_permutation(A, B, sort, 0, len - 1, len);
}

int main()
{
    test_sort_algo(sort4e5c, 4);
    test_sort_algo(sort5e7c, 5);
    return 0;
}

枚举全排列

void full_permutation(int *A, int *B, void sort(int *), int begin, int end, int len)
{
    if (begin >= len) {
        memcpy(B, A, len * sizeof(int));
        sort(B);
        if (!issorted(B, len)) {
            printf("Fault order:\t");
        }
    }
    else {
        for (int i = begin; i <= end; ++i) {
            swap(A[begin], A[i]);
            full_permutation(A, B, sort, begin + 1, end, len);
            swap(A[begin], A[i]);
        }
    }
}

54排序问题

同75排序问题一样，也是使用最少的比较次数（）进行排序的实践，不过相对简单，下面只给出代码。

// 仅使用5次比较对4个元素进行排序
void sort4e5c(int *A)
{
    cmpSwap(0, 1);
    cmpSwap(2, 3);
    cmpSwap(0, 2);
    cmpSwap(1, 3);
    cmpSwap(1, 2);
}

这个代码是采用比较—交换来实现的，其实如果我们使用归并排序来解决4个数的排序问题，也仅需要5次比较。