决策树模型

之前提到过的归并排序,堆排序,快速排序 都是基于比较的排序，也就是说排序的基本操作就是两两比较两个元素的大小，从而确定元素的大小。这样的排序方法其实可以用一种称为决策树 的模型来分析。注意，这里的决策树模型 和机器学习中的决策树模型 并不是同一个概念。

假设给定一个待排序的序列\(R=<a_1,a_2,\cdots,a_n >\),那么对于每一个这样的序列，我们总能给出其相应的决策树模型.这里的决策树模型，是一颗完全二叉树，树上的任何一个非叶结点都表示元素之间中的一次比较,叶结点表示一个这个序列可能的一种排序。对于\(R=<1,2,3>\)这个序列来说，它的决策树模型如下图所示:

每一个结点中的数字\(i:j\)表示当前比较的元素是\(R[i]\)和\(R[j]\)，如果比较结果是小于，则下一步走向左子树；如果是大于，则走向右子树。这样不断比较下去，最终达到叶结点，形成一种可能的排列。

对于一个长度为\(n\)的序列来说，它可能的所有排列的情况有\(n!\),因此它的叶结点数就是\(n!\)，在上述这个例子中就是\(3!=6\)个叶结点。

很自然，基于比较的排序算法就是从根结点开始找到到达目标叶结点的一条路径。

由于一棵决策树是一个完全二叉树，那么我们假设这棵树的高度是\(h\),叶结点树是\(l\),它对应的待排序序列的长度是\(n\)，那么根据完全二叉树的性质，我们有如下的不等式:

对上式两边取对数，我们就能够得到:

由此，我们可以看到，在最坏情况下，任何比较排序算法都需要做\(\Omega(n\lg n)\)次比较。

计数排序

计数排序并不是一种基于比较的排序，在它整个运行过程中，并不需要进行元素之间的比较，因此它不会受到上述\(\Omega(n\lg n)\)的限制.计数排序的基本思想是，对于每一个元素\(x\)，确定小于等于\(x\)的元素个数，从而就能确定\(x\)在输出结果上的位置。举例来说，如果小于等于\(x\)的元素有17个，那么\(x\)在输出数组上的位置就是18.

细节的算法过程在《算法导论》上都有，这里就不再细说了，具体的代码实现如下所示:

#!python
"""
The implement of the Counting Sort

The time consume of Counting Sort is O(n), and this algorithm is stable.

The drawbacks of the this algorithm is that it can only sort the numbers from 0 to k. If there is a negative number in the A, this algorithm can not work.

If the given data is very sparse, it will waster a lot space.
"""

def CountingSort(A):
    k = max(A)

    C = [0] * (k+1)
    B = [None] * len(A)

    for item in A:
        C[item] += 1
    # now C[i] contains the number of elements equal to i.

    for i in range(1,len(C)):
        C[i] = C[i-1] + C[i]
    # now C[i] contains the number of elements less than or equal to i.

    for i in range(len(A)-1,-1,-1): # why from len(A) to 0 not from 0 to len(A) ? Becuse it must be stable!
                                    # only from len(A) to 0 can guarntee stable.
        B[C[A[i]]-1] = A[i]     # not the B[C[A[i]]] = A[i], because A and C starts with 0, not 1.
        C[A[i]] -= 1

    return B

计数排序的缺点也很明显,首先它要求所有的元素必须是非负的，并且元素的分布不能太过分散，如果太过分散，在利用数组计数的时候很容易造成空间的浪费。

基数排序

基数排序的基本思想也很简单的，就是把每一个元素按位排序，先按照个位排序，然后按照十位排序，依次类推。这里很重要的一点就是，在对每一位排序的时候，所采用的排序算法都必须是稳定的(stable).在这里我们刚好可以是上面稳定的计数排序，具体代码如下:

#!python
"""
The implement of Radix Sort.

Radix Sort is using the property of the stable sorting algorithm.
"""

def counting_sort(A,index):
    k = max([item[index] for item in A])
    n = len(A)

    B = [0] * (k+1)
    C = [None] * n

    for item in A:
        B[item[index]] += 1

    for i in range(1,len(B)):
        B[i] += B[i-1]

    for i in range(len(A)-1,-1,-1):
        C[ B[ A[i][index] ] - 1 ] = A[i]
        B[A[i][index]] -= 1

    return C

def radix_sort(A):
    d = len(A[0])
    B = A[:]
    for i in range(d-1,-1,-1):
        B = counting_sort(B,i)
    return B

if __name__ == "__main__":
    A = [
            [3,2,9],
            [4,5,7],
            [6,5,7],
            [8,3,9],
            [4,3,6],
            [7,2,0],
            [3,5,5],
    ]
    print(A)
    B = radix_sort(A)
    print(B)

基数排序的动画演示:http://blogimg.chinaunix.net/blog/upfile/070912120349.swf

Share on: Twitter ❄ Facebook ❄ Email

---

---