第3章计算机软件基础排序技术.ppt

1、第3章搜索和排序技术，3.1基本搜索技术，3.2基本排序技术，上一课所学知识的复习，如果顺序存储结构的线性表出现故障，可以使用什么方法来搜索？如果它是有序的，有什么方法可以找到它？如果是无序的，有什么方法可以找到链式存储结构的线性表？如果它是有序的，有什么方法可以找到它？顺序搜索，二等分搜索，顺序搜索，顺序搜索，如何实现搜索算法？3.2基本排序技术，排序也是数据处理的一个重要内容，所谓排序是指将一个无序的序列排序成一个有序的按非递减顺序排列的值序列。分类可以在各种存储结构下实现。在本节介绍的排序方法中，被排序的对象通常被认为是按顺序存储的线性表，这可以通过编程中的一维数组来实现。3.2基本排序

2、技术，我们根据排序算法的特点对其进行分类：互换类-气泡排序和快速排序，插入类-简单插入排序和希尔排序，选择类-简单选择排序和堆排序、1。C语言课程中的冒泡排序算法，3.2.1冒泡排序和快速排序。第一次排序如下：3 7 5 6 8 0第一3和7比较，3 7 5 6 8 0第二7和5比较，3 5 7 6 8 0第三7和6比较，3 5 6 7 8 0第四7和8比较，3 5 6 7 8 0第五8和0比较，第一次排序中3 5 6 7 0 8，6个数字比较5次，比较6个数字中最好的。第二次排序如下：3 5 6 7 0 8第一次3和5比较，3 5 6 7 0 8第二次5和6比较，3 5 6 7 0 8第三次

3、6和7比较，3 5 6 7 0 8第四次7和0比较，3 5 6 0 7 8第二次排序，最大数8不需要参与比较，其余5个数比较4次， 其中最大数量为7行，依此类推：第三次比较进行三次，第四次比较在6 7 8中进行两次，第五次比较在5 6 7 8中进行一次，最后在3 5 6 7 8中还剩一个数字0，所以不需要再次比较，排序结果为0.35678。 从上面的过程中，我们可以看到n个数字应该被比较n-1次，而在第j次比较中，n-j次应该每两次比较。#定义n6 main()int aN；int i，j，t；对于(I=0；IAI 1)t=ai；ai=ai 1；ai 1=t；打印(已排序的数字：n)；程序运行

4、如下：3 7 5 6 8 0 3 5 6 7 8，动画演示，3.2.1冒泡排序和快速排序-交换排序法，1冒泡排序，首先，从表头到表尾扫描线性表，并在扫描过程中逐个比较相邻两个元素的大小。如果两个相邻元素中的前元素大于后元素，则它们被互换，这称为逆序消去。显然，在扫描过程中，两个相邻元素中最大的一个被连续移回，最后线性表中最大的一个被改变到表中的最后一个。然后从后向前扫描剩余的线性表。同样，在扫描过程中逐个比较两个相邻元素的大小。如果两个相邻元素的后元素小于前元素，它们将被互换，从而消除相反的顺序。显然，在扫描过程中，两个相邻元素中较小的一个被连续向前移动，最后剩余的线性表格中最小的一个被改变到

