人民邮电出版社：高职高专现代信息技术系列教材《数据结构》课程电子教案（PPT课件讲稿）第8章 排序

第8拿并序 本章中主要介绍下列内容: 插入排序 交换排序 选择排序 归并排序 基数排序 请单鼠标左键换页! 退出

第８章 排序 本章中主要介绍下列内容： ⚫ 插入排序 ⚫ 交换排序 ⚫ 选择排序 ⚫ 归并排序 ⚫ 基数排序 退出

8.1基本概念 8.2插入序 8.3交换推序 8.4选择序 8.5归并龙序 8.6基数龙序 请单赤鼠标左键换页!

8.1 基本概念 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序

8.1基本概念 关键字是数据元素中的某个数据项。如果某个数 据项可以唯一地确定一个数据元素,就将其称为主关 键字;否则,称为次关键字。 排序是把一组无序地数据元素按照关键字值递增 (或递减)地重新排列。如果排序依据的是主关键字, 排序的结果将是唯一的, 排序算法的稳定性如果在待排序的记录序列中有 多个数据元素的关键字值相同,经过排序后,这些数 据元素的相对次序保持不变,则称这种排序算法是稳 定的,否则称之为不稳定的。 请单鼠标左键换页!

8.1 基本概念 关键字 是数据元素中的某个数据项。如果某个数 据项可以唯一地确定一个数据元素，就将其称为主关 键字；否则，称为次关键字。 排序 是把一组无序地数据元素按照关键字值递增 （或递减）地重新排列。如果排序依据的是主关键字， 排序的结果将是唯一的， 排序算法的稳定性 如果在待排序的记录序列中有 多个数据元素的关键字值相同，经过排序后，这些数 据元素的相对次序保持不变，则称这种排序算法是稳 定的，否则称之为不稳定的

内部排序与外部排序根据在排序过程中待排序的 所有数据元素是否全部被放置在内存中,可将排序方 法分为内部排序和外部排序两大类。内部排序是指在 排序的整个过程中,待排序的所有数据元素全部被放 置在内存中;外部排序是指由于待排序的数据元素个 数太多,不能同时放置在内存,而需要将一部分数据 元素放置在内存,另一部分数据元素放置在外设上, 整个排序过程需要在内外存之间多次交换数据才能得 到排序的结果。本章只讨论常用的内部排序方法。 排序的基本方法内部排序主要有5种方法:插入 交换、选择、归并和基数。 趟在排序过程中,基本动作执行一次。 请单鼠标左键换页!

内部排序与外部排序 根据在排序过程中待排序的 所有数据元素是否全部被放置在内存中，可将排序方 法分为内部排序和外部排序两大类。内部排序是指在 排序的整个过程中，待排序的所有数据元素全部被放 置在内存中；外部排序是指由于待排序的数据元素个 数太多，不能同时放置在内存，而需要将一部分数据 元素放置在内存，另一部分数据元素放置在外设上， 整个排序过程需要在内外存之间多次交换数据才能得 到排序的结果。本章只讨论常用的内部排序方法。 排序的基本方法 内部排序主要有5种方法：插入、 交换、选择、归并和基数。 趟 在排序过程中，基本动作执行一次

排序算法的效率评价排序算法的效率主要有两点: 是在数据量规模一定的条件下,算法执行所消耗的 平均时间,对于排序操作,时间主要消耗在关键字之 间的比较和数据元素的移动上,因此我们可以认为高 效率的排序算法应该是尽可能少的比较次数和尽可能 少的数据元素移动次数;二是执行算法所需要的辅助 存储空间,辅助存储空间是指在数据量规模一定的条 件下,除了存放待排序数据元素占用的存储空间之外 执行算法所需要的其他存储空间,理想的空间效率是 算法执行期间所需要的辅助空间与待排序的数据量无 关。 请单鼠标左键换页!

排序算法的效率 评价排序算法的效率主要有两点： 一是在数据量规模一定的条件下，算法执行所消耗的 平均时间，对于排序操作，时间主要消耗在关键字之 间的比较和数据元素的移动上，因此我们可以认为高 效率的排序算法应该是尽可能少的比较次数和尽可能 少的数据元素移动次数；二是执行算法所需要的辅助 存储空间，辅助存储空间是指在数据量规模一定的条 件下，除了存放待排序数据元素占用的存储空间之外， 执行算法所需要的其他存储空间，理想的空间效率是 算法执行期间所需要的辅助空间与待排序的数据量无 关

