数据结构 C语言版 教学课件 作者 李云清 第10章_内排序.ppt

《数据结构 C语言版 教学课件 作者 李云清 第10章_内排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构李云清杨庆红揭安全第10章内排序排序是数据处理过程中经常使用的一种重要的运算，排序的方法有很多种，本章主要讨论内排序的各种算法，并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行了讨论。10.1排序的基本概念假设一个文件是由n个记录R1，R2，…，Rn组成，所谓排序就是以记录中某个(或几个)字段值不减(或不增)的次序将这n个记录重新排列，称该字段为排序码。能唯一标识一个记录的字段称为关键码，关键码可以作为排序码，但排序码不一定要是关键码。按排序过程中使用到的存储介质来分，可以将排序分成两大类:内排序

2、和外排序。内排序是指在排序过程中所有数据均放在内存中处理，不需要使用外存的排序方法。而对于数据量很大的文件，在内存不足的情况下，则还需要使用外存，这种排序方法称为外排序。排序码相同的记录，若经过排序后，这些记录仍保持原来的相对次序不变，称这个排序算法是稳定的。否则，称为不稳定的排序算法。评价排序算法优劣的标准：首先考虑算法执行所需的时间，这主要是用执行过程中的比较次数和移动次数来度量；其次考虑算法执行所需要的附加空间。当然，保证算法的正确性是不言而喻的，可读性等也是要考虑的因素。排序算法如未作特别的说明，使用的有

3、关定义如下：/*常见排序算法的头文件，文件名table.h*/#defineMAXSIZE100/*文件中记录个数的最大值*/typedefintkeytype;/*定义排序码类型为整数类型*/typedefstruct{keytypekey;/*此处还可以定义记录中除排序码外的其它域*/}recordtype;/*记录类型的定义*/typedefstruct{recordtyper[MAXSIZE+1];intlength;/*待排序文件中记录的个数*/}table;/*待排序文件类型*/为了方便，r[0]一般

4、不用于存放排序码，在一些排序算法中它可以用来作为中间单元存放临时数据。length域是待排序的记录个数，它必须不大于MAXSIZE，这样，第1~length个记录的排序码分别存于r[1].key~r[length].key中10.2插入排序插入排序的基本方法是:将待排序文件中的记录，逐个地按其排序码值的大小插入到目前已经排好序的若干个记录组成的文件中的适当位置，并保持新文件有序。10.2.1直接插入排序直接插入排序算法的思路是:初始可认为文件中的第1个记录己排好序，然后将第2个到第n个记录依次插入已排序的记录组成

5、的文件中。在对第i个记录Ri进行插入时，R1，R2，…，Ri-1已排序，将记录Ri的排序码keyi与已经排好序的排序码从右向左依次比较，找到Ri应插入的位置，将该位置以后直到Ri-1各记录顺序后移，空出该位置让Ri插入。一组记录的排序码分别为:312，126，272，226，28，165，123初始时将第1个排序码作为已经排好序的，把排好序的数据记录放入中括号[]中，表示有序的文件，剩下的在中括号外，如下所示：[312]，126，272，226，28，165，123设前3个记录的排序码已重新排列有序，构成一个含有

6、3个记录的有序文件:[126，272，312]，226，28，165，123现在要将第4个排序码226插入！[126，272，312]，226，28，165，123现在要将第4个排序码226插入！将待插入的排序码226和已经有序的最后一个排序码312比较，因为待插入的排序码226小于312，所以226肯定要置于312的前面，至于是否就是置于312的前一个位置，此时还不能确定，需要继续向左比较；将所有大于待插入排序码226的那两个排序码312和272依次后移一个位置，在空出的位置插入待排序的排序码226，得一含有4

7、个记录的有序文件：[126，226，272，312]，28，165，123需要注意的是，当待插入排序码小于所有已排序的排序码时，如在插入第5个值28时：[126，226，272，312]，28，165，123算法设计的时候如处理？方法之一：设置“哨兵”voidinsertsort(table*tab){inti,j;for(i=2;i<=tab->length;i++)/*依次插入从第2个开始的所有元素*/{j=i-1;tab->r[0].key=tab->r[i].key;/*设置哨兵，准备找插入位置*/whi

8、le(tab->r[0].keyr[j].key)/*找插入位置并后移*/{tab->r[j+1].key=tab->r[j].key;/*后移*/j=j-1;/*继续向前（左）查找*/}tab->r[j+1].key=tab->r[0].key;/*插入第i个元素的副本，即前面设置的哨兵*/}}算法10.1直接插入排序算法设待排序的7记录的排序码为{312，