非序 静态数据表类定义 #include template class dataList ∥数据表的前视声明 template class Element ∥数据表元素类的定义 Type key ∥排序码 ∥其它数据成 Type getKey (i return key: ∥取当前结点的排序码 void setKey( const Type x )i key=x;) ∥将当前结点的排序码修改为x Element.& operator=(emen&x)结点x的值赋给this i key =x->key; otherdata =x-otherdata;) ey;}消判this与x相等 int operatorkey;}/判this小于或等于x int operator>(Type&x){ return key>x->key;}m判this大于x nt operatorx->key;}m判this小于 template class dataList 用顺序表来存储待排序的元素,这些元素的类型是Type Element *Vector; ∥存储待排序元素的向量 ∥最大元素个数与当前元素个数 int Partition( const int low, const int high ∥用于快速排序的一次划分算法 datalist( int MaxSz= DefaultSize ) Maxsize( Maxsz ) CurrentSize(0) Vector=new Element [MaxSize:;) ∥构造函数 int length(( return CurrentSize; U(int i)( return Vector[;) void swap( Element&x, lement&y)∥交换x,y ∥排序 静态链表类定义 template class staticlinkList; 静态链表类的前视声明 template class Element i 1静态链表元素类的定义 friend class staticlinkList: Type key: ∥排序码,其它信息略 ∥结点的链接指针
第 9 章 排序 1 静态数据表类定义 #include const int DefaultSize = 100; template class dataList //数据表的前视声明 template class Element { //数据表元素类的定义 friend class dataList ; private: Type key; //排序码 field otherdata; //其它数据成员 public: Type getKey ( ) { return key; } //取当前结点的排序码 void setKey ( const Type x ) { key = x; } //将当前结点的排序码修改为 x Element& operator = ( Element& x ) //结点 x 的值赋给 this { key = x->key; otherdata = x->otherdata; } int operator == ( Type& x ) { return key == x->key; } //判 this 与 x 相等 int operator key; } //判 this 小于或等于 x int operator > ( Type& x ) { return key > x->key; } //判 this 大于 x int operator x->key; } //判 this 小于 x } template class dataList { //用顺序表来存储待排序的元素，这些元素的类型是 Type private: Element * Vector; //存储待排序元素的向量 int MaxSize, CurrentSize; //最大元素个数与当前元素个数 int Partition ( const int low, const int high ) //用于快速排序的一次划分算法 public: datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [MaxSize]; } //构造函数 int length ( ) { return CurrentSize; } Element& operator [ ] ( int i ) { return Vector[i]; } void swap ( Element & x, Element & y ) //交换 x, y { Element temp = x; x = y; y = temp; } void Sort ( ); //排序 } 静态链表类定义 template class staticlinkList; //静态链表类的前视声明 template class Element { //静态链表元素类的定义 friend class staticlinkList; 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 staticlinklist i 静态链表的类定义 ement *Vector; ∥储待排序元素的向量 int MaxSize, Currents ize 向量中最大元素个数和当前元素个数 dstaticlinkList( int Maxsz=DefaultSize ) MaxSize( Maxsz ) CurrentSize(0) Vector= new Element [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 staticlinkList { //静态链表的类定义 private: Element *Vector; //存储待排序元素的向量 int MaxSize, CurrentSize; //向量中最大元素个数和当前元素个数 public: dstaticlinkList ( int Maxsz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [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
非序 交换O#与4#对象从O#到3#重新形成堆交换0#与3#对象 从0#到2#重新形成堆交换0#与2#对象从0#到1#重新形成堆 交换0#与1#对象 从O#到1#重新形成堆,得到结果 (8)二路归并排序 采用迭代的方法进行归并排序。设待排序的数据对象有n个。首先把每一个待排序的数 据对象看作是长度为的初始归并项,然后进行两两归并,形成长度为2的归并项,再对它们 两两归并,形成长度为4的归并项,如此一趟一趟做下去,最后得到长度为n的归并结果 排序码比较5次 22[6[02[62[68 排序码比较6次 2121630 10162028 排序码比较7次 20121616202301 排序码比较9次 匚2610121616·8202830 9-3在起泡排序过程中,什么情况下排序码会朝向与排序相反的方向移动,试举例说明。在 快速排序过程中有这种现象吗? 【解答】 如果在待排序序列的后面的若干排序码比前面的排序码小,则在起泡排序的过程中,排 序码可能向与最终它应移向的位置相反的方向移动。例如
第 9 章 排序 6 交换 0# 与 4# 对象 从 0# 到 3# 重新形成堆 交换 0# 与 3# 对象 从 0# 到 2# 重新形成堆 交换 0# 与 2# 对象 从 0# 到 1# 重新形成堆 交换 0# 与 1# 对象 从 0# 到 1# 重新形成堆，得到结果 (8) 二路归并排序 采用迭代的方法进行归并排序。设待排序的数据对象有 n 个。首先把每一个待排序的数 据对象看作是长度为的初始归并项，然后进行两两归并，形成长度为 2 的归并项，再对它们 两两归并，形成长度为 4 的归并项，如此一趟一趟做下去，最后得到长度为 n 的归并结果。 9-3 在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在 快速排序过程中有这种现象吗？ 【解答】 如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排 序码可能向与最终它应移向的位置相反的方向移动。例如， 10 6 2 12 16 16* 20 28 30 18 2 6 10 12 16 16* 20 28 30 18 6 2 10 12 16 16* 20 28 30 18 2 6 10 12 16 16* 20 28 30 18 2 6 10 12 16 16* 20 28 30 18 12 2 16 30 28 10 16* 20 6 18 2 12 16 30 10 28 16* 20 12 6 18 2 12 16 30 10 16* 20 28 6 18 2 10 12 16 16 6 18 * 20 28 30 2 6 10 12 16 16* 18 20 28 30 排序码比较 5 次 排序码比较 6 次 排序码比较 7 次 排序码比较 9 次
非序 540、3、、头197如9向相反方向移动 4875、7199如19向相反方向移动 919如9向最终方向移动 34 如13向相反方向移动 6791157 1319344875如13向最终方向移动 679111354334487如4向相反方向移动 679111319 38344875 679111319345740384875 9-4试修改起泡排序算法,在正反两个方向交替进行扫描,即第一趟把排序码最大的对象放 到序列的最后,第二趟把排序码最小的对象放到序列的最前面。如此反复进行 【解答1】 template void dataList : shaker Sort(i 奇数趟对表 Vector从前向后,比较相邻的排序码,遇到逆序即交换,直到把参加比较排序码序列 ∥中最大的排序码移到序列尾部。偶数趟从后向前,比较相邻的排序码,遇到逆序即交换,直到把 ∥参加比较排序码序列中最小的排序码移到序列前端。 int i=l, j; int exchange; while( i=i;j--) ∥逆向起泡 if( Vector[j-1>Vector])t ∥发生逆序 Swap( VectorJj-1] Vector]); ∥交换,最小排序码放在 Vector[1处 exchange =1: ∥做“发生了交换”标志 if( exchange =0)break; m当 exchange为0则停止排序 for (j=1;j Vector[+1)i Swap( vector[, Vector [+1; ∥交换,最大排序码放在 ector处 exchange =1: ∥做“发生了交换”标志 if( exchange ==0) break; ∥当 exchange为0则停止排序 【解答2】 template void dataList: shaker Sort(t int low=l, high=Currents ize-l, i, j; int exchange; while( low high)( ∥当比较范围多于一个对象时排序 ∥记忆元素交换位置 for (i=lov ∥正向起泡 if( Vector[>Vector[i+1])i ∥发生逆序 Swap( Vector[i], Vector[i+1]); ∥交换 记忆右边最后发生交换的位置j ∥比较范围上界缩小到j 7
第 9 章 排序 7 57 40 38 11 13 34 48 75 6 19 9 7 如 9 向相反方向移动 6 57 40 38 11 13 34 48 75 7 19 9 如 19 向相反方向移动 6 7 57 40 38 11 13 34 48 75 9 19 如 9 向最终方向移动 6 7 9 57 40 38 11 13 34 48 75 19 如 13 向相反方向移动 6 7 9 11 57 40 38 13 19 34 48 75 如 13 向最终方向移动 6 7 9 11 13 57 40 38 19 34 48 75 如 34 向相反方向移动 6 7 9 11 13 19 57 40 38 34 48 75 6 7 9 11 13 19 34 57 40 38 48 75 9-4 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把排序码最大的对象放 到序列的最后，第二趟把排序码最小的对象放到序列的最前面。如此反复进行。 【解答 1】 template void dataList :: shaker_Sort ( ) { //奇数趟对表 Vector 从前向后, 比较相邻的排序码, 遇到逆序即交换, 直到把参加比较排序码序列 //中最大的排序码移到序列尾部。偶数趟从后向前, 比较相邻的排序码, 遇到逆序即交换, 直到把 //参加比较排序码序列中最小的排序码移到序列前端。 int i = 1, j; int exchange; while ( i = i; j-- ) //逆向起泡 if ( Vector[j-1] > Vector[j] ) { //发生逆序 Swap ( Vector[j-1], Vector[j] ); //交换, 最小排序码放在 Vector[i-1]处 exchange = 1; //做“发生了交换”标志 } if ( exchange == 0 ) break; ////当 exchange 为 0 则停止排序 for ( j = i; j Vector[j+1] ) { //发生逆序 Swap ( Vector[j], Vector[j+1] ); //交换, 最大排序码放在 Vector[n-i]处 exchange = 1; //做“发生了交换”标志 } if ( exchange == 0 ) break; //当 exchange 为 0 则停止排序 i++; } } 【解答 2】 template void dataList :: shaker_Sort ( ) { int low = 1, high = CurrentSize-1, i, j; int exchange; while ( low Vector[i+1] ) { //发生逆序 Swap ( Vector[i], Vector[i+1] ); //交换 j = i; //记忆右边最后发生交换的位置 j } high = j; //比较范围上界缩小到 j
非序 for i=high; i>low; i--) ∥反向起泡 if( Vectori-1>Vector)i ∥发生逆序 Swap( Vector[i-1, Vector); ∥交换 ∥记忆左边最后发生交换的位置j ∥比较范围下界缩小到 9-5如果待排序的排序码序列已经按非递减次序有序排列,试证明函数 Quick Sor)的计算 时间将下降到Om2)。 【证明】 若待排序的n个对象的序列已经按排序码非递减次序有序排列,且设排序的时间代价为 T(n)。当以第一个对象作为基准对象时,应用一次划分算法 Partition,通过n-1次排序码比 较,把只能把整个序列划分为:基准对象的左子序列为空序列,右子序列为有n1个对象的 非递减有序序列。对于这样的递归 QuickSort()算法,其时间代价为 T(n)=(n-1)+T(n-1) =(n-1)+{(n-2)+T(n-2)} (n-1)+(n-2)+{(n-3)+T(n-3)} =(n-1)+(n-2)+(n-3)+…+{2+T(1)} =(n-1)+(n-2)+(n-3)+…+2+1 n(n-1)2=O(n2) 9-6在实现快速排序的非递归算法时,可根据基准对象,将待排序排序码序列划分为两个子 序列。若下一趟首先对较短的子序列进行排序,试证明在此做法下,快速排序所需要的栈的 深度为O(logn) 【解答】 由快速排序的算法可知,所需递归工作栈的深度取决于所需划分的最大次数。如果在排 序过程中每次划分都能把整个待排序序列根据基准对象划分为左、右两个子序列。假定这两 个子序列的长度相等,则所需栈的深度为 S(n)=1+S(n/2)= =1+{1+S(n/4)}=2+S(n/4) =2+{1+S(n/8)}=3+S(n/8) logan+ S(1)=log2n (假设1个对象的序列所用递归栈的深度为0) 如果每次递归左、右子序列的长度不等,并且先将较长的子序列的左、右端点保存在递 归栈中,再对较短的子序列进行排序,可用表示最坏情况的大O表示法表示。此时其递归 栈的深度不一定正好是logn,其最坏情况为 O(log2n)。 9-7在实现快速排序算法时,可先检查位于两端及中点的排序码,取三者之中的数值不是最 大也不是最小的排序码作为基准对象。试编写基于这种思想的快速排序算法,并证明对于已 排序的排序码序列,该算法的计算时间为 o(nlog2n) 【解答】参看教科书 9-8在使用非递归方法实现快速排序时,通常要利用一个栈记忆待排序区间的两个端点。那 么能否用队列来代替这个栈?为什么? 【解答】 可以用队列来代替栈。在快速排序的过程中,通过一趟划分,可以把一个待排序区间分
第 9 章 排序 8 for ( i = high; i > low; i-- ) //反向起泡 if ( Vector[i-1] > Vector[i] ) { //发生逆序 Swap ( Vector[i-1], Vector[i] ); //交换 j = i; //记忆左边最后发生交换的位置 j } low = j; //比较范围下界缩小到 j } } 9-5 如果待排序的排序码序列已经按非递减次序有序排列，试证明函数 QuickSort( )的计算 时间将下降到 O(n2 )。 【证明】 若待排序的 n 个对象的序列已经按排序码非递减次序有序排列，且设排序的时间代价为 T(n)。当以第一个对象作为基准对象时，应用一次划分算法 Partition，通过 n-1 次排序码比 较，把只能把整个序列划分为：基准对象的左子序列为空序列，右子序列为有 n-1 个对象的 非递减有序序列。对于这样的递归 QuickSort( )算法，其时间代价为 T(n) = (n-1) + T(n-1) = (n-1) + {( n-2) + T(n-2) } = (n-1) + (n-2) + {(n-3) + T(n-3) } = …… = (n-1) + (n-2) + (n-3) + … + { 2 + T(1) } = (n-1) + (n-2) + (n-3) + … + 2 + 1 = n(n-1)/2 = O(n2 ) 9-6 在实现快速排序的非递归算法时，可根据基准对象，将待排序排序码序列划分为两个子 序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的 深度为 O(log2n)。 【解答】 由快速排序的算法可知,所需递归工作栈的深度取决于所需划分的最大次数。如果在排 序过程中每次划分都能把整个待排序序列根据基准对象划分为左、右两个子序列。假定这两 个子序列的长度相等，则所需栈的深度为 S(n) = 1 + S(n/2) = = 1 + { 1 + S(n/4) } = 2 + S(n/4) = 2 + { 1 + S(n/8) } = 3 + S(n/8) = …… = log2n + S(1) = log2n (假设 1 个对象的序列所用递归栈的深度为 0) 如果每次递归左、右子序列的长度不等，并且先将较长的子序列的左、右端点保存在递 归栈中，再对较短的子序列进行排序，可用表示最坏情况的大 O 表示法表示。此时其递归 栈的深度不一定正好是 log2n，其最坏情况为 O(log2n)。 9-7 在实现快速排序算法时，可先检查位于两端及中点的排序码，取三者之中的数值不是最 大也不是最小的排序码作为基准对象。试编写基于这种思想的快速排序算法，并证明对于已 排序的排序码序列，该算法的计算时间为 O(nlog2n)。 【解答】参看教科书 9-8 在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那 么能否用队列来代替这个栈? 为什么? 【解答】 可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分
非序 为两个子区间,然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间 保存另一个子区间的上界和下界,待该区间处理完成后再从栈中取出另一子区间的边界, 其进行处理。这个功能利用队列也可以实现,只不过是处理子区间的顺序有所变动而已。 99试设计一个算法,使得在On)的时间内重排数组将所有取负值的排序码排在所有取正 值(非负值)的排序码之前 【解答】 template void reArrange( dataList&L) ∥数组元素类型Type只可能取int或noat nt i=0,j=Llength 0-1; while(i=j)t while([]- getKey()=0)j- swap([,Lo]); 9-10奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描,第二趟 对序列中的所有偶数项i扫描。若A[>A[i+1],则交换它们。第三趟有对所有的奇数项, 第四趟对所有的偶数项,…,如此反复,直到整个序列全部排好序为止。 (1)这种排序方法结束的条件是什么? (2)写出奇偶交换排序的算法 (3)当待排序排序码序列的初始排列是从小到大有序,或从大到小有序时,在奇偶交换 排序过程中的排序码比较次数是多少? 【解答】 (1)设有一个布尔变量 exchange,判断在每一次做过一趟奇数项扫描和一趟偶数项扫描 后是否有过交换。若 exchange=1,表示刚才有过交换,还需继续做下一趟奇数项扫描和 趟偶数项扫描;若 exchange=0,表示刚才没有交换,可以结束排序 (2)奇偶排序的算法 emplate void dataList: odd-even Sort (i int i, exchange do i exchange =0: for (i=l; i Vector[i+ID)t ∥相邻两项比较,发生逆序 ∥作交换标记 swap( Vector, Vector+1);W交换 for(i=0 ∥扫描所有偶数项 f( Vector[> Vector[i+1)& ∥相邻两项比较,发生逆序 ∥作交换标记 swap( Vector, Vector[i+1]) ∥交换 i while( exchange I=0);
第 9 章 排序 9 为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区间时， 保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对 其进行处理。这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。 9-9 试设计一个算法, 使得在 O(n)的时间内重排数组, 将所有取负值的排序码排在所有取正 值(非负值)的排序码之前。 【解答】 template void reArrange ( dataList& L ) { //数组元素类型 Type 只可能取 int 或 float int i = 0, j = L.length () – 1; while ( i != j ) { while ( L[i].getKey( ) = 0 ) j--; swap ( L[i], L[j] ); i++; j--; } } 9-10 奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项 i 扫描，第二趟 对序列中的所有偶数项 i 扫描。若 A[i] > A[i+1]，则交换它们。第三趟有对所有的奇数项， 第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。 (1) 这种排序方法结束的条件是什么？ (2) 写出奇偶交换排序的算法。 (3) 当待排序排序码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换 排序过程中的排序码比较次数是多少？ 【解答】 (1) 设有一个布尔变量 exchange，判断在每一次做过一趟奇数项扫描和一趟偶数项扫描 后是否有过交换。若 exchange = 1，表示刚才有过交换，还需继续做下一趟奇数项扫描和一 趟偶数项扫描；若 exchange = 0，表示刚才没有交换，可以结束排序。 (2) 奇偶排序的算法 template void dataList :: odd-evenSort ( ) { int i, exchange; do { exchange = 0; for ( i = 1; i Vector[i+1] ) { //相邻两项比较, 发生逆序 exchange = 1; //作交换标记 swap ( Vector[i], Vector[i+1] ); //交换 } for ( i = 0; i Vector[i+1] ) { //相邻两项比较, 发生逆序 exchange = 1; //作交换标记 swap ( Vector[i], Vector[i+1] ); //交换 } } while ( exchange != 0 );
非序 (3)设待排序对象序列中总共有n个对象。序列中各个对象的序号从0开始。则当所有 待排序对象序列中的对象按排序码从大到小初始排列时,执行m=L(n+1)2」趟奇偶排序。 当所有待排序对象序列中的对象按排序码从小到大初始排列时,执行1趟奇偶排序。 在一趟奇偶排序过程中,对所有奇数项扫描一遍,排序码比较L(n-1)2」次;对所有偶 数项扫描一遍,排序码比较Ln/2」次。所以每趟奇偶排序两遍扫描的结果,排序码总比较次 数为L(n-1)2」+Ln/2」=n-1 9-11请编写一个算法,在基于单链表表示的待排序排序码序列上进行简单选择排序 【解答】 采用静态单链表作为存储表示。用 Vector[0]作为表头结点,各待排序数据对象从 Vector[1 开始存放。算法的思想是每趟在原始链表中摘下排序码最大的结点(几个排序码相等时为最 前面的结点),把它插入到结果链表的最前端。由于在原始链表中摘下的排序码越来越小, 在结果链表前端插入的排序码也越来越小,最后形成的结果链表中的结点将按排序码非递减 的顺序有序链接 Template void staticlinkList : selectsort (4 t h= Vector[o].link, p, q,r,s; ile( hI=0)i ∥原始链表未扫描完 p=s=h: q=r=0; nile(p=0)i ∥扫描原始链表,寻找排序码最大的结点s ir( Vector]data> Vector[s]data)∥记忆当前找到的排序码最大结点 q=p; p=Vector[p]. link if(s==h)h=vector]: ∥排序码最大的结点是原始链表前端结点,摘下 else Vector[[].link= Vector[s].link: ∥排序码最大的结点是原始链表表中结点,摘下 Vector[s]. link Vector[o]. link: ∥结点s插入到结果链表的前端 Vector[o].link 9-12手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个排序码后堆 的变化 (1)按字母顺序排序:Tim,Dot,Eva,Rom,Kim,Guy, Ann . Jim,Kay,Ron,Jan (2)按数值递增顺序排序:26,33,35,29,19,12,22 (3)同样7个数字,换一个初始排列,再按数值的递增顺序排序:12,19,33,26,29,35,22 【解答】为节省篇幅,将用数组方式给出形成初始堆和进行堆排序的变化结果。阴影部分表 示参与比较的排序码。请读者按照完全二叉树的顺序存储表示画出堆的树形表示 (1)按字母顺序排序 形成初始堆(按最大堆) Tim Dot Eva Rom Kim Jim Kay Ro F4 Tim Dot Eva Rom Ron Ann Jim Kay Kim Jan I
第 9 章 排序 10 } (3) 设待排序对象序列中总共有 n 个对象。序列中各个对象的序号从 0 开始。则当所有 待排序对象序列中的对象按排序码从大到小初始排列时，执行 m = (n+1)/2 趟奇偶排序。 当所有待排序对象序列中的对象按排序码从小到大初始排列时，执行 1 趟奇偶排序。 在一趟奇偶排序过程中，对所有奇数项扫描一遍，排序码比较 (n-1)/2 次；对所有偶 数项扫描一遍，排序码比较 n/2 次。所以每趟奇偶排序两遍扫描的结果，排序码总比较次 数为 (n-1)/2 + n/2 = n-1。 9-11 请编写一个算法，在基于单链表表示的待排序排序码序列上进行简单选择排序。 【解答】 采用静态单链表作为存储表示。用Vector[0]作为表头结点，各待排序数据对象从Vector[1] 开始存放。算法的思想是每趟在原始链表中摘下排序码最大的结点(几个排序码相等时为最 前面的结点)，把它插入到结果链表的最前端。由于在原始链表中摘下的排序码越来越小， 在结果链表前端插入的排序码也越来越小，最后形成的结果链表中的结点将按排序码非递减 的顺序有序链接。 Template void staticlinkList :: selectSort ( ) { int h = Vector[0].link, p, q, r, s; Vector[0].link = 0; while ( h != 0 ) { //原始链表未扫描完 p = s = h; q = r = 0; while ( p != 0 ) { //扫描原始链表, 寻找排序码最大的结点 s if ( Vector[p].data > Vector[s].data ) //记忆当前找到的排序码最大结点 { s = p; r = q; } q = p; p = Vector[p].link; } if ( s == h ) h = Vector[h]; //排序码最大的结点是原始链表前端结点, 摘下 else Vector[r].link = Vector[s].link; //排序码最大的结点是原始链表表中结点, 摘下 Vector[s].link = Vector[0].link; //结点 s 插入到结果链表的前端 Vector[0].link = s; } } 9-12 手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个排序码后堆 的变化。 (1) 按字母顺序排序：Tim, Dot, Eva, Rom, Kim, Guy, Ann, Jim, Kay, Ron, Jan (2) 按数值递增顺序排序：26, 33, 35, 29, 19, 12, 22 (3) 同样 7 个数字，换一个初始排列，再按数值的递增顺序排序：12, 19, 33, 26, 29, 35, 22 【解答】为节省篇幅，将用数组方式给出形成初始堆和进行堆排序的变化结果。阴影部分表 示参与比较的排序码。请读者按照完全二叉树的顺序存储表示画出堆的树形表示。 (1) 按字母顺序排序 形成初始堆（按最大堆） 0 1 2 3 4 5 6 7 8 9 10 Tim Dot Eva Rom Kim Guy Ann Jim Kay Ron Jan i=4 Tim Dot Eva Rom [ Ron Guy Ann Jim Kay Kim Jan ]