5、表格的前面，并且对剩余的线性表格重复上述过程，直到剩余的线性表格是空的，此时线性表格已经变得有序。PROCESSE BUBSORT(V，n)k1；mnWHILE (km) DO子表不为空jm1；M0扫描子表IF (V(i)V(i1)然后找到交换dv (I)的相反顺序；V(I)V(i1)；v(i1)d；mi jk1K0 FOR im TO j BY 1 DO扫描子表IF (V(i1) V(i)，然后从后向前查找交换dv (i)的相反顺序；V(I)V(i1)；v(i1)d；Ki RETURN，输入：无序序列v (1: n)。输出：有序序列v (1: n)。，bubble sort-算法描述，m，k

6、，m，m，k，m，k，bubble sort(v，n)int n；ET v；int m，k，j，I；ET d；k0；mn1而(km) /*子表不为空*/jm1；m0；for(ik；ij；I) /*从前到后扫描*/if(VI v1)/*按相反顺序交换*/DVI；vipi 1；vi 1dmi；jk1。k0；for(im；ij；I) /*从后向前扫描*/if (vi1 vi) /*按相反顺序交换*/DVI；vivi-1；VI-1d；ki；返回；程序演示，冒泡排序-算法描述，在冒泡排序中，因为在扫描期间只比较两个相邻的元素，所以在交换两个相邻的元素时只能消除一个逆序，这是低效的。2.快速排序，算法优化

7、：如果通过交换两个(不相邻的)元素可以消除线性表中的多个逆序，排序速度将大大加快。下面我们将介绍的快速排序是气泡排序算法的优化。2.快速排序，(1)逐渐减少J，将P(j)与T逐一比较，直到找到P(j)T，并将P(j)移到P(i)。(2)逐渐增加I，逐个比较P(i)和T，直到找到P(i)T，并将P(i)移动到P(j)的位置。上述两个操作交替进行，直到指针I和j指向相同的位置(即ij)，此时t移动到P(i)的位置。首先，从表格的第一个、中间和最后一个元素中选择中间项目，将其设置为P(k)，将P(k)指定为t，然后将表格中的第一个元素移动到P(k)的位置。然后设置两个指针，分别指向表的开始和最后一个

8、位置。重复以下两个步骤：快速排序-思路，动画演示，输入：要划分的子表P (m: n)。输出：除法后分割线的位置I。线性表分区，过程分割(P，m，n，I)选择P(k)，其中mkntp(k)；P(k)P(m)im；Jn，快速排序-算法描述，当(ij)做当(p (j) t)和(ij)做jj1if (ij)然后p(I)p(j)；ii1 WHILE (P(i)T)和(ij)DO ii1 IF(ij)THEN P(j)P(I)；Jj1 P(i)T RETURN，快速排序算法描述，PRocESS QKSORT 1(P，m，n) IF (nm) THEN的子表不是空的SPLIT(P，m，n，I)；分区QKSO

9、RT1(P，m，i1)；快速排序前面的子表QKSORT1(p，i1，n)；快速排序后面的子表。RETURN是一个快速排序的递归算法。输入：要排序的子表p (m: n)。输出：有序子表p (m: n)。快速排序算法描述，qksort1(p，m，n) int m，n；ET p；int I；如果(nm) /*子表不为空*/isplit(p，m，n)；/*分区*/qksort1(p，m，i1)；/*快速排序前面的子表*/qksort1(p，i1，n)；/*快速排序以下子表*/返回；快速排序-算法描述，int split(p，m，n) /*返回边界位置*/int m，n；ET p；int i，j，k，u

10、；外星人。im；jn；k(ij)/2；if(pipj)(pj PK)uj；/*选择一个元素*/else if(pipk)(pkpj)uk；else uiTPU；pupi而我！(j)而(ij)(pjt)jj 1；if(ij)pipj；ii1而(ij)(pit)ii1；if(ij)pj pi；jj1坑；返回(I)；快速排序-算法描述，程序演示，3.2.2简单插入排序和希尔排序-插入类排序，1。简单的插入排序，即所谓的插入排序，是将无序序列中的每个元素依次插入到有序的线性表中。在线性表中，只包含第一个元素的子表可视为有序表。从线性表的第二个元素到最后一个元素，每个元素都被逐个插入到有序子表中。假设线

11、性表中的第一个j-1元素已经排序。现在，线性表中的jth元素应该被插入到之前的有序子表中。插入过程如下：1135769，J6，5173169，J2，1573169，J，1573169，J，1357169，J，1135。J7，3，4，5，动画演示，J2到中国的程序；(k0)和(P(k)T)DO P(k1)P(k)；Kk1 P(k1)T RETURN，输入：要排序的序列p (1: n)。输出：有序序列p (1: n)。，简单插入排序算法描述，insert，n)int n；ET p；int j，k；外星人。对于(J1；jn；(j)tpj；kj1而(k0)(PKT)pk1pk；kk1pk1t。返回；程

12、序演示，简单的插入排序算法描述，希尔排序思路：将整个无序序列分成几个子序列，并分别插入和排序子序列。分割方法如下：以一定增量h分隔的元素形成一个子序列。在排序过程中，增量一个接一个地减少，当h减少到1时，通过插入一次完成排序。通常，增量序列是htn/2k(k1，2，log2n)，其中n是要排序的序列的长度。2。希尔排序、输入：要排序的序列p (1: n)。输出：有序序列p (1: n)。程序SHLSORT(P，n)HN/2 WHILE(h0)DO FOR jh1 TO n DO tP(j)；同时(i0)和(P(I)t)DO P(ih)P(I)；Iih P(ih)t hh/2 RETURN，hi

13、ll排序算法描述，shlsort(p，n)int n；ET p；国际h，j，I；外星人。HN/2；而(h0)为(JH；jn1(j)tpj；ijh而(i0)(pit)PIH pi；iihpihthh/2；返回；希尔排序-算法描述，程序演示，3.2.3简单选择排序和堆排序，1。简单选择排序，动画演示，输入：无序序列p (1: n)。输出：有序序列p (1: n)。如果P(j)P(k)然后kj IF (ki)然后dP(i)，则为i0到n2 DO ki的程序选择(P，n)；P(I)P(k)；P(k)d RETURN，简单选择和排序算法描述，selesort(p，n)int n；ET p；int i，j

14、，k；ET d；对于(i0；in2ii1)ki；对于(ji1jn1jj1)if(pj PK)kj；如果(k！新闻部；pipkkd。返回；简单的选择排序算法描述，程序演示，堆的定义：一个有n个元素(h1，h2，h n)的序列被称为堆。满足堆排序(i1，2，n/2)。根据堆的定义，堆的顶部元素(即第一个元素)必须是最大的项目或最小的项目。或者具有n个元素(h1，h2，h n)的序列，当且仅当满足(i1，2，n/2)时，称为堆。“最大”堆“最小”堆，序列(91，85，53，36，47，30，24，12)是一个堆吗？调整并构建具有n个节点(由一维数组h (1: n)表示)的完整二叉树中的堆。假设节点H

15、(m)的左右子树都是堆，则以H(m)为根节点的子树也调整为堆。调整堆输入：完整的二叉树数组h (1: n)。其中节点H(m)的左右子树是堆。输出：以H(m)为根节点的子树就是堆。程序筛选(H，n，m)THh(m)；j2m WHILE (jn) DO IF (jn)和(H(j)H(j1)然后jj1 IF (tH(j)然后H(m)H(j)；mj；J2m否则jn1 H(m)t RETURN，(1)首先，一个无序的序列被构建到一个堆中。(2)然后将堆的顶部元素(序列中最大的项目)与堆中的最后一个元素(最大的项目应该在序列的末尾)交换。不考虑最后一个元素，只考虑由前n1个元素组成的子序列。显然，子序列不再是一个堆，但是左右子树仍然是一个堆，所以子序列可以调整为一个堆。重复步骤(2)，直到剩余的子序列为空。堆排序输入：无序序列h (1: n)。输出：无序序列h (1: n)。程序HEAPSORT(H，n)kn/2FOR ik TO 1 BY 1 DO SIFT(H，n，I)for in TO 2 BY 1 DO th(1)；H(1)H(I)；将堆栈顶部元素更改为最后一个SIFT(H，i1，1)，以调整累积RETURN，heapsort(