《数据结构习题解答》习题9解答

非序 静态数据表类定义 #include <iostream. h> template <class Type> class dataList ∥数据表的前视声明 template <class Type> class Element ∥数据表元素类的定义 Type key ∥排序码 ∥其它数据成 Type getKey (i return key: ∥取当前结点的排序码 void setKey( const Type x )i key=x;) ∥将当前结点的排序码修改为x Element.<Iype>& operator=(emen<Iyp>&x)结点x的值赋给this i key =x->key; otherdata =x-otherdata;) ey;}消判this与x相等 int operator<=(Type&x){ return key s=x->key;}/判this小于或等于x int operator>(Type&x){ return key>x->key;}m判this大于x nt operator<(Iype&x){ return key>x->key;}m判this小于 template <class Type> class dataList 用顺序表来存储待排序的元素,这些元素的类型是Type Element <Type>*Vector; ∥存储待排序元素的向量 ∥最大元素个数与当前元素个数 int Partition( const int low, const int high ∥用于快速排序的一次划分算法 datalist( int MaxSz= DefaultSize ) Maxsize( Maxsz ) CurrentSize(0) Vector=new Element <Type>[MaxSize:;) ∥构造函数 int length(( return CurrentSize; U(int i)( return Vector[;) void swap( Element<ype>&x, lement<Iype>&y)∥交换x,y ∥排序 静态链表类定义 template <class Type> class staticlinkList; 静态链表类的前视声明 template <class Type> class Element i 1静态链表元素类的定义 friend class staticlinkList<Type>: Type key: ∥排序码,其它信息略 ∥结点的链接指针

第 9 章 排序 1 静态数据表类定义 #include <iostream.h> const int DefaultSize = 100; template <class Type> class dataList //数据表的前视声明 template <class Type> class Element { //数据表元素类的定义 friend class dataList <Type>; private: Type key; //排序码 field otherdata; //其它数据成员 public: Type getKey ( ) { return key; } //取当前结点的排序码 void setKey ( const Type x ) { key = x; } //将当前结点的排序码修改为 x Element<Type>& operator = ( Element<Type>& x ) //结点 x 的值赋给 this { key = x->key; otherdata = x->otherdata; } int operator == ( Type& x ) { return key == x->key; } //判 this 与 x 相等 int operator <= ( Type& x ) { return key <= x->key; } //判 this 小于或等于 x int operator > ( Type& x ) { return key > x->key; } //判 this 大于 x int operator < ( Type& x ) { return key > x->key; } //判 this 小于 x } template <class Type> class dataList { //用顺序表来存储待排序的元素，这些元素的类型是 Type private: Element <Type> * Vector; //存储待排序元素的向量 int MaxSize, CurrentSize; //最大元素个数与当前元素个数 int Partition ( const int low, const int high ) //用于快速排序的一次划分算法 public: datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element <Type> [MaxSize]; } //构造函数 int length ( ) { return CurrentSize; } Element<Type>& operator [ ] ( int i ) { return Vector[i]; } void swap ( Element <Type>& x, Element <Type>& y ) //交换 x, y { Element <Type> temp = x; x = y; y = temp; } void Sort ( ); //排序 } 静态链表类定义 template <class Type> class staticlinkList; //静态链表类的前视声明 template <class Type> class Element { //静态链表元素类的定义 friend class staticlinkList<Type>; private: Type key; //排序码，其它信息略 int link; //结点的链接指针 public:

第9章排序 Type getKey (f return key; 1 ∥取当前结点的排序码 void setKey( const Type x){key=x;}将当前结点的排序码修改为x ink(return link; ∥取当前结点的链接指针 void setlink( const int ptr){lmk=ptr;}/将当前结点的链接指针置为ptr template <class Type> class staticlinklist i 静态链表的类定义 ement <Type>*Vector; ∥储待排序元素的向量 int MaxSize, Currents ize 向量中最大元素个数和当前元素个数 dstaticlinkList( int Maxsz=DefaultSize ) MaxSize( Maxsz ) CurrentSize(0) Vector= new Element <Type>[Maxsz: 9-1什么是内排序?什么是外排序?什么排序方法是稳定的?什么排序方法是不稳定的? 【解答】内排序是排序过程中参与排序的数据全部在内存中所做的排序,排序过程中无需进 行内外存数据传送,决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移 动次数。外排序是在排序的过程中参与排序的数据太多,在内存中容纳不下,因此在排序过 程中需要不断进行内外存的信息传送的排序。决定外排序时间性能的主要是读写磁盘次数和 在内存中总的记录对象的归并次数 不稳定的排序方法主要有希尔排序、直接选择排序、堆排序、快速排序。不稳定的排序 方法往往是按一定的间隔移动或交换记录对象的位置,从而可能导致具有相等排序码的不同 对象的前后相对位置在排序前后颠倒过来。其他排序方法中如果有数据交换,只是在相邻的 数据对象间比较排序码,如果发生逆序(与最终排序的顺序相反的次序)才交换,因此具有相 等排序码的不同对象的前后相对位置在排序前后不会颠倒,是稳定的排序方法。但如果把算 法中判断逆序的比较“>(或<)”改写成“≥(或≤)”,也可能造成不稳定 92设待排序的排序码序列为{122,16,30,28,10,16*,20,6,18},试分别写出使用以下排序 方法每趟排序后的结果。并说明做了多少次排序码比较。 (1)直接插入排序 (2)希尔排序(增量为5,2,1)(3)起泡排序 (4)快速排序 (5)直接选择排序 (6)基数排序 7)堆排序 (8)二路归并排序 【解答】 (1)直接插入排序 初始排列0123 6789排序码比较次数 1[1212163028101620618 12] 666 302 30281016 301281016 000 i=5[212、16、28、30]1016′20618 5 2220

第 9 章 排序 2 Type getKey ( ) { return key; } //取当前结点的排序码 void setKey ( const Type x ) { key = x; } //将当前结点的排序码修改为 x int getLink ( ) { return link; } //取当前结点的链接指针 void setLink ( const int ptr ) { link = ptr; } //将当前结点的链接指针置为 ptr } template <class Type> class staticlinkList { //静态链表的类定义 private: Element <Type> *Vector; //存储待排序元素的向量 int MaxSize, CurrentSize; //向量中最大元素个数和当前元素个数 public: dstaticlinkList ( int Maxsz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element <Type> [Maxsz]; } } 9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? 【解答】内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进 行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移 动次数。外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在排序过 程中需要不断进行内外存的信息传送的排序。决定外排序时间性能的主要是读写磁盘次数和 在内存中总的记录对象的归并次数。 不稳定的排序方法主要有希尔排序、直接选择排序、堆排序、快速排序。不稳定的排序 方法往往是按一定的间隔移动或交换记录对象的位置，从而可能导致具有相等排序码的不同 对象的前后相对位置在排序前后颠倒过来。其他排序方法中如果有数据交换，只是在相邻的 数据对象间比较排序码，如果发生逆序(与最终排序的顺序相反的次序)才交换，因此具有相 等排序码的不同对象的前后相对位置在排序前后不会颠倒，是稳定的排序方法。但如果把算 法中判断逆序的比较“>(或<)”改写成“≥(或≤)”，也可能造成不稳定。 9-2 设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序 方法每趟排序后的结果。并说明做了多少次排序码比较。 (1) 直接插入排序 (2) 希尔排序(增量为 5,2,1) (3) 起泡排序 (4) 快速排序 (5) 直接选择排序 (6) 基数排序 (7) 堆排序 (8) 二路归并排序 【解答】 (1) 直接插入排序 初始排列 0 1 2 3 4 5 6 7 8 9 排序码比较次数 i = 1 [ 12 ] 2 16 30 28 10 16* 20 6 18 1 i = 2 [ 2 12 ] 16 30 28 10 16* 20 6 18 1 i = 3 [ 2 12 16 ] 30 28 10 16* 20 6 18 1 i = 4 [ 2 12 16 30 ] 28 10 16* 20 6 18 2 i = 5 [ 2 12 16 28 30 ] 10 16* 20 6 18 5 i = 6 [ 2 10 12 16 28 30 ] 16* 20 6 18 3 i = 7 [ 2 10 12 16 16* 28 30 ] 20 6 18 3 i = 8 [ 2 10 12 16 16* 20 28 30 ] 6 18 3 i = 9 [ 2 6 10 12 16 16* 20 28 30 ] 18 8 [ 2 6 10 12 16 16* 18 20 28 30 ]

非序 (2)希尔排序(增量为5,2,1) 初始排列0 56789排序码比较次数 1221630281016206181+1+1+1+1=5 10216 1+1)=9 1021661612182030281+1+3+1+3+1+ 希尔(shel)人采取的增量序列为Ln/21ln/2y2ln/2y2y2↓…,1。一般地,增量 序列可采用 na llna」a」lna」a」Ja」…,l。大量实验表明,取a=045454的增量序列 比取其他的增量序列的优越性更显著。计算L045454n」的一个简单方法是用整数算术计算 (5*n-1)/11。需要注意,当α<1/2时,增量序列可能不以1结束,需要加以判断和调整。 3)起泡排序 初始排列01 6789排序码比较 0[12216,30,28,10 12,616,302810162018 12101630,2816 12161 30281820 6 [161618302820 5 16[1618203028] 10121616[ 121616 4)快速排序 Pivot Pvtpos0123456789排序码比较次数 pos I pos I pos I pos 6210112[281616203018 pos I pos 84,5,6,78[2]6[10]121281616 30181 184,5,6 121816162028[30 2610121616l18[20

第 9 章 排序 3 (2) 希尔排序(增量为 5,2,1) 初始排列 0 1 2 3 4 5 6 7 8 9 排序码比较次数 12 2 16 30 28 10 16* 20 6 18 1+1+1+1+1 = 5 d = 5 10 2 16 6 18 12 16* 20 30 28 (1+1+2+1) + (1+1 d = 2 +1+1) = 9 10 2 16 6 16 * 12 18 20 30 28 1+1+3+1+3+1+1 d = 1 +1+2 = 14 2 6 10 12 16 16* 18 20 28 30 希尔(shell)本人采取的增量序列为 n/2, n/2/2, n/2/2/2, …,1。一般地，增量 序列可采用nα, nαα, nααα, …, 1。大量实验表明，取α=0.45454 的增量序列 比取其他的增量序列的优越性更显著。计算 0.45454n 的一个简单方法是用整数算术计算 (5*n-1)/11。需要注意，当< 1/2 时，增量序列可能不以 1 结束，需要加以判断和调整。 (3) 起泡排序 初始排列 0 1 2 3 4 5 6 7 8 9 排序码比较次数 i = 0 [ 12 2 16 30 28 10 16* 20 6 18 ] 9 i = 1 2 [ 12 6 16 30 28 10 16* 20 18 ] 8 i = 2 2 6 [ 12 10 16 30 28 16* 18 20 ] 7 i = 3 2 6 10 [ 12 16 16* 30 28 18 20 ] 6 i = 4 2 6 10 12 [ 16 16* 18 30 28 20 ] 5 i = 5 2 6 10 12 16 [ 16* 18 20 30 28 ] 4 i = 6 2 6 10 12 16 16* [ 18 20 28 30 ] 3 2 6 10 12 16 16* 18 20 28 30 (4) 快速排序 Pivot Pvtpos 0 1 2 3 4 5 6 7 8 9 排序码比较次数 12 0,1,2,3 [ 12 2 16 30 28 10 16* 20 6 18 ] 9 6 0,1 [ 6 2 10 ] 12 [ 28 16 16* 20 30 18 ] 2 28 4,5,6,7,8 [ 2 ] 6 [ 10 ] 12 [ 28 16 16* 20 30 18 ] 5 18 4,5,6 2 6 10 12 [ 18 16 16* 20 ] 28 [ 30 ] 3 16* 4 2 6 10 12 [ 16 * 16 ] 18 [ 20 ] 28 30 1 2 6 10 12 16* [ 16 ] 18 20 28 30 pos pos pos pos pos pos pos pos pos pos pos pos pos pos pos

非序 左子序列递归深度为1,右子序列递归深度为3 (5)直接选择排序 初始排列0123 6789排序码比较次数 2[12163028101620 6101216[2816203018] 610121616[28203018] 2 610121616·18 8[30 (6)基数排序 12}[2}[16}-[30--[28}[0}[16}[20}6}[18 按最低位分配 r[]r[2]r3]r[4]r[5]r[e 16 f1 f2 f3 f4 f5 f6 f7 f8 f9 收集[30}[10}[20}[12[2[6}[16}[6}[28}[18 按最高位分配 ro]r[1r2]r[]r4]r]r6]r[7r8]r9 20 fo f[ f2 f3 f4 f5 f6 f7 f8 f9

第 9 章 排序 4 左子序列递归深度为 1，右子序列递归深度为 3。 (5) 直接选择排序 初始排列 0 1 2 3 4 5 6 7 8 9 排序码比较次数 i = 0 [ 12 2 16 30 28 10 16* 20 6 18 ] 9 i = 1 2 [ 12 16 30 28 10 16* 20 6 18 ] 8 i = 2 2 6 [ 16 30 28 10 16* 20 12 18 ] 7 i = 3 2 6 10 [ 30 28 16 16* 20 12 18 ] 6 i = 4 2 6 10 12 [ 28 16 16* 20 30 18 ] 5 i = 5 2 6 10 12 16 [ 28 16* 20 30 18 ] 4 i = 6 2 6 10 12 16 16* [ 28 20 30 18 ] 3 i = 7 2 6 10 12 16 16* 18 [ 20 30 28 ] 2 i = 8 2 6 10 12 16 16* 16 20 [ 30 28 ] 1 2 6 10 12 16 16* 16 20 28 [ 30 ] (6)基数排序 收集 按最高位分配 12 2 16 30 28 10 16* 20 6 18 按最低位分配 r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 12 2 30 16 28 10 16* 20 6 18 30 10 20 12 2 16 16* 6 28 18 r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] 18 16* 16 12 2 10 20 30 6 28

非序 收集[2[6□0}[12}[6}[6}18}[20}[28}-30 (7)堆排序 第一步,形成初始的最大堆(略),第二步,做堆排序 初始排列,不是最大堆 形成初始最大堆 交换0与9对象 ⑩ 从0#到8#重新形成堆交换0#与8#对象从0#到7#重新形成堆 ⑩Q 交换Q#与7#对象从O#到6#重新形成堆交换O#与6#对象 从O#到5#重新形成堆 交换0#与5#对象 从0#到4#重新形成堆

第 9 章 排序 5 收集 (7) 堆排序 第一步，形成初始的最大堆 (略)，第二步，做堆排序。 初始排列，不是最大堆 形成初始最大堆 交换 0 # 与 9 # 对象 从 0# 到 8# 重新形成堆 交换 0# 与 8# 对象 从 0# 到 7# 重新形成堆 交换 0# 与 7# 对象 从 0# 到 6# 重新形成堆 交换 0# 与 6# 对象 从 0# 到 5# 重新形成堆 交换 0# 与 5# 对象 从 0# 到 4# 重新形成堆 12 2 16 30 28 10 16* 20 6 18 30 28 16 20 18 10 16* 2 6 12 12 28 16 20 18 10 16* 2 6 30 28 20 16 12 18 10 16* 2 6 30 6 20 16 12 18 10 16* 2 28 30 20 18 16 12 6 10 16* 2 28 30 2 18 16 12 6 10 16* 20 28 30 18 12 16 2 6 10 16* 20 28 30 12 16 2 6 10 16* 20 28 30 18 10 12 16 2 6 16* 20 28 30 10 12 16 2 6 16* 20 28 30 18 18 16 12 10 2 6 16* 20 28 30 18 6 12 10 2 16 16* 20 28 30 18 12 6 10 2 16 16* 20 28 30 18 2 6 10 12 16 16* 20 28 30 18 16* 2 6 10 12 16 18 20 28 30