数据结构 叶乃文 郑晓红 第八章

《数据结构 叶乃文 郑晓红 第八章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第８章排序本章中主要介绍下列内容：插入排序交换排序选择排序归并排序基数排序退出8.1基本概念8.2插入排序8.3交换排序8.4选择排序8.5归并排序8.6基数排序8.1基本概念关键字是数据元素中的某个数据项。如果某个数据项可以唯一地确定一个数据元素，就将其称为主关键字；否则，称为次关键字。排序是把一组无序地数据元素按照关键字值递增（或递减）地重新排列。如果排序依据的是主关键字，排序的结果将是唯一的，排序算法的稳定性如果在待排序的记录序列中有多个数据元素的关键字值相同，经过排序后，这些数据元素的相对次序保持不变，则称这种排序算法是稳定的，否则

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

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

4、序外），我们将待排序的记录序列用顺序存储结构表示，即用一维数组实现。其定义如下所示：#defineMAX_NUM80//待排序记录序列中的最大数据元素个数typedefstructelemtype{//待排序的数据元素类型keytypekey;//数据元素的关键字anytypeotheritem;//数据元素中的其他成份}DataType[MAX_NUM+1];8.2插入排序插入排序的主要思路是不断地将待排序的数值插入到有序段中，使有序段逐渐扩大，直至所有数值都进入有序段中位置。8.2.1直接插入排序1.直接插入排序的基本思想直接插入排序是

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

6、中。一共需要经过n-1趟就可以将初始序列的n个记录重新排列成按关键字值大小排列的有序序列。2.直接插入排序算法将第i个记录插入到由前面i-1个记录构成的有序段中主要有两个步骤：⑴将待插入记录a[i]保存在a[0]中，即a[0]=a[i];⑵搜索插入位置：j=i-1;//j最初指示i的前一个位置while(a[0].key

7、voidinsertsort(DataTypea,intn){for(i=2;i<=n;i++)//需要n-1趟{a[0]=a[i];//将a[i]赋予监视哨j=i-1;while(a[0].key

8、时，大量的比较和移动操作将使直接插入排序算法的效率降低；然而，当待排序的数据元素基本有序时，直接插入排序过程中的移动次数大大减少，从而效率会有所提高。插入排序是一种稳定的排序方法