1、第 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; /将当前结点的排序码修改为 xElem
2、ent otherdata = x-otherdata; int operator = ( Type /判 this 与 x 相等int operator key; /判 this 小于或等于 xint operator ( Type /判 this 大于 xint operator x-key; /判 this 小于 xtemplate class dataList /用顺序表来存储待排序的元素，这些元素的类型是 Typeprivate:Element * Vector; /存储待排序元素的向量int MaxSize, CurrentSize; /最大元素个数与当前元素个数int Parti
3、tion ( const int low, const int high ) /用于快速排序的一次划分算法public:datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) Vector = new Element MaxSize; /构造函数int length ( ) return CurrentSize; Element void swap ( Element x = y; y = temp; void Sort ( ); /排序静态链表类定义template class staticlinkL
4、ist; /静态链表类的前视声明 template class Element /静态链表元素类的定义friend class staticlinkList;private:第 9 章 排序2Type key; /排序码，其它信息略int link; /结点的链接指针public:Type getKey ( ) return key; /取当前结点的排序码void setKey ( const Type x ) key = x; /将当前结点的排序码修改为 xint getLink ( ) return link; /取当前结点的链接指针void setLink ( const int ptr
5、 ) link = ptr; /将当前结点的链接指针置为 ptrtemplate class staticlinkList /静态链表的类定义private:Element *Vector; /存储待排序元素的向量int MaxSize, CurrentSize; /向量中最大元素个数和当前元素个数public:dstaticlinkList ( int Maxsz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) Vector = new Element Maxsz; 9-1 什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么
6、排序方法是不稳定的? 【解答】内排序是排序过程中参与排序的数据全部在内存中所做的排序，排序过程中无需进行内外存数据传送，决定排序方法时间性能的主要是数据排序码的比较次数和数据对象的移动次数。外排序是在排序的过程中参与排序的数据太多，在内存中容纳不下，因此在排序过程中需要不断进行内外存的信息传送的排序。决定外排序时间性能的主要是读写磁盘次数和在内存中总的记录对象的归并次数。不稳定的排序方法主要有希尔排序、直接选择排序、堆排序、快速排序。不稳定的排序方法往往是按一定的间隔移动或交换记录对象的位置，从而可能导致具有相等排序码的不同对象的前后相对位置在排序前后颠倒过来。其他排序方法中如果有数据交换，只
7、是在相邻的数据对象间比较排序码，如果发生逆序(与最终排序的顺序相反的次序)才交换，因此具有相等排序码的不同对象的前后相对位置在排序前后不会颠倒，是稳定的排序方法。但如果把算法中判断逆序的比较“(或 void dataList : shaker_Sort ( ) /奇数趟对表 Vector 从前向后, 比较相邻的排序码, 遇到逆序即交换, 直到把参加比较排序码序列/中最大的排序码移到序列尾部。偶数趟从后向前, 比较相邻的排序码, 遇到逆序即交换, 直到把/参加比较排序码序列中最小的排序码移到序列前端。int i = 1, j; int exchange;while ( i = i; j- ) /
8、逆向起泡if ( Vectorj-1 Vectorj ) /发生逆序Swap ( Vectorj-1, Vectorj ); /交换, 最小排序码放在 Vectori-1处exchange = 1; /做“发生了交换”标志if ( exchange = 0 ) break; /当 exchange 为 0 则停止排序for ( j = i; j Vectorj+1 ) /发生逆序Swap ( Vectorj, Vectorj+1 ); /交换, 最大排序码放在 Vectorn-i处exchange = 1; /做“发生了交换”标志if ( exchange = 0 ) break; /当 ex
9、change 为 0 则停止排序i+;【解答 2】template void dataList : shaker_Sort ( ) int low = 1, high = CurrentSize-1, i, j; int exchange;while ( low Vectori+1 ) /发生逆序Swap ( Vectori, Vectori+1 ); /交换j = i; /记忆右边最后发生交换的位置 jhigh = j; /比较范围上界缩小到 j第 9 章 排序10for ( i = high; i low; i- ) /反向起泡if ( Vectori-1 Vectori ) /发生逆序S
10、wap ( Vectori-1, Vectori ); /交换j = i; /记忆左边最后发生交换的位置 jlow = j; /比较范围下界缩小到 j9-5 如果待排序的排序码序列已经按非递减次序有序排列，试证明函数 QuickSort( )的计算时间将下降到 O(n2)。【证明】若待排序的 n 个对象的序列已经按排序码非递减次序有序排列，且设排序的时间代价为 T(n)。当以第一个对象作为基准对象时，应用一次划分算法 Partition，通过 n-1 次排序码比较，把只能把整个序列划分为：基准对象的左子序列为空序列，右子序列为有 n-1 个对象的非递减有序序列。对于这样的递归 QuickSor
11、t( )算法，其时间代价为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)。【解答】由快速排序的算法可知,所需递归工作栈
12、的深度取决于所需划分的最大次数。如果在排序过程中每次划分都能把整个待排序序列根据基准对象划分为左、右两个子序列。假定这两个子序列的长度相等，则所需栈的深度为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 在使用非递归方法实现快速排序时, 通常要利用一个栈记忆待排序区间的两个端点。那么能否用队列来代替这个栈? 为什么?【解答】可以用队列来代替栈。在快速排序的过程中，通过一趟划分，可以把一个待排序区间分为两个子区间，然后分别对这两个子区间施行同样的划分。栈的作用是在处理一个子区
