第九章排序 .概述 插入排序 快速排序 交换排序（起泡排序） 。 选择排序 。归进排序
第九章 排序 • 概述 • 插入排序 • 快速排序 • 交换排序（起泡排序） • 选择排序 • 归并排序 1
概述 .排序：将一组杂乱无章的数据按一定的规律顺次 排列起来。 数据表(datalist:它是待排序数据元素的有限集合。 排序码k小：通常数据元素有多个属性域，即多个 数据成员组成，其中有一个属性域可用来区分元素， 作为排序依据。该域即为排序码。每个数据表用 哪个属性域作为排序码，要视具体的应用需要而 定。 2
概述 • 排序：将一组杂乱无章的数据按一定的规律顺次 排列起来。 • 数据表(datalist): 它是待排序数据元素的有限集合。 • 排序码(key): 通常数据元素有多个属性域, 即多个 数据成员组成, 其中有一个属性域可用来区分元素, 作为排序依据。该域即为排序码。每个数据表用 哪个属性域作为排序码，要视具体的应用需要而 定。 2
.排序算法的稳定性：如果在元素序列中有两个元 素r[和[，它们的排序码心=k,且在排序之 前，元素排在1前面。如果在排序之后，元素 仍在元素的前面，则称这个排序方法是稳定 的，否则称这个排序方法是不稳定的。 内排序与外排序：内排序是指在排序期间数据元 素全部存放在内存的排序；外排序是指在排序期 间全部元素个数太多，不能同时存放在内存，必 须根据排序过程的要求，不断在内、外存之间移 动的排序。 3
• 排序算法的稳定性: 如果在元素序列中有两 个元 素r[i]和r[j], 它们的排序码 k[i] == k[j] , 且在排序之 前, 元素r[i]排在r[j]前面。如果在排序之后, 元素 r[i]仍在元素r[j]的前面, 则称这个排序方法是稳定 的, 否则称这个排序方法是不稳定的。 • 内排序与外排序: 内排序是指在排序期间数据元 素全部存放在内存的排序；外排序是指在排序期 间全部元素个数太多，不能同时存放在内存，必 须根据排序过程的要求，不断在内、外存之间移 动的排序。 3
排序的时间开销：排序的时间开销是衡量算法好 坏的最重要的标志。排序的时间开销可用算法执 行中的数据比较次数与数据移动次数来衡量。 算法运行时间代价的大略估算一般都按平均情况 进行估算。对于那些受元素排序码序列初始排列 及元素个数影响较大的算法，需要按最好情况和 最坏情况进行估算。 算法执行时所需的附加存储： 评价算法好坏的另 一标准。 4
• 排序的时间开销: 排序的时间开销是衡量算法好 坏的最重要的标志。排序的时间开销可用算法执 行中的数据比较次数与数据移动次数来衡量。 • 算法运行时间代价的大略估算一般都按平均情况 进行估算。对于那些受元素排序码序列初始排列 及元素个数影响较大的算法，需要按最好情况和 最坏情况进行估算。 • 算法执行时所需的附加存储: 评价算法好坏的另 一标准。 4
待排序数据表的类定义 #include <iostream.h> const int DefaultSize =100; template <class T> class Element 川数据表元素定义 public: T key; /排序码 field otherdata; /川其他数据成员 Element<T>&operator=(Element<T>&x){ key =x.key;otherdata=x.otherdata; return this; 5
待排序数据表的类定义 #include <iostream.h> const int DefaultSize = 100; template <class T> class Element { //数据表元素定义 public: T key; //排序码 field otherdata; //其他数据成员 Element<T>& operator = (Element<T>& x) { key = x.key; otherdata = x.otherdata; return this; } 5