第9章排序 Type key ∥排序码,其它信息略 ∥结点的链接指针 Type getKey (i return key:) 取当前结点的排序码 void setKey( const Type x){key=x;}/将当前结点的排序码修改为x ink(return link; ∥取当前结点的链接指针 void setlink( const int ptr){link=ptr;}将当前结点的链接指针置为p template <class Type> class staticlinklist i 静态链表的类定义 ement <Type>*Vector; ∥储待排序元素的向量 int MaxSize, Currents ize 向量中最大元素个数和当前元素个数 dstaticlinkList( int Maxsz=DefaultSize ) MaxSize( Maxsz ) CurrentSize(0) i Vector=new Element <Type>[Maxsz:1 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 1=2[212]163028101620618 16]3028101620618 1630128101620618 i=5[212、16、28、30]1016′20618 i=7[210121616283012061 11125333 8[210、12、16、16:、20、28、30]618第 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