第9章排序 第9章排序 静态数据表类定义 #include 0; template class dataList ∥数据表的前视声明 template class Element i ∥数据表元素类的定义 friend class dataList Type key; ∥排序码 field otherdata: ∥其它数据成员 public Type getKey (i return key: j 取当前结点的排序码 void setKey( const Type x )ikey =x;j ∥将当前结点的排序码修改为 Element.& operator=( Elements&x)w结点x的值赋给thi int operator==(Type&x){ return key=x->key;}判this与x相等 int operatorkey;}判this小于或等于x int operator>(Type&x){ return key>x->key;}消this大于x int operatorx->key;}消判this小于x template class dataList i ∥用顺序表来存储待排序的元素,这些元素的类型是Type private Element * Vector; ∥存储待排序元素的向量 It maxSize Currentsize 最大元素个数与当前元素个数 int Partition( const int low, const int high) 用于快速排序的一次划分算法 public datalist int MaxSz= DefaultSize ) MaxSize( Maxsz ) CurrentSize(0) i Vector=new Element [MaxSize:) ∥构造函数 int length(( return CurrentSize: j Element& operator [(int i return Vector;) void swap( Element&x, Element&y)∥交换x,y Element temp=x; x=y; y=temp: j oid Sort (; 静态链表类定义 template class staticlinkList; 静态链表类的前视声明 template class Element i /静态链表元素类的定义 friend class staticlinkList private
第 9 章 排序 1 第 9 章 排序 静态数据表类定义 #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:
第9章排序 Type key ∥排序码,其它信息略 ∥结点的链接指针 Type getKey (i return key:) 取当前结点的排序码 void setKey( const Type x )key=x; ∥将当前结点的排序码修改为x retu 取当前结点的链接指针 void setlink( const int pt){lmk=ptr;}将当前结点的链接指针置为pr template class staticlinklist i 静态链表的类定义 ement *Vector; ∥储待排序元素的向量 int MaxSize, Currents ize ∥量中最大元素个数和当前元素个数 dstaticlinkList( int Maxsz= DefaultSize ) Max Size( Maxsz ) CurrentSize(0) i 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)二路归并排序 (9)基数排序 【解答】 )直接插入排序 初始排列0123456789排序码比较次数 1[1212163028101620618 i=2[212]163028101620618 16]3028101620618 1112 16301281016 30]、1016 1=6[210121628、30l、162061 8[210、12、16、16:、20、28、30]618 333
第 9 章 排序 2 Type key; //排序码，其它信息略 int link; //结点的链接指针 public: 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) 二路归并排序 (9) 基数排序 【解答】 (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
第9章排序 i=9[261012161620、2830]、18 (2)希尔排序(增量为5,2,1) 初始排列0123456789排序码比较次数 1221630281016,206181+1+1+1+1=5 102166181216203028(1+1+2+1)+(1+1 +1+1)=9 1021661612182030281+1+3+1+3+1+1 +1+2=14 6 12161618202830 希尔(she)本人采取的增量序列为Ln/21ln/2y2un/2y2y21…1。一般地,增量 序列可采用 na luna ja lna」a」a」…,1。大量实验表明,取a=045454的增量序列 比取其他的增量序列的优越性更显著。计算L045454n」的一个简单方法是用整数算术计算 (5*n-1)/1l。需要注意,当α<12时,增量序列可能不以1结束,需要加以判断和调整。 (3)起泡排序 初始排列0 排序码比较次数 101620618 2[12 26[120163028,161820 [16’18 [18202 (4)快速排序 Pivot Pvtpos 89排序码比较次数 2810 pos I pos I pos I pos 6,7,8[2]6[10]12I 184,5,626101218161620128[30 I pos Ipos I pos 61012I1616l18[20
第 9 章 排序 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 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 pos pos pos pos pos pos pos pos pos pos pos pos pos pos pos
第9章排序 左子序列递归深度为1,右子序列递归深度为3。 (5)直接选择排序 初始排列0123456789排序码比较次数 0[1221630 61012[2816 3018] 6101216[28162 18] 2 610121616[28203018 2 610121616162028[30 (6)锦标赛排序 输出2,调整胜者树 当参加排序的数据对象个数n不足2的某次幂时,将其补足到2的某次幂。本题的 10,将叶结点个数补足到24=16个。排序码比较次数=9。 输出6,调整胜者树
第 9 章 排序 4 2 6 10 12 16* [ 16 ] 18 20 28 30 左子序列递归深度为 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) 锦标赛排序 当参加排序的数据对象个数 n 不足 2 的某次幂时，将其补足到 2 的某次幂。本题的 n = 10，将叶结点个数补足到 2 4 = 16 个。排序码比较次数 = 9。 12 2 16 30 28 10 16* 20 6 18 2 2 2 2 6 6 6 16 10 10 16* 输出 2，调整胜者树 12 12 10 6 6 6 6 16 10 10 16* 输出 6，调整胜者树
第9章排序 回囫画囫卤国□口□ 输出10,调整胜者树 排序码比较 次数 当某结点的比较对手的参选标志为“不再参选”,该结点自动升入双亲结点,此动作不 计入排序码比较次数。 输出12,调整胜者树 排序码比较 次数=3 回自凶回画回回口亡画白口□ 排序码比较次数=3。某对象输出后,对手自动升到双亲,不计入排序码比较次数。 ④输出16,调整胜者树 排序码比较 次数 回囱凶回囟回的回囟 2品品 输出16,调整胜者树 排序码比较 次数=2 输出18,调整胜者树 排序码比较 次数=3
第 9 章 排序 5 当某结点的比较对手的参选标志为“不再参选”，该结点自动升入双亲结点，此动作不 计入排序码比较次数。 排序码比较次数=3。某对象输出后，对手自动升到双亲，不计入排序码比较次数。 12 2 16 30 28 10 16* 20 6 18 输出 10，调整胜者树 12 2 16 30 28 10 16* 20 6 18 12 12 10 10 18 18 18 16 10 10 16* 排序码比较 次数 = 1。 输出 12，调整胜者树 12 2 16 30 28 10 16* 20 6 18 12 12 12 12 18 18 18 16 28 16* 排序码比较 次数 = 3。 16* 输出 16，调整胜者树 12 2 16 30 28 10 16* 20 6 18 12 16 16 16 18 18 18 16 28 16* 排序码比较 次数 = 2。 16* 输出 16*，调整胜者树 12 2 16 30 28 10 16* 20 6 18 12 30 18 18 18 30 28 16* 排序码比较 次数 = 2。 16* 16* 16* 输出 18，调整胜者树 30 18 18 排序码比较 次数 = 3。 20 18 20
第9章排序 输出20,调整胜者树 排序码比较 次数=0 输出28,调整胜者树 排序码比较 次数=2 输出30,排序完成 排序码比较 次数=0 包圖回函回应鹵口亡 7)堆排序 第一步,形成初始的最大堆(略),第二步,做堆排序 初始排列,不是最大堆 形成初始最大堆 交换0与9对象
第 9 章 排序 6 (7) 堆排序 第一步，形成初始的最大堆 (略)，第二步，做堆排序。 初始排列，不是最大堆 形成初始最大堆 交换 0 # 与 9 # 对象 12 2 16 30 28 10 16* 20 6 18 12 30 28 20 18 输出 20，调整胜者树 12 2 16 30 28 10 16* 20 6 18 12 30 18 18 18 30 28 20 排序码比较 次数 = 0。 20 20 20 输出 28，调整胜者树 12 2 16 30 28 10 16* 20 6 18 12 30 18 18 18 30 28 20 排序码比较 次数 = 2。 28 28 28 输出 30，排序完成 12 2 16 30 28 10 16* 20 6 18 12 30 18 18 18 30 28 20 排序码比较 次数 = 0。 28 30 30 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* 20 16 12 18 10 16* 28 20 18 16 12 6 10 16*
第9章排序 从0#到8#重新形成堆交换0#与8#对象从0#到7#重新形成堆 (o(8 交换0#与7#对象从O#到6#重新形成堆 换0#与6#对象 710 从O#到5#重新形成堆 交换0#与5#对象 从0#到4#重新形成堆 交换0#与4#对象 从0#到3#重新形成堆 换0#与3#对象 从0#到2#重新形成堆交换O#与2#对象从0#到1#重新形成堆 交换0#与1#对象 从0#到1#重新形成堆,得到结果 7
第 9 章 排序 7 从 0# 到 8# 重新形成堆 交换 0# 与 8# 对象 从 0# 到 7# 重新形成堆 交换 0# 与 7# 对象 从 0# 到 6# 重新形成堆 交换 0# 与 6# 对象 从 0# 到 5# 重新形成堆 交换 0# 与 5# 对象 从 0# 到 4# 重新形成堆 交换 0# 与 4# 对象 从 0# 到 3# 重新形成堆 交换 0# 与 3# 对象 从 0# 到 2# 重新形成堆 交换 0# 与 2# 对象 从 0# 到 1# 重新形成堆 交换 0# 与 1# 对象 从 0# 到 1# 重新形成堆，得到结果 2 6 30 6 2 30 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 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
第9章排序 (8)二路归并排序 采用迭代的方法进行归并排序。设待排序的数据对象有n个。首先把每一个待排序的数 据对象看作是长度为的初始归并项,然后进行两两归并,形成长度为2的归并项,再对它们 两两归并,形成长度为4的归并项,如此一趟一趟做下去,最后得到长度为n的归并结果。 排序码比较5次 21216301028 排序码比较6次 1216301[01620281[618 排序码比较7次 210121616202830 排序码比较9次 2610121616·182 (9)基数排序 12}[2}[16}[30}[28}[0}[16}-[20}-6}□18 按最低位分配 r[]r[2]rB]4]f]r]r7r[8r9 16 [o f 1 f2 f3 f4 f5 f6 f7 f8 f9 收集[30}[10[20}-[12}[2}[16}-[16}[6}[28}[8 按最高位分配 r[o r[ 2]r[r4]rr6]t[7r8]r19 0]t1 2]134]ff6]7f8]9 收集[2[6[10[12[6}[16-}[18}[20-28}[30 9-3在起泡排序过程中,什么情况下排序码会朝向与排序相反的方向移动,试举例说明。在 快速排序过程中有这种现象吗? 【解答】 如果在待排序序列的后面的若干排序码比前面的排序码小,则在起泡排序的过程中,排 序码可能向与最终它应移向的位置相反的方向移动。例如
第 9 章 排序 8 (8) 二路归并排序 采用迭代的方法进行归并排序。设待排序的数据对象有 n 个。首先把每一个待排序的数 据对象看作是长度为的初始归并项，然后进行两两归并，形成长度为 2 的归并项，再对它们 两两归并，形成长度为 4 的归并项，如此一趟一趟做下去，最后得到长度为 n 的归并结果。 (9) 基数排序 收集 按最高位分配 收集 9-3 在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在 快速排序过程中有这种现象吗？ 【解答】 如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排 序码可能向与最终它应移向的位置相反的方向移动。例如， 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 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 16* 2 6 10 12 16 18 20 28 30 排序码比较 5 次 排序码比较 6 次 排序码比较 7 次 排序码比较 9 次
第9章排序 540、3、、头197如9向相反方向移动 75.7 如19 向相反方向 移动 919如9向最终方向移动 13344719如13向相反方向移动 向最 终方向移动 6791113543344875如4向相反方向移动 679111319 38344875 679111319345740384875 9-4试修改起泡排序算法,在正反两个方向交替进行扫描,即第一趟把排序码最大的对象放 到序列的最后,第二趟把排序码最小的对象放到序列的最前面。如此反复进行 【解答1】 template void dataList : shaker Sort(i 奇数趟对表 Vector从前向后,比较相邻的排序码,遇到逆序即交换,直到把参加比较排序码序列 ∥中最大的排序码移到序列尾部。偶数趟从后向前,比较相邻的排序码,遇到逆序即交换,直到把 ∥参加比较排序码序列中最小的排序码移到序列前端。 while( i=i;j--) ∥逆向起泡 if( Vector[j-1>Vector])t ∥发生逆序 Swap( VectorJj-1] Vector]); ∥交换,最小排序码放在 Vector[i-处 exchange =1: ∥做“发生了交换”标志 if( exchange =0)break; m当 exchange为0则停止排序 for (j=1;j Vector[+1)i Swap( vector[, Vector [+1; ∥交换,最大排序码放在 Vector-订处 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
第 9 章 排序 9 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
第9章排序 for i=high; i>low; i--) ∥反向起泡 if( Vectori-1>Vector)i ∥发生逆序 Swap( Vector[i-1 Vector); ∥交换 ∥记忆左边最后发生交换的位置j ∥比较范围下界缩小到 9-5如果待排序的排序码序列已经按非递减次序有序排列,试证明函数 Quick Sor)的计算 时间将下降到Omn2)。 【证明】 若待排序的n个对象的序列已经按排序码非递减次序有序排列,且设排序的时间代价为 T(n)。当以第一个对象作为基准对象时,应用一次划分算法 Partition,通过n-1次排序码比 较,把只能把整个序列划分为:基准对象的左子序列为空序列,右子序列为有n1个对象的 非递减有序序列。对于这样的递归 Quick Sort()算法,其时间代价为 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 章 排序 10 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 在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那 么能否用队列来代替这个栈? 为什么? 【解答】 可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分