《《数据结构实用教程（C语言版）》-董凤服-电子教案及算法 电子教案 第8章 排序》由会员分享，可在线阅读，更多相关《《数据结构实用教程（C语言版）》-董凤服-电子教案及算法 电子教案 第8章 排序（69页珍藏版）》请在金锄头文库上搜索。
1、,数据结构实用教程（C语言版） 中国水利水电出版社,第8章 排序,本章中主要介绍下列内容： 排序的概念 插入排序方法：直接插入排序和希尔排序 交换排序方法：冒泡排序和快速排序 选择排序方法：直接选择排序和堆排序 归并排序方法,本章目录,结束,8.1 排序的基本概念,8.1.1 排序的定义 8.1.2 相关概念,返回到总目录,8.1.1 排序的定义,有n个记录的序列R1，R2，Rn，其相应关键字的序列是K1，K2，Kn ，相应的下标序列为1，2，n。通过排序，要求找出当前下标序列1，2，n的一种排列p1，p2， ，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1Kp2Kpn ，这
2、样就得到一个按关键字有序的记录序列：Rp1，Rp2，Rpn。这样一种操作称为排序。 简单的说，就是将无序序列按记录中的关键字排成以该关键字有序的序列过程就是排序。,返回到本节目录,关键字Ki可以是记录Ri的主关键字，也可以是记录Ri的次主关键字。若Ki是记录Ri的主关键字，则任何一个记录的无序序列经过排序后得到的结果是唯一的；若Ki是记录Ri的次主关键字，则经过排序后得到的结果可能不一唯一。这是因为在待排序的记录序列中可能存在两个或两个以上关键字相等的记录。,返回到本节目录,8.1.2 相关概念,1内部排序 整个排序过程完全在内存中进行，称为内部排序。 2外部排序 由于待排序记录数据量太大，内
3、存无法容纳全部数据，排序需要借助外部存储设备才能完成，称为外部排序。 3稳定排序和不稳定排序 假设Ki=Kj(1in，1jn，ij)，若在排序前的序列中Ri领先于Rj(即ij)，经过排序后得到的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的 ；反之，若相同关键字的先后次序在排序过程中发生变化者，则称所用的排序方法是不稳定的。,返回到本节目录,本章主要介绍的是内部排序。内部排序主要分为插入排序法、交换排序法、选择排序法和归并排序法。 我们假定待排序的记录均是以顺序存储结构存放的，且假定记录的关键字均为整数。另外，假定待排序的记录是按递增顺序进行排序。其排序记录的数据类型定义如下：,返回到本节
4、目录,#define MaxSize 100 /*查找表中最大元素个数*/ typedef int KeyType; /*重定义关键字类型为整型，也可以为其它类型*/ typedef char ElemType; /*重定义数据项类型为字符型*/ typedef struct KeyType Key; /*关键字域*/ ElemType data; /*其他数据项*/ LineList; /*线性查找表类型*/,返回到本节目录,8.2 插入排序,8.2.1 直接插入排序 8.2.2 希尔排序,返回到总目录,8.2.1 直接插入排序,1直接插入排序的基本思想 直接插入排序是一种最简单的排序方法，
5、它的基本思想是依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。有n个记录的无序序列具体的排序过程可以描述如下： （1）首先将待排序记录序列中的第一个记录作为一个有序段，此时这个有序段中只有一个记录。 （2）从第2个记录起到最后一个记录，依次将记录和前面子序列中的记录比较，确定记录插入的位置。,返回到本节目录,（3）将记录插入到子序列中，子序列中的记录个数加1，直至子序列长度和原来待排序列长度一致时排序结束。 一共经过n-1趟就可以将初始序列的n个记录重新排列成按关键字值从小到大排列的有序序列。 为了防止在比较过程中数组下标的溢出，我们设一个监视哨r0，即先将要比较的关键字
6、存入监视哨r0中，然后再用r0从后向前进行比较。若r0小于所比较的关键字，则将该关键字向后移一位，并且继续向前比较，直到r0大于等于所比较的关键字时结束。因为我们是边比较边移动记录的，所以在当前比较记录的后面位置是空出来的，直接将r0存入即可。,返回到本节目录,【例8.1】设待排序的记录序列有n=7个记录，其关键字的初始序列为：32，15，6，48，19，21，49，请给出直接插入排序的过程。在序列中有两个相同关键字15，我们用方框将后一个15框上加以区分。 解：直接插入排序过程如图8-1所示。就是对此记录序列进行直接插入排序的过程示意图。其中括号内部的关键字为已排好序的部分。,返回到本节目录
7、,图8-1 直接插入排序过程,返回到本节目录,2直接插入排序的算法如算法8.1所示 算法8.1 void InsertSort(LineList r,int n) int i,j; for(i=2;i=n;i+) /*一共需要比较n-1趟*/ r0=ri; /*将r0赋为监视哨*/ j=i-1;,返回到本节目录,while(r0.Keyrj.Key) /*搜索插入位置*/ rj+1=rj; j=j-1; rj+1=r0; /*将原来ri中的记录放入第j+1个位置*/ 该算法的主函数同后面希尔排序的主函数，只是将调用语句改为InsertSort(r,n);即可。,返回到本节目录,3直接插入排序算
8、法分析： 从空间角度来看，它只需要一个辅助空间r0。 从时间耗费角度来看，主要时间耗费在关键字比较和移动元素上。算法执行时间在最坏的情况下是O(n2) 。 在这种插入过程中两个15先后位置没有发生变化，所以直接插入排序是一种稳定排序方法。,返回到本节目录,8.2.2 希尔排序,1希尔排序的基本思想 希尔排序又称为缩小增量排序，其基本思想是：先将待排序的记录划分为几组，从而减小参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，最后再对所有的记录实施直接插入排序。 希尔排序的具体方法如下：,返回到本节目录,（1）取定一个正整数d1n，把d1作为间隔值，把全部记录从第一个记录起
9、进行分组，所有距离为dk1倍数的记录放在一组中，在各组内进行直接插入排序。 （2）取定一个正整数d2d1，重复上述分组和排序工作，直至取di=1为止，即所有记录在一个组中进行直接插入排序。 希尔提出的d1= ，di+1= 。,返回到本节目录,【例8.2】已知待排序的一组记录的关键字初始排列为25，36，12，68，45，16，37，22，请给出希尔排序的过程。 解：其希尔排序的过程如图8-2所示。,图8-2 希尔排序的过程,返回到本节目录,2希尔排序的算法 （1）希尔排序如算法8.2所示。 算法8.2 void ShellSort(LineList r,int n) int i,j,d; d=
10、n/2; /*初始步长为表长的一半*/ while(d0) for(i=d;i=n;i+) r0=ri; /*设监视哨*/ j=i-d;,返回到本节目录,while(j=0 ,返回到本节目录,8.3 交换排序,交换排序的基本方法是：通过两两比较待排序记录的关键字，若有不满足次序要求的一对数据则交换，直到全部满足为止。本节主要介绍冒泡排序和快速排序两种排序方法。 8.3.1 冒泡排序 8.3.2 快速排序,返回到总目录,8.3.1 冒泡排序,1冒泡排序的基本思想 冒泡排序是交换排序中一种简单的排序方法。它的基本思想是对所有相邻记录的关键字值进行比较，如果是逆序（rjrj+1），则将其交换，最终达
11、到有序化。其处理过程为： （1）将整个待排序的记录序列划分成有序区和无序区。初始状态有序区为空，无序区包括所有待排序的记录。,返回到本节目录,（2）对无序区从前向后依次将相邻记录的关键字进行比较，若逆序则将其交换，从而使得关键字值小的记录向上“飘”（左移），关键字值大的记录向下“沉”（右移）。 每经过一趟冒泡排序，都使无序区中关键字值最大的记录进入有序区，对于由n个记录组成的记录序列，最多经过n-1趟冒泡排序，就可以将这n个记录重新按关键字顺序排列。,返回到本节目录,【例8.3】已知有10个待排序的记录，它们的关键字序列为43，12，35，18，26，57，7，21，43，46，给出冒泡排序法
12、进行排序的过程。（两个相同的关键字43，后面的43用方框框上） 解：冒泡排序的过程如图8-3所示。其中括号内表示有序区。,返回到本节目录,图8-3 冒泡排序的过程,返回到本节目录,2 冒泡排序算法,（1）基本的冒泡排序算法 对由n个记录组成的记录序列，最多经过（n-1）趟冒泡排序，就可以使记录序列成为有序序列，第一趟定位第n个记录，此时有序区只有一个记录；第二趟定位第n-1个记录，此时有序区有两个记录；以此类推，直到最后所有的记录都进入有序区，排序结束。 完整的冒泡排序算法如算法8.3所示。,返回到本节目录,算法8.3 void BubbleSort1(LineList r, int n) i
13、nt i,j; LineList temp; for (i=n-1;i0;i-) /*i为每趟排序的数组最大下标值*/ for (j=0;jrj+1.Key) /*若逆序*/ temp=rj;rj=rj+1;rj+1=temp; ,返回到本节目录,（2）改进的冒泡排序算法 在冒泡排序过程中，一旦发现某一趟没有进行交换操作，就表明此时待排序记录序列已经成为有序序列，冒泡排序再进行下去已经没有必要，应立即结束排序过程。 如例8.1题中，在第六趟排序后，序列已经成为有序序列，从第七次到第九次排序就没有必要。为实现这一方法我们在循环体内设一个查看是否有记录交换的变量，在每趟比较时查看是否有交换，如果没
14、有，则提前结束循环。 改进的冒泡排序算法如算法8.4所示。,返回到本节目录,算法8.4 void BubbleSort2(LineList r,int n) int i,j, exchange; /* exchange 为标记是否交换的标识变量*/ LineList temp; for (i=n-1;i0;i-) /*i为每趟排序的数组最大下标值*/ exchange=0;,返回到本节目录,for (j=0;jrj+1.Key) /*若逆序*/ temp=rj;rj=rj+1;rj+1=temp;exchange=1; if (exchange=0) return; ,返回到本节目录,8.3.
15、2 快速排序,快速排序（Quick Sort）是对起泡排序的一种改进。 1快速排序的基本思想 快速排序又称为分区交换排序，通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可以分别对这两部分记录继续进行排序，以达到整个序列有序。,返回到本节目录,具体过程是：首先将待排序记录序列中的所有记录作为当前待排序区域，从中任选取一个记录（通常选取第一个记录）作为支点（或枢轴），并以该记录的关键字值为基准，从位于待排序记录序列左右两端开始，逐渐向中间靠拢，交替与基准记录的关键字进行比较、交换。 每次比较，若遇左侧记录的关键字值大于基准记录的关键字，则将其与基准记录交换，使其移到基准记录的右侧；若遇右侧记录的关键字值小于基准值，则将其与基准记录交换，使其移至基准记录的左侧，最后让基准记录到达它的最终位置。,返回到本节目录,此时，基准记录将待排序记录分成了左右两个区域，位于基准记录左侧的记录都小于或等于基准记录的关键字，位于基准记录右侧的所有记录的关键字都大于或等于基准记录的关键字，这就是一趟快速排序。 一趟快速排序之后，再分别对左右两个区域进行快速排序，以此类推，直到每个分区域都只有一个记录为止。此时整个待排序记录按关键值有序排列，至此排序结束。,返回到本节目录,【例8.2】已知一
