快速排序与随机构建二叉搜索树

　　写这篇博客的目的主要是详细分析随机构建二叉搜索树，因为下一篇博客主要讲Treap，证明需要用到随机构建二叉搜索树，Treap是在学习完红黑树之后做的13-4的思考题，第一次看着概念独立写出一种树不看别人的代码，并且加上证明。对于红黑树的博客，也打算写，毕竟红黑树的分析算是一种比较简单的，分析红黑树完全比不上分析Treap难，尽管Treap是最简单的树。

快速排序的描述：

　　对于包含n个数的数组而言，快速排序是一种最坏时间复杂度为O(n2)的排序算法。虽然最环情况很差，但是快速排序往往是排序时的最优选择，因为期望时间复杂度为Θ(nlogn)，并且常数很小。

　　快速排序使用了分治的思想，下面是快速排序的分治步骤：

  1. 分解：将数组A[l, r] 划分为A[l, p?1] 和 A[p+1, r]两个数组，使得A[l, p?1]中的元素全都小于A[p]，A[p+1, r]中的元素全都大于A[p]
  2. 递归：对A[l, p?1] 和 A[p+1, r]两个数组执行快速排序

　　下面是快速排序的实现：

package jckeep.sort;

import java.math.*;
import java.util.Comparator;

public class Sort {
    public static extends Comparable> void qsort(E[] A, int l, int r) {
        if (l < r) {
            int p = partition(A, l, r);
            qsort(A, l, p - 1);
            qsort(A, p + 1, r);
        }    
    }

    
    public static  void qsort(E[] A, int l, int r, Comparator<? super E> cmp) {
        if (l < r) {
                        int p = partition(A, l, r, cmp);
                        qsort(A, l, p - 1, cmp);
                        qsort(A, p + 1, r, cmp);
                }

    }


    public static extends Comparable> void topK(E[] A, int l, int r, int i) {
                if (l < r) {
                        int p = partition(A, l, r);
            int k = p - l + 1;
                        if (i == k)
                                return;
                        else if (i < k)
                                topK(A, l, p - 1, i);
                        else
                                topK(A, p + 1, r, i - k);
                }
        }

    private static extends Comparable> int partition(E[] A, int l, int r) {
        E p = A[r];
        int i = l - 1;
        for (int j = l; j < r; ++j) {
            if (A[j].compareTo(p) <= 0)
                swap(A, j, ++i);
        }
        swap(A, ++i, r);
        return i;
    }


    private static  int partition(E[] A, int l, int r, Comparator<? super E> cmp) {
                E p = A[r];
                int i = l - 1;
                for (int j = l; j < r; ++j) {
                        if (cmp.compare(A[j],p) <= 0)
                                swap(A, j, ++i);
                }
                swap(A, ++i, r);
                return i;
        }


    public static  void swap(E[] A, int i, int j) {
        E p = A[i];
        A[i] = A[j];
        A[j] = p;
    }
}

　　

　　排序过程中总是选取p = A[r]为主元，并围绕它来进行划分。

快速排序的平均情况分析：

通过观察，我们不难得出快速排序的运行时间的关系：

　　对于一般情况，我们假设每个元素被选取作为主元的概率相等，为1/n，所以我们可以得出：

　　通过构造，我们可以得到：

　　并注意到，右边最后一项为调和级数：

　　所以可以得到：

随机构建的二叉搜索树

　　证明随机构建的二叉搜索树的高度与节点深度的期望值，通过i证明，我们可以发现二叉搜索树与快速排序的递推关系具有相似之处，并且快速排序就其本质就是一棵随机插入的二叉搜索树，二叉搜索树最坏情况插入为O(n)，n次插入即为O(n2)，正式快速排序的下界，并且导致这种极端情况的数据都有一个特点：基本有序。我们以快速排序的期望时间分析来分析二叉搜索树，这样能够更好的理解。(虽然二叉搜索树是最普通的一种搜索树，但分析平均情况却比很多平衡树要难得多)。

　　定理1：一棵有n个不同节点的随机构建二叉搜索树的期望高度为O(log n)

　　证明  ：定义：(1) Xn ：一棵具有n个节点的随机构建二叉搜索树的高度

　　　　　　　　  (2)Yn  ：2Xn  定义为指数高度

　　　　　　　　  (3)Rn  : 表示这个关键字在二叉搜索树中的秩，即左子树的节点树加1

　　所以由定义我们可以得到：

　　其中初始条件为Y0 = 0（定义n=0时为0）， Y1 = 1

　　对于n个节点的随机构建二叉搜索树，每个节点根节点为根节点的概率相等，所以E(pi) = 1/n

　　因此我们有：

　　我们对等式两边求期望值

　　我们可以得出最后的不等式，这里不给出证明过程，可以通过数学归纳法进行证明，中等难度：

　　最后我们应用Jensen不等式，有：

　　所以我们可以得到 E(Xn) = O(log n)

　　定理2：随机构建二叉搜索树的平均节点深度为O(log n)

　　证明：定义P(T)为T中所有节点x的深度之和，每个节点深度定义为d(x)

　　我们可以轻易地知道平均节点深度：

　　设Tl 为左子树，Tr 为右子树，所以我们有

　　与前面类似，由于每个节点为根节点概率相等，所以有

　　可以看到，这个递推式正式快速排序的递推式，快速排序与排序过程中隐式的建立了一棵二叉搜索树，这棵树等价于一棵随机构建二叉搜索树，并且复杂度相同，同时常数也几乎相同。也就是说把数组逐个插入二叉搜索树与执行快速排序速度是几乎相同的，因为常数几乎相同。

　　显而易见平均节点深度为O(log n)

相关

标签