第9章排序 第9章排序 静态数据表类定义 #include <iostream. h> 0; template <class Type> class dataList ∥数据表的前视声明 template <class Type> class Element i ∥数据表元素类的定义 friend class dataList <Type> Type key; ∥排序码 field otherdata: ∥其它数据成员 public Type getKey (i return key: j 取当前结点的排序码 void setKey( const Type x )ikey =x;j ∥将当前结点的排序码修改为 Element.<Iype>& operator=( Elements<lype>&x)w结点x的值赋给thi 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 i ∥用顺序表来存储待排序的元素,这些元素的类型是Type private Element <Type>* 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 <Type>[MaxSize:) ∥构造函数 int length(( return CurrentSize: j Element<Type>& operator [(int i return Vector;) void swap( Element<Iype>&x, Element<Iype>&y)∥交换x,y Element <Type>temp=x; x=y; y=temp: j oid Sort (; 静态链表类定义 template <class Type> class staticlinkList; 静态链表类的前视声明 template <class Type> class Element i /静态链表元素类的定义 friend class staticlinkList<Type> private
第 9 章 排序 1 第 9 章 排序 静态数据表类定义 #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:
第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 Type> class staticlinklist i 静态链表的类定义 ement <Type>*Vector; ∥储待排序元素的向量 int MaxSize, Currents ize ∥量中最大元素个数和当前元素个数 dstaticlinkList( int Maxsz= DefaultSize ) Max Size( Maxsz ) CurrentSize(0) i 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)二路归并排序 (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 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) 二路归并排序 (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