福州大学：《数据结构》课程教学资源（PPT课件讲稿）第九章 排序

第九章排序 概述 插入排序 选择排序 归并排序 口基数非序 外推序

概述 排序:将一组杂乱无章的数据按一定的规律 顺次排列起来。 数据表(aai0它是待排序数据对象的有限 集合。 排序码kep:通常数据对象有多个属性域, 即多个数据成员组成,其中有一个属性域可 用来区分对象,作为排序依据。该域即为排 序码。每个数据表用哪个属性域作为排序码, 要视具体的应用需要而定

」排序算法的稳定性:如果在对象序列中有两 个对象叫和m它们的排序码=k,且 在排序之前,对象排在r前面。如果在排 序之后对象叫仍在对象m的前面,则称这 个排序方法是稳定的,否则称这个排序方法 是不稳定的。 内排序与外排序:内排序是指在排序期间 数据对象全部存放在内存的排序;外排序 是指在排序期间全部对象个数太多,不能 同时存放在内存,必须根据排序过程的要 求,不断在内、外存之间移动的排序

」排序的时间开销:排序的时间开销是衡量 算法好坏的最重要的标志。排序的时间开销 可用算法执行中的数据比较次数与数据移动 次数来衡量。 算法运行时间代价的大略估算一般都按平均 情况进行佔算。对于那些受对象排序码序列 初始排列及对象个数影响较大的,需要按最 好情况和最坏情况进行估算。 口算法执行时所需的附加存储:评价算法好 坏的另一标准

待排序数据表的类定义 include const int DefaultSize =100 template class datalist t template class element t friend class dataList; pl rivate. Type key; ∥/排序码 field otherdata:/它数据成员 public Element (: key(0), otherdata(NULL)&

#include const int DefaultSize = 100; template class dataList { template class Element { friend class dataList; private: Type key; //排序码 field otherdata; //其它数据成员 public: Element ( ) : key(0), otherdata(NULL) { }

Type getKey()i return key Element c operators 9= 提取排序码 void setKey( const Type x)(ke y=x;}/修改 赋值 Element&x)i key =x>key otherdata=x->otherdata; 3 int operator ==(Element&x) f return key ==x-key; /this==X int operator &x) f return key &x) return key key;) /Jthis <X

Type getKey ( ) { return key; } //提取排序码 void setKey ( const Type x ) { key = x; } //修改 Element & operator = //赋值 ( Element& x ) { key = x->key; otherdata = x->otherdata; } int operator == (Element& x ) { return key == x->key; } //判this == x int operator & x ) { return key key; } //判this  x int operator & x ) { return key key; } //判this < x

int operator >(Element&x) t return key >x>key; /Jthis >X template class datalist t p rivate Element* Vector;∥存储向量 int maxSize, Currentsize;/大与当前个数 pl ublic. datalist( int Maxsz= Defaultsize ): MaxSize( maxsz ) Currentsize(0 f Vector =new Element[Maxszl:

int operator > (Element& x ) { return key > x->key; } //判this > x } template class dataList { private: Element * Vector; //存储向量 int MaxSize, CurrentSize; //最大与当前个数 public: datalist ( int MaxSz = DefaultSize ) : MaxSize ( Maxsz ), CurrentSize (0) { Vector = new Element [MaxSz]; }

void sort (); /排序 void swap( Element&x,∥对换 Element &y)i Element temp =x; X=y, y= temp

void sort ( ); //排序 void swap ( Element & x, //对换 Element & y ) { Element temp = x; x = y; y = temp; } }

插入排序( Insert Sorting 基本方法是:每步将一个待排序的对象,按 其排序码大小,插入到前面已经排好序的 组对象的适当位置上,直到对象全部插入为止。 直接插入排序( nsert Sort) 基本思想是:当插入第i(≥1)个对象时,前 面的V0V[,,V1]已经排好序。这时, 用V的排序码与V[1,V2],的排序码 顺序进行比较,找到插入位置即将V团插入, 原来位置上的对象向后顺移

各趟排序结 2125 49 25 1回0 2 3 果 i=1 21 49 2511608 2345 temp i=2 21252 25 49 1608 012345 emp

各趟排序结果 0 1 2 3 4 5 0 1 2 3 4 5 temp 25 0 1 2 3 4 5 temp 49