待排序记录序列的存储结构待排序记录序列可以 用顺序存储结构和和链式存储结构表示。在本章的讨 论中(除基数排序外),我们将待排序的记录序列用 顺序存储结构表示,即用一维数组实现。其定义如下 所示: define maX num80∥待排序记录序列中的最大数 据元素个数 typedef struct elemtype{∥(排序的数据元素类型 keytype key: 数据元素的关键字 anytype otheritem;/数据元素中的其他成份 )Data Type MAX NUM+l 请单赤鼠标左键换页!

待排序记录序列的存储结构 待排序记录序列可以 用顺序存储结构和和链式存储结构表示。在本章的讨 论中（除基数排序外），我们将待排序的记录序列用 顺序存储结构表示，即用一维数组实现。其定义如下 所示： #define MAX_NUM 80 //待排序记录序列中的最大数 据元素个数 typedef struct elemtype { //待排序的数据元素类型 keytype key; //数据元素的关键字 anytype otheritem; //数据元素中的其他成份 }DataType[MAX_NUM+1];

8.2插入排序 插入排序的主要思路是不断地将待排序的数值插 入到有序段中,使有序段逐渐扩大,直至所有数值都 进入有序段中位置。 8.2.1直接插入排序 1.直接插入排序的基本思想 请单赤鼠标左键换页!

8.2 插入排序 插入排序的主要思路是不断地将待排序的数值插 入到有序段中，使有序段逐渐扩大，直至所有数值都 进入有序段中位置。 8.2.1 直接插入排序 1. 直接插入排序的基本思想

直接插入排序是一种比较简单的排序方法。它的 基本思想是依次将记录序列中的每一个记录插入到有 序段中,使有序段的长度不断地扩大。其具体的排序 过程可以描述如下:首先将待排序记录序列中的第 个记录作为一个有序段,将记录序列中的第二个记录 插入到上述有序段中形成由两个记录组成的有序段, 再将记录序列中的第三个记录插入到这个有序段中, 形成由三个记录组成的有序段,…依此类推,每一趟 都是将一个记录插入到前面的有序段中,假设当前欲 处理第个记录,则应该将这个记录插入到由前i-1个记 录组成的有序段中,从而形成一个由个记录组成的按 关键字值排列的有序序列,直到所有记录都插入到有 序段中。一共需要经过n-趟就可以将初始序列的n个 记录重新排列成按关键字值大小排列的有序序列 请单赤鼠标左键换页!

直接插入排序是一种比较简单的排序方法。它的 基本思想是依次将记录序列中的每一个记录插入到有 序段中，使有序段的长度不断地扩大。其具体的排序 过程可以描述如下：首先将待排序记录序列中的第一 个记录作为一个有序段，将记录序列中的第二个记录 插入到上述有序段中形成由两个记录组成的有序段， 再将记录序列中的第三个记录插入到这个有序段中， 形成由三个记录组成的有序段，…依此类推，每一趟 都是将一个记录插入到前面的有序段中，假设当前欲 处理第i个记录，则应该将这个记录插入到由前i-1个记 录组成的有序段中，从而形成一个由i个记录组成的按 关键字值排列的有序序列，直到所有记录都插入到有 序段中。一共需要经过n-1趟就可以将初始序列的n个 记录重新排列成按关键字值大小排列的有序序列

2.直接插入排序算法 将第个记录插入到由前面i1个记录构成的有序段 中主要有两个步骤: (1)将待插入记录a保存在a0中,即a0=a[i; 2)搜索插入位置: j=i-l;最初指示的前一个位置 while(ajo. key <alj. key) ai+1}=ajl;∥后移关键字值大于a|01key的记录 /将指向前一个记录,为下次比较做准备 a+1=a|0;/将a0放置在第j+1个位置上 请单鼠标左键换页!

2. 直接插入排序算法 将第i个记录插入到由前面i-1个记录构成的有序段 中主要有两个步骤： ⑴ 将待插入记录a[i] 保存在a[0]中，即a[0]=a[i]; ⑵ 搜索插入位置： j=i-1; //j最初指示i的前一个位置 while (a[0].key <a[j].key) { a[j+1]=a[j]; //后移关键字值大于a[0].key的记录 j=j-1; //将j指向前一个记录，为下次比较做准备 } a[j+1]=a[0]; //将a[0]放置在第j+1个位置上

完整的插入排序算法为: void insertsort (Data Type a, int n) for(i=2; i<=n; i++) ∥:要n-1趟 a|0}=ai;∥将a[赋予监视哨 while(al0key< alj. key)搜索插入位置 i alj+1=all; jj-1; ai+1|=a0;∥将原a中的记录放入第+个位置 请单赤鼠标左键换页!

完整的插入排序算法为： void insertsort (DataType a, int n) { for (i=2; i<=n; i++) //需要n-1趟 { a[0]=a[i]; //将a[i]赋予监视哨 j=i-1; while (a[0].key<a[j].key) //搜索插入位置 { a[j+1]=a[j]; j=j-1; } a[j+1]=a[0]; // 将原a[i]中的记录放入第j+1个位置 } }