数据结构(金远平)试卷.ppt

JYP * JYP * 分析：设2k–1≤n 2k，则与记录表对应的完全二叉树有k层，第i层的结点数≤2i–1。第一个for循环对每个有子女的结点调用adjust一次。该循环的时间不大于各层结点数与该层结点可移动的最大距离的积之和，即 第二个for循环调用adjust共n–1次，最大深度为 ?log2(n+1)?。 因此，堆排序的总计算时间是O(n log n)。 而且，只需要O(1)辅助空间。 JYP * 作业：P259—16 JYP * 7.7 基数排序 当n个记录的关键字list[i].key（0≤in）的取值是0到n–1范围内的整数时，可以用下列代码对其排序： for (int i = 0; i n; i++) result[list[i].key] = list[i]; 这里用关键字值来确定记录在最终就序数组中的位置。这就是最基本的箱排序。 其中，我们为n个关键字值安排n个箱子，并根据关键字值将记录分配到对应的箱中。 此方法效率极高，无论记录关键字的初始顺序如何，只需要O(n) 时间即可完成排序。 JYP * 在实际应用中，一个箱子可以存放多个记录，同时关键字的取值范围不必与n直接关联。 为了有效地利用箱排序的思想，可以将关键字解释为多个子关键字：K0, …, Kd–1（K0是最高位，Kd–1是最低位）。 如果记录表R0, …, Rn-1中的任意两个记录Ri和Rj（0≤i j n）都满足 则称该记录表相对于关键字 (K0, …, Kd–1) 已排好序。 JYP * 例如，排序100张关键字值为0到99的卡片可看成对两个子关键字K0和K1的排序，其中K0对应十位，K1对应个位。 我们按最低位优先（简称LSD）策略应用箱排序解决此问题： 首先根据K1将卡片逐张分配到0号箱到9号箱中。 接着，将8号箱的卡片放在9号箱的之前，…，将0号箱的卡片放在1号箱的之前。 再根据K0按照稳定排序的要求将卡片逐张分配到0号箱到9号箱中，按照从0到9的箱号顺序收集即得到已排序的卡片。 JYP * 可见，如果关键字是十进制数，可将其中的每个十进制位看成一个子关键字，并按LSD策略用10个箱子对每个子关键字进行箱排序。 一般地，在基数排序中，用基数r分解关键字。 当r = 10，则得到上述十进制分解。 如果关键字是长度为d的小写英文标识符，则可分解为d个子关键字 (K0, …, Kd–1)，其中，Ki ? {‘a’, ‘b’, …, ‘z’} （0≤i d），r = 26。 基数r排序需要r个箱子。 JYP * 假设记录表是R0, …, Rn-1。关键字用基数r分解，每个分解为d位，每位的取值是0到r – 1，则需要r个箱子。 记录元素的类定义如下： class Element { public: … private: int key[d]; // 关键字数组，d是常数 // 其它字段 … int link; }; JYP * 每个箱子中的记录链接成队列，f[i]和e[i]（0≤i r）分别指向第i个箱子的首、尾记录。 函数RadixSort给出了用LSD策略实现基数r排序的细节： int RadixSort (Element *list, const int d, const int n) { // 按关键字key[0],…key[d-1]排序(list[0],…,list[n-1])， // 0≤key[i] radix，radix是常数 int f[radix], e[radix]; // radix个队列的首、尾指针 for (int i = 0; i n–1; i++) list[i].link = i+1; list[n–1].link = -1; int current = 0; // 链接成一个以current开 // 头的链表，用-1表示空指针 JYP * 由于jlogej是j的递增函数，由 (7.2) 式可得 Tavg(m)≤cm + = cm + = cm + = kmlogem + (cm + ) JYP * 当m≥2， cm +