北京师范大学《数据结构——C语言描述》教学课件：第九章 排序

第九章排序 ■概述 插入排序 交换排序 选择排序 归并排序 m外排序

1 ◼ 概述 ◼ 插入排序 ◼ 交换排序 ◼ 选择排序 ◼ 归并排序 ◼ 外排序

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

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

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

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

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

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

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

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

各趟排序结果 6(08 0 23 1团目同同 0 234 5 temp i=2 21|25 49 08 5 temp

6 各 趟 排 序 结 果 21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 08 i = 1 25 0 1 2 3 4 5 temp 21 25 49 25* 16 08 49 i = 2

i=3 212549 62825 0 12345 252549 目同 01234 5 temp i=5 1621 2525*49 5 temp

7 21 25 49 25* 16 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 16 i = 4 08 0 1 2 3 4 5 temp 21 25 49 16 25* 08 i = 5 i = 3 25* 16 08

完成 08]162112525149 0 23 i=4时的排序过程 j=3 21 2525/46 0 1 23 4 5 temp j=221 2525* 49 08 6 2 4 5 temp

8 16 49 16 16 21 25 49 16 25* 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 25 49 25* 08 i = 4 时的排序过程 0 1 2 3 4 5 temp 21 25 25* 49 完成 16 08 16 i = 4 j = 3 i = 4 j = 2

j=121125 252 49 08 16 0 2 j=021 2525 49 08 网 3 temp i=4 j=-1 j园园 2549 08 6 0 2 3 5 temp

9 25 25* 16 16 21 25 49 25* 08 0 1 2 3 4 5 0 1 2 3 4 5 temp 21 49 25* 08 0 1 2 3 4 5 temp 21 25 25* 49 16 08 16 16 25 21 i = 4 j = 1 i = 4 j = 0 i = 4 j = -1 16

直接插入排序的算法 typedef int SortData; void InsertSort( SortData VI, intn)i /按非递减顺序对表进行排序 SortData temp; int i,j; for(1=1;i0;j--)/从后向前顺序比较 if( temp<Vl-1]=Vi-1I else breaks Vul-=temp

10 直接插入排序的算法 typedef int SortData; void InsertSort ( SortData V[ ], int n ) { //按非递减顺序对表进行排序 SortData temp; int i, j; for ( i = 1; i 0; j-- ) //从后向前顺序比较 if ( temp < V[j-1] ) V[j] = V[j-1]; else break; V[j] = temp; } }