数据结构(C语言版)9、排序

数据结构(C语言版) 教学课件

第8章 排序本章中主要介绍下列内容： 插入排序

交换排序选择排序 归并排序 基数排序

退出

数据结构(C语言版) 教学课件

8.1 基本概念

8.2 插入排序8.3 交换排序

8.4 选择排序8.5 归并排序 8.6 基数排序

数据结构(C语言版) 教学课件

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

数据结构(C语言版) 教学课件

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

排序的基本方法 内部排序主要有5种方法：插入、 交换、选择、归并和基数。 趟 在排序过程中，基本动作执行一次。

数据结构(C语言版) 教学课件

排序算法的效率 评价排序算法的效率主要有两点： 一是在数据量规模一定的条件下，算法执行所消耗的

平均时间，对于排序操作，时间主要消耗在关键字之间的比较和数据元素的移动上，因此我们可以认为高 效率的排序算法应该是尽可能少的比较次数和尽可能

少的数据元素移动次数；二是执行算法所需要的辅助存储空间，辅助存储空间是指在数据量规模一定的条 件下，除了存放待排序数据元素占用的存储空间之外， 执行算法所需要的其他存储空间，理想的空间效率是 算法执行期间所需要的辅助空间与待排序的数据量无 关。

数据结构(C语言版) 教学课件

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

//数据元素的关键字

数据结构(C语言版) 教学课件

8.2 插入排序插入排序的主要思路是不断地将待排序的数值插入到有序段中，

使有序段逐渐扩大，直至所有数值都 进入有序段中位置。 8.2.1 直接插入排序 1. 直接插入排序的基本思想

数据结构(C语言版) 教学课件

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

数据结构(C语言版) 教学课件

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个位置上

数据结构(C语言版) 教学课件

完整的插入排序算法为：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个位置 } }

数据结构(C语言版) 教学课件

直接插入排序算法简单、容易实现，只需要一个 记录大小的辅助空间用于存放待插入的记录(在C语

言中，我们利用了数组中的0单元)和两个int型变量。当待排序记录较少时，排序速度较快，但是，当待排 序的记录数量较大时，大量的比较和移动操作将使直 接插入排序算法的效率降低；然而，当待排序的数据 元素基本有序时，直接插入排序过程中的移动次数大 大减少，从而效率会有所提高。 插入排序是一种稳定的排序方法。

数据结构(C语言版) 教学课件

8.2.2 希尔排序 1. 希尔排序的基本思想 希尔排序方法又称为缩小增量排序，其基本思想

是将待排序的记录划分成几组，从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排

列已经基本有序，这个时候再对所有的记录实施直接插入排序。

数据结构(C语言版) 教学课件

具体步骤可以描述如下：假设待排序的记录为n个， 先取整数d<n,例如，取d=n/2 (n/2 表示不大于n/2的

最大整数),将所有距离为d的记录构成一组，从而将整个待排序记录

序列分割成为d个子序列，如图8-2所 示，对每个分组分别进行直接插入排序，然后再缩小 间隔d,例如，取d=d/2,重复上述的分组，再对每个 分组分别进行直接插入排序，直到最后取d=1,即将所

有记录放在一组进行一次直接插入排序，最终将所有记录重新排列成按关键字有序的序列。

数据结构(C语言版) 教学课件

3. 希尔排序算法 (1) 分别让每个记录参与相应分组中的排序 若分为d组，前d个记录就应该分别构成由一个记 录组成的有序段，从d+1个记录开始，逐一将每个记录 a[i]插入到相应组中的有序段中，其算法可以这样实现：

for (i=d+1; i<=n; i++){ 将a[i]插入到相应组的有序段中； }

数据结构(C语言版) 教学课件

(2) 将a[i]插入到相应组的有序段中的操作可以这 样实现： 将a[i]赋予a[0]中，即a[0]=a[i]; 让j指向a[i]所属组的有序序列中最后一个记录 搜索a[i]的插入位置 while(j>0 && a[0].key<a[j].key) {

a[j+d]=a[j]; j=j-d;}

数据结构(C语言版) 教学课件

希尔排序的完整算法如下： void shellsort(DataType a,int n) { for(d=n/2;d>=1;d=d/2) { for(i=1+d;i<=n;i++) //将a[i]插入到所属组的有序列段中 { a[0]=a[i]; j=i-d; while(j>0&&a[0].key<a[j].key) { a[j+d]=a[j]; j=j-d; } a[j+d]=a[0]; } }