《数据结构实例教程（C语言版）：第9章 排序的分析与应用》由会员分享，可在线阅读，更多相关《数据结构实例教程（C语言版）：第9章 排序的分析与应用（27页珍藏版）》请在金锄头文库上搜索。
1、 数据结构实例教程（数据结构实例教程（C语言版）语言版）第第9 9章排序的分析与应用章排序的分析与应用 学习目标学习目标 了解排序的定义。 熟练掌握各种排序方法的基本思想及实现方法。 掌握各种排序方法时间复杂度和稳定性的分析方法。 掌握各种排序方法在何种情况下使用的分析方法。 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.19.1排序的基本概念排序的基本概念一、排序的定义1、排序的定义：假设含n个记录的序列为 R1, R2, ,Rn ， 按照关键字的递增（或递减），记录将形成新的序列为 Rp1, Rp2, ，Rpn 。2、举例 关键字：12，45，9，23，90，77，65 调整为
2、：9，12，23，45，65，77，90 学号学号姓名姓名成成绩31101001王菲9031101002周董8731101007飞儿7731101006石头9031101005刘欢95可以按学号或者成绩进行排序 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.19.1排序的基本概念排序的基本概念二、相关概念1、内部排序：若整个排序过程不需要访问外存便能完成。2、外部排序：若内存无法容纳全部数据，排序需要借助外 部存储设备才能完成。3、稳定排序和不稳定排序 假设Ki=Kj(1in，1jn，ij)，若在排序前的序列中 Ri领先于Rj(即ij)，经过排序后得到的序列中Ri仍领先于Rj，则排
3、序方法是稳定的；反之，是不稳定的。排序前的序列为：(56, 34, 47, 23, 66, 18, 82, 47)若排序后结果为：(18, 23, 34, 47,47, 56, 66, 82)，则称该排序方法是稳定的。若排序后结果为：(18, 23, 34,47,47, 56, 66, 82)，则称该排序方法是不稳定的。 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.29.2插入排序插入排序一、直接插入排序1、排序过程描述 首先将待排序记录序列中的第一个记录作为一个有序段。 从第2个记录起到最后一个记录，依次和前面子序列中的 记录比较，确定插入的位置。 数据结构实例教程（数据结构实
4、例教程（C语言版）语言版）9.29.2插入排序插入排序一、直接插入排序2、举例：对序列32，15，6，48，19，15，49进行直接插 入排序。 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.29.2插入排序插入排序一、直接插入排序3、直接插入排序算法如下： void inerSort(LineList R ,int n)void inerSort(LineList R ,int n) int i,j; int i,j; for(i=2;i=n;+i) for(i=2;i=n;+i) if(Ri.keyRi-1.key) if(Ri.keyRi-1.key) R0.key=Ri.k
5、ey; R0.key=Ri.key; for (j=i-1;R0.keyRj.key;-j) for (j=i-1;R0.keyRj.key;-j) Rj+1=Rj Rj+1=Rj； Rj+1=R0Rj+1=R0； 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.29.2插入排序插入排序二、希尔排序1、排序过程描述 取定一个正整数d1n，把d1作为间隔值，把全部记录从 第一个记录起进行分组，所有距离为d1倍数的记录放在 一组中，在各组内进行直接插入排序。 取定一个正整数d20)/while(d0)/直到直到d d为为1 1 for(i=d+1;i=n;+i)/ for(i=d+1;i
6、=n;+i)/对每组进行直接插入排序对每组进行直接插入排序 if(Ri.keyRi-d.key)if(Ri.key0&R0.key0&R0.keyRj.key;j=j-d) Rj+d=Rj Rj+d=Rj； Rj+d=R0Rj+d=R0； d=d/2;/ d=d/2;/缩小步长值缩小步长值 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.39.3交换排序交换排序一、冒泡排序1、排序过程描述 将整个记录序列划分成有序区和无序区。初始状态有序区 为空，无序区包括所有待排序的记录。 对无序区从前向后依次将相邻记录的关键字进行比较，若 逆序将其交换，值小的记录向左移，值大的记录向右移。 每经
7、过一趟冒泡排序，无序区中关键字值最大的记录进入 有序区，最多经过n-1趟冒泡排序，就可以完成排序。 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.39.3交换排序交换排序一、冒泡排序2、举例：对序列45，19，35，28，57，7，45，46 进行冒 泡排序。 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.39.3交换排序交换排序一、冒泡排序3、冒泡排序算法如下： void BubbleSort(LineList R ,int n)void BubbleSort(LineList R ,int n) int i,j; int i,j; for(i=1;in;i+) /i
8、 for(i=1;in;i+) /i为比较为比较趟数趟数 for(j=1;j=n-i;j+) /for(j=1;jRj+1.key) / if(Rj.keyRj+1.key) /若若逆序逆序 R0=Rj; R0=Rj; Rj=Rj+1; Rj=Rj+1; Rj+1=R0;/ Rj+1=R0;/用用R0R0最为中间最为中间变量实现交换变量实现交换 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.39.3交换排序交换排序二、快速排序1、排序过程描述 对rst中记录进行一趟快速排序，附设两个指针i和j，设 枢轴记录R0=Rs，初始时令i=s,j=t； 首先从j所指的记录开始从后向前扫描，搜
9、索第一个关键 字小于R0.key的记录Rj，并复制到Rs处，i加1，使关键 码小（同轴值相比）的记录移动到前面去； 再从i所指的记录开始从前向后扫描, 找到第一个关键字大 于R0.key的记录Ri，并复制到Rj处，j减1，使关键码大 （同轴值比较）的记录移动到后面去；重复上述两步，直至i=j为止；把R0复制到记录Ri(或Rj)处。 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.39.3交换排序交换排序二、快速排序2、举例：对序列32，42，7，48，15，48，12，18 进行快 速排序。 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.39.3交换排序交换排序二、快速排
10、序3、快速排序算法如下： void QuickSort(LineList R ,int first,int end)void QuickSort(LineList R ,int first,int end) int i,j; int i,j; LineList temp; LineList temp; i=first;j=end;temp=Ri;R0=Ri; / i=first;j=end;temp=Ri;R0=Ri; /初始化初始化 while(ij)while(ij) while(ij&R0.key=Rj.key) j-; / while(ij&R0.key=Rj.key) j-; /从右
11、从右端开始扫描端开始扫描 if(ij)Ri=Rj;i+;if(ij)Ri=Rj;i+; while(i=Ri.key) i+;/ while(i=Ri.key) i+;/从左从左端开始扫描端开始扫描 if(ij)Rj=Ri;j-;if(ij)Rj=Ri;j-; Ri=R0; Ri=R0; if(firsti-1) QuickSort(R,first,i-1); / if(firsti-1) QuickSort(R,first,i-1); /对左分区对左分区递归快速排序递归快速排序 if(i+1end) QuickSort(R,i+1,end); /if(i+1end) QuickSort(R,
12、i+1,end); /对右分区递归对右分区递归快速排序快速排序 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.49.4选择排序选择排序一、直接选择排序1、排序过程描述 首先设定当前无序区域的第一个位置i ，假设这个位置的 关键字最小，然后用它与无序区域中其他记录进行比较， 寻找最小记录位置。 将最小记录交换到有序区域的第i个位置，使得有序区域 扩展了一个记录，而无序区域减少了一个记录。 重复（1）、（2），直到无序区域剩下一个记录为止。 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.49.4选择排序选择排序一、直接选择排序2、举例：对序列42，7，48，15，48，25
13、，18 进行直接选 择速排序。 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.49.4选择排序选择排序一、直接选择排序3、直接选择排序算法如下：void selectSort(LineList R,int void selectSort(LineList R,int n)n) int i,j,index; int i,j,index; for(i=1;in;+i) for(i=1;in;+i) index=i; index=i; for(j=i+1;j=n;+j) for(j=i+1;j=n;+j) if(Rj.keyRindex.key) if(Rj.keyRindex.key)
14、 index=j;index=j; if(index!=i) if(index!=i) R0=Ri; R0=Ri; Ri=Rindex; Ri=Rindex; Rindex=R0; Rindex=R0; 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.49.4选择排序选择排序二、堆排序1、大根堆的定义：若将堆看成是一棵完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不小于其左、右孩子结点的值。堆顶元素为最大值。2、小根堆的定义：若将堆看成是一棵完全二叉树，则这棵完全二叉树中的每个非终端结点的值均不大于其左、右孩子结点的值。堆顶元素为最小值。 数据结构实例教程（数据结构实例教程（C
15、语言版）语言版）9.49.4选择排序选择排序二、堆排序3、筛选的定义：将根结点值与左、右子树的根结点值进行比较，并与其中小者（大者）进行交换；重复上述操作，直至叶子结点，将得到新的堆。4、排序过程描述： 从无序序列的第n/2个元素（即此无序序列对应的完全 二叉树的最后一个非终端结点）起，至第一个元素止，进 行反复筛选。 输出堆的根结点之后，以堆中最后一个元素替代之，调整 剩余元素成为一个新的堆。 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.49.4选择排序选择排序二、堆排序5、举例：对序列76,50,65,49,97,15,38,27 进行堆排序。 数据结构实例教程（数据结构实例
16、教程（C语言版）语言版）9.49.4选择排序选择排序二、堆排序5、举例：对序列76,50,65,49,97,15,38,27 进行堆排序。 6 6、堆排序算法源程序链接、堆排序算法源程序链接 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.59.5归并排序归并排序一、归并排序2、排序过程描述 设初始序列含有n个记录，则可看成n个有序的子序列，每 个子序列长度为1； 两两合并，得到n/2个长度为2或1的有序子序列； 再两两合并，如此重复，直至得到一个长度为n的有序序 列为止。1、2-路归并排序定义:将两个位置相邻的有序子序列归并为一个有序的序列。 数据结构实例教程（数据结构实例教程（C
17、语言版）语言版）9.59.5归并排序归并排序一、归并排序3、举例：对序列49,38,65,97,76,13,27进行归并排序。 4 4、归并排序算法源程序链接、归并排序算法源程序链接 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.69.6各种排序比较各种排序比较一、时间复杂度比较排序方法排序方法平均情况平均情况最好情况最好情况最坏情况最坏情况直接插入排序O(n2)O(n)O(n2)希尔排序O(nlog2n)O(n1.3)O(n2)冒泡排序O(n2)O(n)O(n2)快速排序O(nlog2n)O(nlog2n)O(n2)直接选择排序O(n2)O(n2)O(n2)堆排序O(nlog2n
18、)O(nlog2n)O(nlog2n)归并排序O(nlog2n)O(nlog2n)O(nlog2n) 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.69.6各种排序比较各种排序比较二、空间复杂度比较排序方法排序方法辅助空助空间直接插入排序O(1)希尔排序O(1)冒泡排序O(1)快速排序O(log2n)O(n)直接选择排序O(1)堆排序O(1)归并排序O(n) 数据结构实例教程（数据结构实例教程（C语言版）语言版）9.69.6各种排序比较各种排序比较三、稳定性比较排序方法排序方法稳定性定性直接插入排序稳定希尔排序不稳定冒泡排序稳定快速排序不稳定直接选择排序不稳定堆排序不稳定归并排序稳定
