第3章 数据描述.ppt

箱子排序实现 void BinSort(ChainNode X, int range) {// Sort by score. int len = X.Length(); Node x; ChainNode *bin; bin = new ChainNode [range + 1]; // 以下部分为关键：将元素放入箱子 for (int i = 1; i = len; i++) { X.Delete(1,x); bin[x.score].Insert(0,x); } 元素的取值范围 * 箱子排序实现（续） for (int j = range; j = 0; j--) while (!bin[j].IsEmpty()) { bin[j].Delete(1,x); X.Insert(0,x); } delete [] bin; } Delete操作——Θ(1)? 第一个循环Θ(n)，第二个循环Θ(n+range) 总复杂性Θ(n+range) * 优化：作为Chain类的成员函数 直接操纵Chain的数据成员【程序3-44】 节点重复被多个链表使用，避免对new和delete的频繁调用 templateclass T void ChainT::BinSort(int range) {// Sort by score. int b; // bin index ChainNodeT **bottom, **top; bottom = new ChainNodeT* [range + 1]; top = new ChainNodeT* [range + 1]; for (b = 0; b = range; b++) bottom[b] = 0; bottom[b]：箱子b链表首top[b]：箱子b链表尾 * 优化：作为Chain类的成员函数 // distribute to bins for (; first; first = first-link) {// add to bin b = first-data; if (bottom[b]) {// bin not empty top[b]-link = first; top[b] = first;} else // bin empty bottom[b] = top[b] = first; } Delete、Insert调用变为对链表内部结构的直接操纵 旧版本：Delete——deleteInsert——new新版本：节点从原链表摘除，直接放入箱子链表 * 优化：作为Chain类的成员函数 // collect from bins into sorted chain ChainNodeT *y = 0; for (b = 0; b = range; b++) if (bottom[b]) {// bin not empty if (y) // not first nonempty bin y-link = bottom[b]; else // first nonempty bin first = bottom[b]; y = top[b];} if (y) y-link = 0; delete [] bottom; delete [] top; } 时间复杂性Θ(n+2range) 稳定排序 * 基数排序（radix sort） 箱子排序的优点，如果元素可能取值范围较小（nrange），复杂性Θ(n+range)明显优于其他排序算法 但若nrange，性能则会很差 基数排序——多阶段的箱子排序 * 基数排序的思想 将数据切为几段，每段对次序的影响力是不同的 如0～rc-1的n个整数排序，rc-1（range）n 将整数分解为c位r进制数十进制：928?9、2、8；3725?3、7、2、560进制：3725?1、2、5；928?15、28 c个步骤：每个步骤对分解后的每一位进行箱子排序?Θ((n+r)*c)Θ(n+rc) * 基数排序例 箱子排序：2010个执行步（2*range+n） 基数排序：90个执行步（c*(2*r+n)） * 基数的选定 1000个数，取值范围0～106-1 r=106——简单箱子排序：2001000步 r=1000：