数据结构实用教程（c语言版）下ppt

《数据结构实用教程（c语言版）下ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实用教程（C语言版）下第七章排序第八章查找第七章排序7．1排序的基本概念7．2插入排序7．3交换排序7．4选择排序7．5归并排序*7．6基数排序7．7内排序方法的比较7．1排序的基本概念1．排序对象由记录序列组成的文件，每一个记录又由若干数据项组成。由于文件是记录的序列，所以从逻辑结构上看它是个线性表表7.1学生成绩表2．排序码通常把选作排序依据的数据项的值称为排序码。3．排序的定义将一组记录按照某个排序码非递增或非递减的次序重新排列的过程。一条记录一个数据项4．排序的稳定性排序码相同的两个记录经过排序之后，其相对次序保持不变，称该排序方法是稳定的；

2、反之，称该排序方法是不稳定的。5．内部排序与外部排序整个排序过程全部在内存中进行，这种排序称为内部排序。涉及内外存之间数据交换的排序称为外部排序。外部排序的速度比内部排序的速度要慢得多。6.排序两种基本操作：1）比较两个记录排序码的大小；2）将记录从一个位置移动到另一个位置。7.常见排序方法：插入排序、交换排序、选择排序、归并排序、基数排序8．排序方法的评价时间复杂度，空间复杂度、稳定性和简单性等9．记录序列采用顺序存储结构，其C语言描述如下：#defineN20typedefstruct{intkey;/*定义排序码*/DataTypeother;/*定义

3、其他数据项*/}RecType;/*记录的类型*/RecTypeR[N+1];N为待排序记录的个数，R[0]不存放记录，原因有两个:其一，使数组的下标和记录的序号对应；其二，将R[0]留作他用，比如做监视哨或者做记录交换的辅助空间。7．2插入排序插入排序（InsertionSort）的基本思想是：将一个待排序记录按照排序码的大小插入到一个有序序列的适当位置，使得插入后的序列仍然有序，直到所有记录全部插入到有序序列中。插入排序主要包括两种方法：直接插入排序和希尔（Shell）排序。7．2．1直接插入排序直接插入排序的基本思想：待排序的n个记录存放在数组R[1]

4、~R[n]中，把数组分成一个有序表和一个无序表，开始时有序表中只有一个记录R[1]，无序表中含有n-1个记录R[2]~R[n]。在排序的过程中每一次从无序表中取出第一个记录，把它插入到有序表中的适当位置，使之成为新的有序表，这样经过n-1次插入后，无序表成为空表，有序表就包含了全部n个记录，排序完毕。将一个记录插入到有序表的过程称为一趟直接插入排序。举例：排序码初始序列为（78，38，32，97，78，30，29，17）R[1]R[2]R[3]R[4]R[5]R[6]R[7]R[8][78]38329778302917（初始状态）[3878]32977830

5、2917（插入38后）[323878]9778302917（插入32后）[32387897]78302917（插入97后）[3238787897]302917（插入78后）[303238787897]2917（插入30后）[29303238787897]17（插入29后）[1729303238787897]（插入17后）直接插入排序过程图示直接插入排序算法的C函数如下：voidinsertSort(RecTypeR[])/*对数组R中的记录进行直接插入排序*/{inti,j;for(i=2;i<=N;i++)/*待插入记录为R[2]，…，R[N]*/{R[0

6、]=R[i];/*将待插入的记录R[i]放入R[0]中*/j=i-1;while(R[0].key

7、对所有的记录进行一次直接插入排序即可。如何分组将数组R[1]~R[n]的记录分为d个组，使下标距离为d的记录在同一组，即{R[1]，R[1+d]，R[1+2d]，...}为第一组，{R[2],R[2+d],R[2+2d],...}为第二组，以此类推，{R[d],R[2d]，R[3d],...}为最后一组（第d组），这里的d叫做步长（或增量值）。这种分组在每一组内做直接插入排序的时候，记录移动一次，能跨跃较大的距离，从而加快了排序的速度。希尔排序要对记录序列进行多次分组，每一次分组的步长d都在递减，即d1＞d2＞d3＞…＞dt，直到最后一次选取步长dt=1，所

8、有的记录都在一组中，进行最后一次直接插入排序，我们将