数据结构课件(c语言)

《数据结构课件(c语言)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章排序排序是指将一组数据元素按某个数据项值的大小排列成一个有序序列的过程。排序是计算机程序设计中经常使用的一种重要操作，是组织数据和处理数据的最基本最重要的运算之一。排序被广泛应用于数据处理、情报检索、商业金融等许多领域。9.6分配排序（基数排序）1．记录、关键码和排序表：记录：数据元素关键码（或排序码）：作为排序依据的数据项称为数据元素的关键码。排序表：若干个（n个）排序纪录组成的集合。排序表也称成为文件，主要操作是排序。2．非递减序列、递减序列、非递增序列、递增有序3．稳定排序和非稳定排序稳定排序：记录的相对位置在排序前后

2、不发生变化不稳定排序：4．内部排序和外部排序待排序的表完全放在内存中称为内排序5．对排序方法的评价空间性能：除排序表以外的内存占用情况。时间性能：比较关键码的次数，数据移动的次数。它们往往是排序表规模（n）的函数6.记录和排序表的数据结构在本章的讨论中，除特殊声明外，一般采用顺序结构存储排序表。记录和排序表的类型定义如下：#defineMAXNUM…/*MAXNUM为足够大的数*/typedefstruct{keytypekey;/*关键码字段*/……/*其它信息*/}datatype;/*记录类型RecNode*/datatyp

3、eR[MAXNUM];/*定义排序表的存储*/如不加特别说明，排序表中的记录R1…Rn存放在R[1]…R[n]分量中，R[0]分量闲置或做监视哨（n是排序表中记录的个数）。9.6分配排序（基数排序）1直接插入排序2折半插入排序3*表插入排序3希尔排序插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表的适当位置，直到全部记录插入完成，整个表有序为止。9.2.1直接插入排序直接插入排序是一种简单的插入排序方法，基本思想为：在R[1]至R[i-1]长度为i-1的子表已经有序的情况下，将R[i]插入，得

4、到R[1]至R[i]长度为i的子表有序，这样通过n-1趟（i=2..n）之后，R[1]至R[n]有序。例如，对于以下序列（为简便起见，每一个记录只列出其排序码，用排序码代表记录）：[1018203660]2530181256其中，前5个记录组成的子序列是有序的，这时要将第6个记录插入到前5个记录组成的有序子序列中去，得到一个含有6个记录的新有序序列。完成这个插入首先需要找到插入位置：20<25<36，因此25应插入到记录20和记录36之间，从而得到以下新序列：[101820253660]30181256这就是一趟直接插入排序的过程

5、。直接插入排序：仅有一个记录的表总是有序的，因此，对n个记录的表，可从第二个记录开始直到第n个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。R[0]R[1]R[2]R[3]R[4]R[5]R[6]R[7]R[8]R[9]R[10]初始:36201810602530181256i=2：(20)(2036)1810602530181256i=3：(18)(182036)10602530181256i=4：(10)(10182036)602530181256……i=7：(30)(10182025303660)181

6、256i=8：(18)(1018182025303660)1256【算法9-1】直接插入排序voidD_InsertSort(datatypeR[],intn){/*对排序表R[1]..R[n]进行直接插入排序，n是记录的个数*/for(i=2;i<=n;i++)if(R[i].key

7、合适位置*/}}性能分析空间性能：仅用了一个辅助单元R[0]作为监视哨，空间复杂度为O(1)。时间性能：向有序表中逐个插入记录的操作，进行了n1趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于初始序列的排列情况。分三种情况讨论：总比较次数总移动次数(2)最坏情况下：即第j趟操作，插入记录需要同前面的j个记录进行j次关键码比较，移动记录的次数为j+2次。最好情况下：即待排序列已按关键码有序，每趟操作只需1次比较，0次移动。即：总比较次数=n-1次总移动次数=0次(3)平均情况下：即第j趟操作，插入记录大约同

8、前面的j/2个记录进行关键码比较，移动记录的次数为j/2+2次。总比较次数总移动次数由此，直接插入排序的时间复杂度为O(n2)。直接插入排序是一个稳定的排序方法。直接插入排序也可以在链式结构上实现。9.2.2折半插入排序直接插入排序的基本操作是向有