《数据结构实用教程（c语言版）下ppt》由会员分享，可在线阅读，更多相关《数据结构实用教程（c语言版）下ppt（123页珍藏版）》请在金锄头文库上搜索。
1、数据结构实用教程（C语言版）下,第七章 排序 第八章 查找,第七章 排序,71 排序的基本概念 72 插入排序 73 交换排序 74 选择排序 75 归并排序 *76 基数排序 77 内排序方法的比较,71 排序的基本概念,1排序对象 由记录序列组成的文件，每一个记录又由若干数据项组成。由于文件是记录的序列，所以从逻辑结构上看它是个线性表 表7.1 学生成绩表 2排序码 通常把选作排序依据的数据项的值称为排序码。 3排序的定义 将一组记录按照某个排序码非递增或非递减的次序重新排列的过程。,一条记录,一个数据项,4排序的稳定性 排序码相同的两个记录经过排序之后，其相对次序保持不变，称该排序方法是
2、稳定的；反之，称该排序方法是不稳定的。 5内部排序与外部排序 整个排序过程全部在内存中进行，这种排序称为内部排序。涉及内外存之间数据交换的排序称为外部排序。外部排序的速度比内部排序的速度要慢得多。 6.排序两种基本操作： 1）比较两个记录排序码的大小；2）将记录从一个位置移动到另一个位置。 7.常见排序方法：插入排序、交换排序、选择排序、归并排序、基数排序,8排序方法的评价 时间复杂度，空间复杂度、稳定性和简单性等 9记录序列采用顺序存储结构，其C语言描述如下： #define N 20 typedef struct int key; /*定义排序码*/ DataType other; /*定
3、义其他数据项*/ RecType; /*记录的类型*/ RecType RN+1; N为待排序记录的个数，R0不存放记录，原因有两个: 其一，使数组的下标和记录的序号对应； 其二，将R0留作他用，比如做监视哨或者做记录交换的辅助空间。,72 插入排序,插入排序（Insertion Sort）的基本思想是：将一个待排序记录按照排序码的大小插入到一个有序序列的适当位置，使得插入后的序列仍然有序，直到所有记录全部插入到有序序列中。 插入排序主要包括两种方法：直接插入排序和希尔（Shell）排序。,721 直接插入排序,直接插入排序的基本思想：待排序的n个记录存放在数组R1Rn中，把数组分成一个有序表
4、和一个无序表，开始时有序表中只有一个记录R1，无序表中含有n-1个记录R2Rn。在排序的过程中每一次从无序表中取出第一个记录，把它插入到有序表中的适当位置，使之成为新的有序表，这样经过n-1次插入后，无序表成为空表，有序表就包含了全部n个记录，排序完毕。 将一个记录插入到有序表的过程称为一趟直接插入排序。,举例：排序码初始序列为（78，38，32，97，78， 30，29，17）,R1 R2 R3 R4 R5 R6 R7 R8 78 38 32 97 78 30 29 17 （初始状态） 38 78 32 97 78 30 29 17 （插入38后） 32 38 78 97 78 30 29
5、17 （插入32后） 32 38 78 97 78 30 29 17 （插入97后） 32 38 78 78 97 30 29 17 （插入78后） 30 32 38 78 78 97 29 17 （插入30后） 29 30 32 38 78 78 97 17 （插入29后） 17 29 30 32 38 78 78 97 （插入17后） 直接插入排序过程图示,直接插入排序算法的C函数如下：,void insertSort (RecType R) /*对数组R中的记录进行直接插入排序*/ int i,j; for(i=2;i=N;i+) /*待插入记录为R2，RN*/ R0=Ri; /*将待插
6、入的记录Ri放入R0中*/ j=i-1; while(R0.keyRj.key) /*查找记录Ri应该插入的位置*/ Rj+1=Rj-; /*将排序码大于Ri.key的记录后移*/ Rj+1=R0; /*插入Ri*/ ,直接插入排序算法的性能分析,时间效率 最好情况下为O(n) 最坏和平均时间复杂度都为O(n2) 空间效率 O(1) 稳定的排序方法,722 希尔排序,希尔排序的基本思想是：将待排序记录序列分成几个组，在每一组内分别进行直接插入排序，使得整个记录序列部分有序；重复此过程，直到所有记录都在同一组中，最后对所有的记录进行一次直接插入排序即可。,如何分组 将数组R1Rn的记录分为d个组
7、，使下标距离为d的记录在同一组，即R1，R1+d，R1+2d，. 为第一组，R2,R2+d,R2+2d,. 为第二组，以此类推，Rd,R2d，R3d, . 为最后一组（第d组），这里的d叫做步长（或增量值）。 这种分组在每一组内做直接插入排序的时候，记录移动一次，能跨跃较大的距离，从而加快了排序的速度。 希尔排序要对记录序列进行多次分组，每一次分组的步长d都在递减，即d1d2d3dt，直到最后一次选取步长dt =1，所有的记录都在一组中，进行最后一次直接插入排序， 我们将每一次分组排序的过程称为一趟希尔排序。,举例：设排序码初始序列:(36，25，48，65，12，25，43，57，76，32
8、),R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 36 25 48 65 12 25 43 57 76 32 （初始状态） 36 25 （d1=5） 25 43 48 57 65 76 12 32 25 25 48 65 12 36 43 57 76 32 （一趟希尔排序结果） 25 65 43 32 （d2=3） 25 12 57 48 36 76 25 12 36 32 25 48 43 57 76 65 （二趟希尔排序结果） 25 12 36 32 25 48 43 57 76 65 （d3=1） 12 25 25 32 36 43 48 57 65 76 （三趟希尔排序
9、结果） 希尔排序过程图示,一趟希尔排序算法的C函数： void shellInsert(RecType R,int d) /*按步长d进行分组，每一组分别做直接插入排序*/ int i,j; for (i=d+1;i0 /*插入记录*/ ,整个希尔排序算法的C函数： void shellSort(RecType R，int d,int t) /*d0dt-1为每一趟分组的步长*/ int k; for(k=0;kt;k+) shellInsert(R,dk); ,希尔排序算法的性能分析,当n较大时，希尔排序的平均时间复杂度在O(nlog 2n)和O(n2)之间，大约为O(n1.5)。 算法的空
10、间复杂度是O(1)。 希尔排序是不稳定的。,73 交换排序,交换排序的基本思想是：两两比较待排序记录的排序码，不符合排列顺序则交换记录，直到所有记录的排序码都符合排序要求。 本节主要介绍两种交换排序：起泡排序和快速排序。,731 起泡排序,起泡排序的基本思想是：首先将记录R1的排序码与记录R2的排序码做比较（从上向下），若R1的排序码大于R2的排序码，则交换两个记录的位置，使排序码大的记录（重者）往下“沉”（移到下标大的位置），使排序码小的记录（轻者）往上“浮”（移到下标小的位置）；然后比较R2和R3的排序码，同样轻者上浮，重者下沉；依此类推，直到比较Rn-1和Rn的排序码，若不符合顺序就交换
11、位置，称此过程为一趟起泡排序，结果是R1Rn中排序码最大的记录沉“底”，即放入Rn中。接下来，在R1Rn-1中进行第二趟起泡排序，又会将一个排序码最大的记录沉“底”，放到Rn-1中。这样重复进行n-1趟排序后，对于n个记录的起泡排序就结束了，数组R1Rn成为有序表。,举例：设有8个记录的排序码初始序列为（36，25，48，12，25，65，43，57）,R1 36 25 25 25 25 25 25 25 R2 25 36 36 36 36 36 36 36 R3 48 48 48 12 12 12 12 12 R4 12 12 12 48 25 25 25 25 R5 25 25 25 25
12、 48 48 48 48 R6 65 65 65 65 65 65 43 43 R7 43 43 43 43 43 43 65 57 R8 57 57 57 57 57 57 57 65 一趟排序的过程图示,R1 R 2 R 3 R4 R5 R6 R7 R 8 36 25 48 12 25 65 43 57 （初始状态） 25 36 12 25 48 43 57 65 （1趟排序结果） 25 12 25 36 43 48 57 65 （2趟排序结果） 12 25 25 36 43 48 57 65 （3趟排序结果） 12 25 25 36 43 48 57 65 （4趟排序结果） 12 25
13、25 36 43 48 57 65 （5趟排序结果） 12 25 25 36 43 48 57 65 （6趟排序结果） 12 25 25 36 43 48 57 65 （7趟排序结果） 起泡排序的全过程图示,起泡排序算法的C函数如下： void bubbleSort(RecType R) RecType x; int i,j,flag; for (i=1;iRj+1.key) x=Rj;Rj=Rj+1;Rj+1=x; flag=0; if (flag) break; /*若没有交换，表明已有序，结束循环*/ ,起泡排序的性能分析,时间效率：起泡排序的最好时间复杂度为O(n)，最坏时间复杂度为O(n2)，可以证明它的平均时间复杂度也为O(n2)。 空间效率：在整个算法中，需要一个用于交换记录的辅助空间，所以起泡排序的空间复杂度为O(1)。 稳定性：起泡排序是稳定的。,732 快速排序,快速排序(Quick Sort)也被称为划分排序或分区排序，它是目前所有的内部排序方法中速度最快的一种，快速排序是对起泡排序的一种改进。 快速排序的基本思想是：在R1Rn中，任意选取一个记录作为“基准记录”，将整个数
