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

第九章排序 概述 插入排序 快速排序 交换排序(起泡排序) 选择排席 归并排序

第九章 排序 • 概述 • 插入排序 • 快速排序 • 交换排序（起泡排序） • 选择排序 • 归并排序 1

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

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

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

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

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

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

待排序数据表的类定义 #include const int Defaultsize =100 template class element i /数据表元素定义 public C tkey 排序码 field otherdata 其他数据成员 Element& operator=(Element& xi key =x key; otherdata=x otherdata; return this

待排序数据表的类定义 #include const int DefaultSize = 100; template class Element { //数据表元素定义 public: T key; //排序码 field otherdata; //其他数据成员 Element& operator = (Element& x) { key = x.key; otherdata = x.otherdata; return this; } 5

bool operator==(Element&x { return key=xkey;}thi与x相等 bool operator & x) { return key=(Element& x) { return key>=xkey;}判this大于或等于x bool operator >(Element& x) { return key>xkey;}判this大于x bool operator&x) { return key<xkey;}判thi小于x

bool operator == (Element& x) { return key == x.key; } //判*this与x相等 bool operator & x) { return key = (Element& x) { return key >= x.key; } //判*this大于或等于x bool operator > (Element& x) { return key > x.key; } //判*this大于x bool operator & x) { return key < x.key; } //判*this小于x }; 6

template class datalist i /数据表类定义 rivate Element * vector: )存储排序元素的向量 int maxsize; /向量中最大元素个数 int currentSize ∥/前元素个数 public datalist( int maXSz= DefaultSize):∥构造函数 maxSize( maxSz), currentSize(0) i Vector= new element[maxSize];) int Length{ return currentsize;}∥取表长度

template class dataList{ //数据表类定义 private: Element * Vector; //存储排序元素的向量 int maxSize; //向量中最大元素个数 int currentSize; //当前元素个数 public: datalist (int maxSz = DefaultSize) : //构造函数 maxSize(maxSz), currentSize(0) { Vector = new Element[maxSize]; } int Length() { return currentSize; } //取表长度 7

void Swap(Element& x, Element& y) f Element temp=x;x=y; y=temp; j Element<>& operator](inti)/取第个元素 freturn Vector; int Partition(const int low, const int high) 快速排序划分

void Swap (Element& x, Element& y) { Element temp = x; x = y; y = temp; } Element& operator [](int i) //取第i个元素 { return Vector[i]; } int Partition (const int low, const int high); //快速排序划分 }; 8

插入排序( Insert Sorting) 基本方法是:每步将一个待排序的元素,按其排序 码大小,插入到前面已经排好序的一组元素的适当 位置上,直到元素全部插入为止。 直接插入排序 折芊插入排序 希尔排序

插入排序 (Insert Sorting) • 基本方法是：每步将一个待排序的元素，按其排序 码大小，插入到前面已经排好序的一组元素的适当 位置上, 直到元素全部插入为止。 – 直接插入排序 – 折半插入排序 – 希尔排序 9

直接插入排序( nsert Sort) 基本思想是 当插入第i(i≥1)个元素时,前面的v0,V1l,…, V[i-1已经排好序。这时,用V训的排序码与Vi 1lv[i-2,的排序码顺序进行比较,找到插入位 置即将V插入,原来位置上的元素向后顺移

• 基本思想是 : 当插入第i (i≥1) 个元素时，前面的V[0], V[1], …, V[i-1]已经排好序。这时，用V[i]的排序码与V[i- 1], V[i-2], …的排序码顺序进行比较，找到插入位 置即将V[i]插入，原来位置上的元素向后顺移。 10 直接插入排序 (Insert Sort)