数据结构教学课件作者C语言PPT 第9章.ppt

《数据结构教学课件作者C语言PPT 第9章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章排序概述插入排序交换排序选择排序归并排序分配排序外排序一、概述什么是排序(Sorting)？简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。排序是计算机中经常遇到的操作。排序的几个基本概念数据表(DataList)待排序的数据对象的有限集合。关键字(Key)作为排序依据的数据对象中的属性域。主关键字不同的数据对象若关键字互不相同，则这种关键字称为主关键字。排序的确切定义使一组任意排列的对象变成一组按关键字线性有序的对象。排序的几个基本概念（续）排序算法的稳定性判断标准：关键字相同的数据对象在排序过程中是否保持前后次序不变。如2,2*,1，排序后若为1,2*

2、,2则该排序方法是不稳定的。内排序与外排序区分标准：排序过程是否全部在内存进行。排序的时间开销它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量。排序的方法有很多，但简单地判断那一种算法最好，以便能够普遍选用则是困难的。评价排序算法好坏的标准主要有两条：算法执行所需要的时间和所需要的附加空间。另外，算法本身的复杂程度也是需要考虑的一个因素。排序算法所需要的附加空间一般都不大，矛盾并不突出。而排序是一种经常执行的一种运算，往往属于系统的核心部分，因此排序的时间开销是算法好坏的最重要的标志。为简单起见，数据的存储结构采用记录数组形式，同时假定关键字是整数。记录

3、数组的类型说明如下：typedefstruct{intkey;datatypeother;}rectype;rectypeR[n];其中n为记录总数加1二、插入排序基本原理，每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象适当位置上，直到对象全部插入为止。直接插入排序(InsertSort)希尔排序(ShellSort)直接插入排序(InsertSort)基本思想：当插入第i个对象时，前面的V[0],V[1],…,V[i-1]已经排好序，此时，用v[i]的关键字与V[i-1],V[i-2],…的关键字顺序进行比较，找到插入位置即将V[i]插入，原来位置上对象向后顺移

4、。直接插入排序举例i(0)(1)(2)(3)(4)(5)temp[21]254925*1608251[2125]4925*1608492[212549]25*160825*3[212525*49]1608164[16212525*49]08085[0816212525*49]直接插入排序算法INSERTSORT(rectypeR[]){inti,j;for(i=2;i

5、[i]的副本，使得不至于因记录的后移而丢失R[i]中的内容；其二是在while循环“监视”下标变量j是否越界，一旦越界（即j<1），R[0]自动控制while循环的结束，从而避免了在while循环内的每一次都要检测j是否越界（即省略了循环条件j>=1）。因此，我们把R[0]称为“监视哨”。算法分析直接插入排序算法由两重循环组成，对于有n个记录的排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。若初始时关键字递增有序，这是最好情况。每一趟排序中仅需进行一次关键字的比较，所以总的比较次数为n-1。在while循环之前和之中，至少要移动记录两次，所以总的比较次数为2(n-1

6、)。若初始时关键字递减有序，这是最坏情况。这时的记录比较和移动次数分别为：直接插入排序的稳定性直接插入排序是一种稳定的排序方法。原理：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。希尔排序1959年由D.L.Shell提出，又称缩小增量排序(Diminishing-incrementsort)。基本思想：在插入排序中，只比较相邻的结点，一次比较最多把结点移动一个位置。如果对位置间隔较大距离的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就可以提高排序的速度。希尔排序的基本过程设待排序的对象序列有n个对象，首先取一个整数gap

7、p个子序列，所有距离为gap的对象放在同一个序列中，在每一个子序列中分别施行直接插入排序，然后缩小间隔gap，如取gap=gap/2，重复上述的子序列划分和排序工作，直到最后取gap为1为止。希尔排序示例i(0)(1)(2)(3)(4)(5)gap21254925*1608121--25*325--1649--0821160825*2549221-08-25216-25*-4908162125*2549308162125*25491