地理信息系统算法课件

地理信息系统算法地理信息系统算法地理信息系统算法第一章算法设计和分析 第一节 概述第二节 算法设计原则第三节 算法复杂性的度量第四节 最优算法第一章 算法设计和分析第一节 概述第二节 算法设计原则第三节第一节概述一一、算法的概念：算法是一系列解决问题的清晰指令，也就是说，能够算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出对一定规范的输入，在有限时间内获得所要求的输出第一节 概述一、算法的概念：二、算法特性：有穷性二、算法特性：有穷性、确定性确定性、可行性可行性、有输入有输入、有输出。有输出。1.1.有穷性：对于任意一组合法输入值，在执行有穷步骤之后一有穷性：对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。定能结束，即：算法中的每个步骤都能在有限时间内完成。2.2.确定性：对于每种情况下所应执行的操作，在算法中都有确确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。行。并且在任何条件下，算法都只有一条执行路径。3.3.可行性：算法中的所有操作都必须足够基本，都可以通过已可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。经实现的基本操作运算有限次实现之。4 4.有输入：作为算法加工对象的量值，通常体现为算法中的一有输入：作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。表面上可以没有输入，实际上已被嵌入算法之中。5.5.有输出：它是一组与有输出：它是一组与“输入输入”有确定关系的量值，是算法进有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。行信息加工后得到的结果，这种确定关系即为算法的功能。第一节 概述二、算法特性：有穷性、确定性、可行性、有输入、有输出。第一节三、算法的几个要点：三、算法的几个要点：1.1.算法的每一个步骤都必须清晰、明确。算法的每一个步骤都必须清晰、明确。2.2.算法所处理的输入的值域必须仔细定义。算法所处理的输入的值域必须仔细定义。3.3.同样的一个算法可以用几种不同的形式来描述。同样的一个算法可以用几种不同的形式来描述。4.4.可能存在几种解决相同问题的算法。可能存在几种解决相同问题的算法。5.5.针对同一个问题的算法可能会基于完全不同的解题思路，而针对同一个问题的算法可能会基于完全不同的解题思路，而且解题的速度也会有明显区别。且解题的速度也会有明显区别。第一节 概述三、算法的几个要点：第一节 概述n nExample求两个正整数求两个正整数m,nm,n的最大公约数的最大公约数gcd(m,n)gcd(m,n)gcd(m,n)gcd(m,n)1.1.1.1.同一个算法有不同的表达方式：同一个算法有不同的表达方式：同一个算法有不同的表达方式：同一个算法有不同的表达方式：（1 1 1 1）第一节 概述gcd(m,n)gcd(m,n)的欧几里得算法 第一步：如果n=0，返回m的值作 为结果，结束；否则进入第二步第二步：用n去除m，将余数赋给r。第三步：将n的值赋给m，将r的值 赋给n，回第一步。Example第一节 概述gcd(m,n)的欧几里得算法 （2 2）算法Euclid(m,n)/使用欧几里得算法计算gcd(m,n)/输入：两个不全为0的非负整数m,n/输出：m，n的最大公约数While n!=0 dor m mod nm nn rReturn m第一节概述（2）算法Euclid(m,n)第一节 概述2.2.2.2.同一个问题有不同的解决方法：同一个问题有不同的解决方法：同一个问题有不同的解决方法：同一个问题有不同的解决方法：（1 1 1 1）gcd(m,n)gcd(m,n)的连续整数检测算法的连续整数检测算法 第一步：将第一步：将minm,nminm,n的值赋给的值赋给t t。第二步：第二步：m m除以除以t t，如果余数为，如果余数为0 0，则进入第三步；否则，则进入第三步；否则，进入第四步。进入第四步。第三步：第三步：n n除以除以t t，如果余数为，如果余数为0 0，则返回，则返回t t值作为结果；值作为结果；否则，进入第四步。否则，进入第四步。第四步：把第四步：把t t的值减的值减1 1。返回第二步。返回第二步。（2 2 2 2）gcd(m,n)gcd(m,n)的中学计算算法的中学计算算法 第一步：找到第一步：找到m m的所有质因数。的所有质因数。第二步：找到第二步：找到n n的所有质因数的所有质因数 第三步：从第一步和第二步中求得的质因数分解式找出所第三步：从第一步和第二步中求得的质因数分解式找出所 有的公因数。有的公因数。第四步：将第三步中找的质因数相乘，其结果作为给定数第四步：将第三步中找的质因数相乘，其结果作为给定数 字的最大公因数。字的最大公因数。第一节 概述2.同一个问题有不同的解决方法：第一节 概述算法问题求解的过程：算法问题求解的过程：算法问题求解的过程：算法问题求解的过程：第一节 概述理解问题决定：计算方法。精确和近似的解法。设计算法正确性证明分析算法根据算法写代码算法问题求解的过程：第一节 概述理解问题决定：计算方法。精确 设计算法前做的第一件事情。设计算法前做的第一件事情。仔细阅读问题的描述仔细阅读问题的描述 提出疑问提出疑问理解问题：理解问题：手工处理一些实例手工处理一些实例 考虑特殊情况考虑特殊情况 确定输入确定输入 抽象出问题，用数学表达式描述抽象出问题，用数学表达式描述选择精确解和近似解：选择精确解和近似解：某些重要的问题无法求得精确解某些重要的问题无法求得精确解 某些问题利用精确解速度慢，无法接受某些问题利用精确解速度慢，无法接受第一节 概述 设计算法前做的第一件事情。第一节算法设计技术：算法设计技术：使用算法解题的一般性方法，用于解决计算领域的多种问题。使用算法解题的一般性方法，用于解决计算领域的多种问题。详细表述算法的方法：详细表述算法的方法：自然语言：自然语言：用我们日常生活中的自然语言（可以是中文形式，用我们日常生活中的自然语言（可以是中文形式，也可以是英文形式）也可以描述算法。也可以是英文形式）也可以描述算法。伪代码：伪代码：我们可以用数学语言或约定的符号语言来描述算法。我们可以用数学语言或约定的符号语言来描述算法。流程图：流程图：一个算法可以用流程图的方式来描述，输入输出、判一个算法可以用流程图的方式来描述，输入输出、判 断、处理分别用不同的框图表示，用箭头表示流程的流断、处理分别用不同的框图表示，用箭头表示流程的流 向。这是一种描述算法的较好方法，目前在一些高级语向。这是一种描述算法的较好方法，目前在一些高级语 言程序设计中仍然采用。也有其他的图形辅助工具。言程序设计中仍然采用。也有其他的图形辅助工具。第一节 概述算法设计技术：第一节 概述证明算法的正确性证明算法的正确性：证明对于每一个合法的输入，该算法都会在有限的时间内输证明对于每一个合法的输入，该算法都会在有限的时间内输出一个满足要求的结果。出一个满足要求的结果。一般方法：数学归纳法一般方法：数学归纳法证明算法的正确性与不正确哪一个更容易？证明算法的正确性与不正确哪一个更容易？分析算法：分析算法：算法有两种效率：时间效率和空间效率。算法有两种效率：时间效率和空间效率。算法的另外两个特性：简单性和一般性。算法的另外两个特性：简单性和一般性。第一节 概述证明算法的正确性：第一节 概述为算法写代码：为算法写代码：用计算机程序实现算法。用计算机程序实现算法。在把算法转变为程序的过程中，可能会在把算法转变为程序的过程中，可能会 发生错误或者效率非常低。发生错误或者效率非常低。作为一种规律，一个好的算法是反复努力和重新修正的结果作为一种规律，一个好的算法是反复努力和重新修正的结果 算法是一个最优性问题：对于给定的问题需要花费多少力算法是一个最优性问题：对于给定的问题需要花费多少力气（资源）？气（资源）？是不是每个问题都能够用算法的方法来解决？是不是每个问题都能够用算法的方法来解决？发明或发现算法是一个非常有创造性和非常值得付出的过程！发明或发现算法是一个非常有创造性和非常值得付出的过程！发明或发现算法是一个非常有创造性和非常值得付出的过程！发明或发现算法是一个非常有创造性和非常值得付出的过程！第一节 概述为算法写代码：用计算机程序实现算法。第一节 概述算法和程序的关系：算法和程序的关系：算法和程序的关系：算法和程序的关系：（1 1）算法着重体现思路和方法，程序着重体现计算机的实现。）算法着重体现思路和方法，程序着重体现计算机的实现。（2 2）程序不一定满足有穷性（死循环），另外，程序中的指令）程序不一定满足有穷性（死循环），另外，程序中的指令 必须是机器可执行的，算法中的指令无此限制。必须是机器可执行的，算法中的指令无此限制。（3 3）一个算法若用计算机语言来书写，它就可以是一个程序。）一个算法若用计算机语言来书写，它就可以是一个程序。第一节 概述算法和程序的关系：第一节 概述第二节算法设计原则1.1.正确性：正确性：是指对于一个问题，之所以将其放在第一位是因为是指对于一个问题，之所以将其放在第一位是因为如果一个算法自身有缺陷，或者不适合于问题的求解，那么如果一个算法自身有缺陷，或者不适合于问题的求解，那么该算法将不会解决问题。该算法将不会解决问题。2.2.确定性：确定性：是指算法的每个步骤必须含义明确，对每种可能的是指算法的每个步骤必须含义明确，对每种可能的情况，算法都能给出确定的操作。即采用同一种算法，在同情况，算法都能给出确定的操作。即采用同一种算法，在同样的条件下无论计算多少次，始终能够得到确定的结果。样的条件下无论计算多少次，始终能够得到确定的结果。3.3.清晰性：清晰性：一个良好的算法必须思路清晰，结构合理。算法的一个良好的算法必须思路清晰，结构合理。算法的设计要模块化。模块化的目的是使算法结构清晰，容易阅读，设计要模块化。模块化的目的是使算法结构清晰，容易阅读，容易理解，容易测试，容易修改。容易理解，容易测试，容易修改。第二节 算法设计原则1.正确性：是指对于一个问题，之所以将其第三节算法复杂性的度量算法分析算法分析:是对一个算法需要多少计算时间和存储空间作定是对一个算法需要多少计算时间和存储空间作定 量的分析。即时间特性量的分析。即时间特性(时间复杂度时间复杂度T(n)T(n)和空间和空间 特性特性(空间复杂度空间复杂度S(n)S(n)。一个特定算法的一个特定算法的“运行工作量运行工作量”的大小，只依赖于问题的规模的大小，只依赖于问题的规模（通常用整数量（通常用整数量n n表示），或者说，它是问题规模的函数。表示），或者说，它是问题规模的函数。时间复杂度：假如，随着问题规模时间复杂度：假如，随着问题规模 n n 的增长，的增长，算法执行时算法执行时算法执行时算法执行时间的增长率和间的增长率和间的增长率和间的增长率和f(n)f(n)f(n)f(n)的增长率相同的增长率相同的增长率相同的增长率相同，则可记作：，则可记作：T(n)=O(f(n)T(n)=O(f(n)T(n)=O(f(n)T(n)=O(f(n)称称称称T(n)T(n)T(n)T(n)为算法的为算法的为算法的为算法的(渐近渐近)时间复杂度。时间复杂度。时间复杂度。时间复杂度。第三节 算法复杂性的度量算法分析:是对一个算法需要多少计算时第三节算法复杂性的度量如何估算算法的时间复杂度？如何估算算法的时间复杂度？如何估算算法的时间复杂度？如何估算算法的时间复杂度？算法算法算法算法 =控制结构控制结构控制结构控制结构(顺序、分支和循环三种顺序、分支和循环三种 )+)+)+)+原操作原操作原操作原操作（固有数据（固有数据类型的操作）类型的操作）算法的执行时间算法的执行时间算法的执行时间算法的执行时间 =原操作原操作原操作原操作(i)(i)(i)(i)的执行次数的执行次数的执行次数的执行次数原操作原操作原操作原操作(i)(i)(i)(i)的执行时间的执行时间的执行时间的执行时间算法的执行时间算法的执行时间算法的执行时间算法的执行时间 与与与与 原操作执行次数之和原操作执行次数之和原操作执行次数之和原操作执行次数之和 成正比成正比成正比成正比 从算法中选取一种对于所研究的问题来说是从算法中选取一种对于所研究的问题来说是 基本操作基本操作基本操作基本操作 的原操的原操作，以该基本操作作，以该基本操作 在算法中重复执行的次数在算法中重复执行的次数在算法中重复执行的次数在算法中重复执行的次数 作为算法运行时间的作为算法运行时间的衡量准则。衡量准则。第三节 算法复杂性的度量如何估算算法的时间复杂度？第三节算法复杂性的度量算法效率的主要指标是基本操作次数的增长次数。算法效率的主要指标是基本操作次数的增长次数。增长次数：小规模输入在运行时间上的差别不足以将高效的增长次数：小规模输入在运行时间上的差别不足以将高效的 算法和低效的算法区分开来。算法和低效的算法区分开来。第三节 算法复杂性的度量算法效率的主要指标是基本操作次数的增第三节算法复杂性的度量为了对这些增长次数进行比较和归类，计算机科学家们使用了为了对这些增长次数进行比较和归类，计算机科学家们使用了3 3种符号：种符号：O O（读（读“O”O”）：上界）：上界 （读（读”omega”omega”）：下界）：下界 （读（读”theta”theta”）：相等）：相等1.1.1.1.符号符号符号符号O O O O定义定义1 1 对于足够大的对于足够大的n n，t(n)t(n)的上界由的上界由g(n)g(n)的常数倍来确定，的常数倍来确定，即：记为即：记为t(n)t(n)O(g(n)O(g(n)t(n)t(n)cg(n)cg(n)，c c为常数为常数 n n O(n)O(n)100n+5 100n+5 O(n)O(n)n(n-1)/2 n(n-1)/2 O(n)O(n)第三节 算法复杂性的度量为了对这些增长次数进行比较和归类，计第三节算法复杂性的度量2.2.2.2.符号符号符号符号定义定义:对于足够大的对于足够大的n n，t(n)t(n)的下界由的下界由g(n)g(n)的常数倍来确定，的常数倍来确定，即：记为即：记为t(n)t(n)(g(n)(g(n)t(n)t(n)cg(n)cg(n)，c c为常数为常数 nn(n)(n)n(n+1)n(n+1)(n)(n)4n+5 4n+5(n)(n)第三节 算法复杂性的度量2.符号第三节算法复杂性的度量符号符号定义定义:对于足够大的对于足够大的n n，t(n)t(n)的上界和下界由的上界和下界由g(n)g(n)的常数倍来确的常数倍来确 定，即：定，即：c1g(n)t(n)c2g(n)c1g(n)t(n)c2g(n)，c1,c2c1,c2为常数为常数 记为记为 t(n)t(n)(g(n)(g(n)n+3n+2 n+3n+2 (n)n(n-1)/2 (n)n(n-1)/2 (n)4n+5 (n)4n+5(n)(n)第三节 算法复杂性的度量符号第三节算法复杂性的度量渐进符号的有用特性渐进符号的有用特性渐进符号的有用特性渐进符号的有用特性 定理定理:如果如果t t1 1(n)O(g(n)O(g1 1(n)(n)并且并且t t2 2(n)O(g(n)O(g2 2(n)(n)，则，则t t1 1(n)+(n)+t t2 2(n)O(max(g(n)O(max(g1 1(n),g(n),g2 2(n)(n)对于符号对于符号和和，该定理也成立。，该定理也成立。该定理表明：该定理表明：当算法由两个连续执行部分组成时，该算法的当算法由两个连续执行部分组成时，该算法的整体效率由具有较大增长次数的那部分所决定。整体效率由具有较大增长次数的那部分所决定。利用极限比较增长次数利用极限比较增长次数利用极限比较增长次数利用极限比较增长次数前两种情况意味着前两种情况意味着t(n)t(n)O(g(n)O(g(n)后两种情况意味着后两种情况意味着t(n)t(n)(g(n)(g(n)第二种情况意味着第二种情况意味着t(n)t(n)(g(n)(g(n)第三节 算法复杂性的度量渐进符号的有用特性第三节算法复杂性的度量基本的效率类型基本的效率类型基本的效率类型基本的效率类型 指数时间算法一般有：指数时间算法一般有：O()O(n!)O()O()O(n!)O()。常量常量(1)(1)、对数、对数(logn)(logn)、线性、线性(n)(n)、平方平方(n)(n)、立方、立方(n)(n)、指数、指数(2n)(2n)、阶乘阶乘(n!)(n!)其中有六种多项式时间算法最其中有六种多项式时间算法最为常见，其关系为：为常见，其关系为：O(1)O(logn)O(n)O(nlogn)O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(n2)O(n3)；第三节 算法复杂性的度量基本的效率类型 第三节算法复杂性的度量void void void void mult(mult(intintintint a,a,intintintint b,b,int&int&int&int&c)c)/以二维数组存储矩阵元素，以二维数组存储矩阵元素，c c 为为 a a 和和 b b 的乘积的乘积 forforforfor(i=1;i=n;+i)(i=1;i=n;+i)forforforfor(j=1;j=n;+j)(j=1;j=n;+j)ci,j=0;ci,j=0;forforforfor(k=1;k=n;(k=1;k=n;+k)k)ci,j+=ci,j+=ai,kai,k*bk,j;bk,j;基本操作基本操作:乘法乘法乘法乘法操作操作 时间复杂度时间复杂度:O(nO(nO(nO(n )例例一一两两个个矩矩阵阵相相乘乘第三节 算法复杂性的度量void mult(int a,第三节算法复杂性的度量voidvoidvoidvoid select_sort(select_sort(int&int&int&int&a,a,intintintint n)n)/将将将将 a a a a 中整数序列重新排列成自小至大有序的整数序列中整数序列重新排列成自小至大有序的整数序列中整数序列重新排列成自小至大有序的整数序列中整数序列重新排列成自小至大有序的整数序列。for for for for(i=0;i n-1;(i=0;i n-1;+i)i)j=i;j=i;/选择第选择第选择第选择第 i i i i 个最小元素个最小元素个最小元素个最小元素 forforforfor (k=i+1;k n;(k=i+1;k n;+k)k)if if if if(ak(ak 0)f(n)=1)(n0)f(n)=1(n=0)1(n=0)则当则当0 0时，须用时，须用f(n-1)f(n-1)来定义来定义f(n),f(n),用用f(n-1-1)f(n-1-1)来定义来定义f(n-f(n-1)1)当当n=0n=0时，时，f(n)=1f(n)=1。由上例我们可看出，递归定义有两个要素：由上例我们可看出，递归定义有两个要素：（1 1）递归边界条件。也就是所描述问题的最简单情况，它本身）递归边界条件。也就是所描述问题的最简单情况，它本身不再使用递归的定义。如上例，当不再使用递归的定义。如上例，当n=0n=0时，时，f(n)=1f(n)=1，不使用，不使用f(n-f(n-1)1)来定义。来定义。（2 2）递归定义：使问题向边界条件转化的规则。递归定义必须）递归定义：使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。如上例：能使问题越来越简单。如上例：f(n)f(n)由由f(n-1)f(n-1)定义，越来越靠定义，越来越靠近近f(0),f(0),也即边界条件。最简单的情况是也即边界条件。最简单的情况是f(0)=1f(0)=1。递归算法的效率往往很低递归算法的效率往往很低,费时和费内存空间费时和费内存空间.但是递归也有但是递归也有其长处其长处,它能使一个蕴含递归关系且结构复杂的程序简化精炼它能使一个蕴含递归关系且结构复杂的程序简化精炼,增加可读性增加可读性.特别是在难于找到从边界到解的全过程的情况下特别是在难于找到从边界到解的全过程的情况下,如果把问题推进一步简化而其结果仍维持原问题的关系如果把问题推进一步简化而其结果仍维持原问题的关系,则采则采用递归算法编程比较合适用递归算法编程比较合适.常用算法分析例如：定义函数f(n)为：f(n)=n*f(n各种排序算法比较一、插入排序一、插入排序(Insertion Sort)(Insertion Sort)1 1）基本思想：每次将一个待排序的数据元素，插入到前面已基本思想：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。序数据元素全部插入完为止。2 2）排序过程：排序过程：【示例示例】：初始关键字初始关键字 49 38 65 97 76 13 27 49 49 38 65 97 76 13 27 49 J=2(38)38 49 65 97 76 13 27 49 J=2(38)38 49 65 97 76 13 27 49 J=3(65)38 49 65 97 76 13 27 49 J=3(65)38 49 65 97 76 13 27 49 J=4(97)38 49 65 97 76 13 27 49 J=4(97)38 49 65 97 76 13 27 49 J=5(76)38 49 65 76 97 13 27 49 J=5(76)38 49 65 76 97 13 27 49 J=6(13)13 38 49 65 76 97 27 49 J=6(13)13 38 49 65 76 97 27 49 J=7(27)13 27 38 49 65 76 97 49 J=7(27)13 27 38 49 65 76 97 49 J=8(49)13 27 38 49 49 65 76 97 J=8(49)13 27 38 49 49 65 76 97 各种排序算法比较一、插入排序(Insertion Sort)各种排序算法比较直接插入排序直接插入排序直接插入排序直接插入排序:void si_sort(int e,int n)void si_sort(int e,int n)int i,j,t;int i,j,t;for(i=0;i n;i+)for(i=0;i=0&t=0&tej;j-)ej+1=ej;ej+1=ej;ej+1=t;ej+1=t;各种排序算法比较直接插入排序:各种排序算法比较二、选择排序二、选择排序二、选择排序二、选择排序1 1）基本思想：每一趟从待排序的数据元素中选出最小（或最基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。待排序的数据元素排完。2 2）排序过程：排序过程：【示例示例】：初始关键字初始关键字 49 38 65 97 76 13 27 4949 38 65 97 76 13 27 49 第一趟排序后第一趟排序后 13 13 38 65 97 76 49 27 4938 65 97 76 49 27 49 第二趟排序后第二趟排序后 13 27 13 27 65 97 76 49 38 4965 97 76 49 38 49 第三趟排序后第三趟排序后 13 27 38 97 76 49 65 4913 27 38 97 76 49 65 49 第四趟排序后第四趟排序后 13 27 38 49 49 97 65 7613 27 38 49 49 97 65 76 第五趟排序后第五趟排序后 13 27 38 49 49 97 97 7613 27 38 49 49 97 97 76 第六趟排序后第六趟排序后 13 27 38 49 49 76 76 9713 27 38 49 49 76 76 97 第七趟排序后第七趟排序后 13 27 38 49 49 76 76 9713 27 38 49 49 76 76 97 最后排序结果最后排序结果 13 27 38 49 49 76 76 9713 27 38 49 49 76 76 97 各种排序算法比较二、选择排序各种排序算法比较 选择排序主要是每一趟从待排序列中选取一个关键码最小的选择排序主要是每一趟从待排序列中选取一个关键码最小的记录，也即第一趟从记录，也即第一趟从n n个记录中选取关键码最小的记录，第二趟个记录中选取关键码最小的记录，第二趟从剩下的从剩下的n-1n-1个记录中选取关键码最小的记录，直到整个序列的个记录中选取关键码最小的记录，直到整个序列的记录选完。这样，由选取记录的顺序，便得到按关键码有序的记录选完。这样，由选取记录的顺序，便得到按关键码有序的序列。序列。操作方法：第一趟，从操作方法：第一趟，从n n个记录中找出关键码最小的记录与第个记录中找出关键码最小的记录与第一个记录交换；第二趟，从第二个记录开始的一个记录交换；第二趟，从第二个记录开始的n-1n-1个记录中再选个记录中再选出关键码最小的记录与第二个记录交换；如此，第出关键码最小的记录与第二个记录交换；如此，第i i趟，则从第趟，则从第i i个记录开始的个记录开始的n-i+1n-i+1个记录中选出关键码最小的记录与第个记录中选出关键码最小的记录与第i i个记个记录交换，直到整个序列按关键码有序。录交换，直到整个序列按关键码有序。各种排序算法比较 选择排序主要是每一趟从待排序列中选取一个各种排序算法比较算法算法算法算法:void SelectSort(S_TBL*s)void SelectSort(S_TBL*s)for(i=1 for(i=1；ilengthilength；i+)i+)/*/*作作length-1length-1趟选取趟选取*/for(j=i+1 for(j=i+1，t=it=i；jlengthjlength；j+)j+)/*/*在在i i开始的开始的length-n+1length-n+1个记录中选关键码最小的记录个记录中选关键码最小的记录*/if(s-elemt.keys-elemj.key)if(s-elemt.keys-elemj.key)t=j t=j；/*t/*t中存放关键码最小记录的下标中存放关键码最小记录的下标*/s-elemts-elemi s-elemts-elemi；/*/*关键码最小的记录与第关键码最小的记录与第i i个记录交换个记录交换*/各种排序算法比较算法:各种排序算法比较三、冒泡排序三、冒泡排序三、冒泡排序三、冒泡排序(BubbleSort)(BubbleSort)(BubbleSort)(BubbleSort)1 1）基本思想：两两比较待排序数据元素的大小，发现两个数据）基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止元素的次序相反时即进行交换，直到没有反序的数据元素为止2 2）排序过程：设想被排序的数组）排序过程：设想被排序的数组R R1.N1.N垂直竖立，将每个垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组原则，从下往上扫描数组R R，凡扫描到违反本原则的轻气泡，就，凡扫描到违反本原则的轻气泡，就使其向上使其向上“漂浮漂浮”，如此反复进行，直至最后任何两个气泡都，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。是轻者在上，重者在下为止。示例：示例：49 13 13 13 13 13 13 1349 13 13 13 13 13 13 13 38 49 27 27 27 27 27 27 38 49 27 27 27 27 27 27 65 38 49 38 38 38 38 38 65 38 49 38 38 38 38 38 97 65 38 49 49 49 49 49 97 65 38 49 49 49 49 49 76 97 65 49 49 49 49 49 76 97 65 49 49 49 49 49 13 76 97 65 65 65 65 65 13 76 97 65 65 65 65 65 27 27 76 97 76 76 76 76 27 27 76 97 76 76 76 76 49 49 49 76 97 97 97 97 49 49 49 76 97 97 97 97 各种排序算法比较三、冒泡排序(BubbleSort)各种排序算法比较冒泡排序算法实践：冒泡排序算法实践：冒泡排序算法实践：冒泡排序算法实践：void sb_sort(int e,int n)void sb_sort(int e,int n)int j,h,tint j,h,t，i;i;i=1 i=1；for(h=n-i;h0;i+)for(h=n-i;h0;i+)for(j=0;jh;j+)for(j=0;jh;j+)if(ej ej+1)if(ej ej+1)t=ej;ej=ej+1;ej+1=t;t=ej;ej=ej+1;ej+1=t;各种排序算法比较冒泡排序算法实践：各种排序算法比较冒泡排序冒泡排序冒泡排序冒泡排序(Bubble Sort)(Bubble Sort)(Bubble Sort)(Bubble Sort)算法分析：算法分析：算法分析：算法分析：先来看看待排序列一趟冒泡的过程：设先来看看待排序列一趟冒泡的过程：设1jn1ri+1.keyri.keyri+1.key时，时，r0=rir0=ri；ri=ri+1ri=ri+1；ri+1=r0ri+1=r0；将；将riri与与ri+1ri+1交换；交换；i=i+1i=i+1；调整对下两个记录进行两两比较，转调整对下两个记录进行两两比较，转冒泡排序方法：对冒泡排序方法：对n n个记录的表，第一趟冒泡得到一个关键码最大个记录的表，第一趟冒泡得到一个关键码最大的记录的记录rnrn，第二趟冒泡对，第二趟冒泡对n-1n-1个记录的表，再得到一个关键码最个记录的表，再得到一个关键码最大的记录大的记录rn-1rn-1，如此重复，直到，如此重复，直到n n个记录按关键码有序的表。个记录按关键码有序的表。各种排序算法比较冒泡排序(Bubble Sort)算法分析：各种排序算法比较四四四四、快速排序（快速排序（快速排序（快速排序（Quick SortQuick SortQuick SortQuick Sort）1 1）基本思想：）基本思想：在当前无序区在当前无序区R1.HR1.H中任取一个数据元素作为比较的中任取一个数据元素作为比较的“基基准准”(不妨记为不妨记为X)X)，用此基准将当前无序区划分为左右两个较小，用此基准将当前无序区划分为左右两个较小的无序区：的无序区：R1.I-1R1.I-1和和RI+1.HRI+1.H，且左边的无序子区中数据，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准等于基准元素，而基准X X则位于最终排序的位置上，即则位于最终排序的位置上，即R1.I-R1.I-1X.KeyRI+1.H(1IH)1X.KeyRI+1.H(1IH)，当，当R1.I-1R1.I-1和和RI+1.HRI+1.H均均非空时，分别对它们进行上述的划分过程，直至所有无序子区非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。中的数据元素均已排序为止。各种排序算法比较四、快速排序（Quick Sort）各种排序算法比较2 2）排序过程：）排序过程：示例示例:初始关键字初始关键字 49 38 65 97 76 13 27 4949 38 65 97 76 13 27 49第一次交换后第一次交换后27 38 65 97 76 13 49 4927 38 65 97 76 13 49 49第二次交换后第二次交换后27 38 49 97 76 13 65 4927 38 49 97 76 13 65 49J J向左扫描，位置不变，第三次交换后向左扫描，位置不变，第三次交换后27 38 13 97 76 49 65 4927 38 13 97 76 49 65 49I I向右扫描，位置不变，第四次交换后向右扫描，位置不变，第四次交换后27 38 13 49 76 97 65 4927 38 13 49 76 97 65 49J J向左扫描向左扫描 27 38 13 49 76 97 65 4927 38 13 49 76 97 65 49各种排序算法比较2）排序过程：各种排序算法比较（一次划分过程）（一次划分过程）初始关键字初始关键字49 38 65 97 76 13 27 4949 38 65 97 76 13 27 49一趟排序之后一趟排序之后27 38 1327 38 13 49 49 76 97 65 4976 97 65 49二趟排序之后二趟排序之后1313 27 27 3838 49 49 49 6549 6576 76 9797三趟排序之后三趟排序之后 13 27 38 49 49 13 27 38 49 49 656576 9776 97最后的排序结果最后的排序结果 13 27 38 49 49 65 76 9713 27 38 49 49 65 76 97 快速排序是通过比较关键码、交换记录，以某个记录为界快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点该记录称为支点)，将待排序列分成两部分。其中，一部分所，将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。划分，直到整个序列按关键码有序。各种排序算法比较（一次划分过程）各种排序算法比较算法算法算法算法:void QSort(S_TBL*tbl,int low,int high)/*void QSort(S_TBL*tbl,int low,int high)/*递归形式的快递归形式的快排序排序*/*/*对顺序表对顺序表tbltbl中的子序列中的子序列tbl-lowhightbl-lowhigh作快排序作快排序*/if(lowhigh)if(lowhigh)pivotloc=partition(tbl,low,high);/*pivotloc=partition(tbl,low,high);/*将表一分为二将表一分为二*/QSort(tbl,low,pivotloc-1);/*QSort(tbl,low,pivotloc-1);/*对低子表递归排序对低子表递归排序*/QSort(tbl,pivotloc+1,high);/*QSort(tbl,pivotloc+1,high);/*对高子表递归排序对高子表递归排序*/各种排序算法比较算法:各种排序算法比较效率分析效率分析效率分析效率分析:空间效率空间效率：快速排序是递归的，每层递归调用时的指针和参数：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层次数与上述二叉树的深度一致。均要用栈来存放，递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为因而，存储开销在理想情况下为O(log2n)O(log2n)，即树的高度；在最，即树的高度；在最坏情况下，即二叉树是一个单链，为坏情况下，即二叉树是一个单链，为O(n)O(n)。时间效率时间效率：在：在n n个记录的待排序列中，一次划分需要约个记录的待排序列中，一次划分需要约n n次关键次关键码比较，时效为码比较，时效为O(n)O(n)，若设，若设T(n)T(n)为对为对n n个记录的待排序列进行快个记录的待排序列进行快速排序所需时间。速排序所需时间。理想情况下：每次划分，正好将分成两个等长的子序列，则理想情况下：每次划分，正好将分成两个等长的子序列，则 T(n)cn+2T(n/2)cT(n)cn+2T(n/2)c是一个常数是一个常数 cn+2(cn/2+2T(n/4)=2cn+4T(n/4)cn+2(cn/2+2T(n/4)=2cn+4T(n/4)2cn+4(cn/4+T(n/8)=3cn+8T(n/8)2cn+4(cn/4+T(n/8)=3cn+8T(n/8)cnlog2n+nT(1)=O(nlog2n)cnlog2n+nT(1)=O(nlog2n)各种排序算法比较效率分析:各种排序算法比较最坏情况下：即每次划分，只得到一个子序列，时效最坏情况下：即每次划分，只得到一个子序列，时效O(n)O(n)。快速排序是通常被认为在同数量级（快速排序是通常被认为在同数量级（O(nlog2n)O(nlog2n)）的排序方法中）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中三者取中法法”来选取支点记录，即将排序区间的两个端点与中点三个记来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。序方法。各种排序算法比较最坏情况下：即每次划分，只得到一个子序列，时各种排序算法比较五、堆排序五、堆排序五、堆排序五、堆排序(Heap Sort)(Heap Sort)(Heap Sort)(Heap Sort)1 1）基本思想：堆排序是一树形选择排序，在排序过程中，将）基本思想：堆排序是一树形选择排序，在排序过程中，将R1.NR1.N看成是一颗完全二叉树的顺序存储结构，利用完全二叉看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。树中双亲结点和孩子结点之间的内在关系来选择最小的元素。2 2）堆的定义）堆的定义:N:N个元素的序列个元素的序列K1,K2,K3,.,Kn.K1,K2,K3,.,Kn.称为堆，当且称为堆，当且仅当该序列满足特性：仅当该序列满足特性：KiK2i Ki K2i+1(1 I N/2)KiK2i Ki K2i+1(1 I N/2)堆实质上是满足如下性质的完全二叉树：树中任一非叶子结堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,7010,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。大于等于其孩子的关键字，则称之为大根堆。各种排序算法比较五、堆排序(Heap Sort)各种排序算法比较3 3）排序过程：堆排序正是利用小根堆（或大根堆）来选取当前）排序过程：堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的记录实现排序的。我们不妨利无序区中关键字小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。各种排序算法比较3）排序过程：堆排序正是利用小根堆（或大根堆各种排序算法比较示例：对关键字序列示例：对关键字序列4242，1313，9191，2323，2424，1616，0505，8888建堆建堆 堆排序堆排序void sift(e,n,s)void sift(e,n,s)int e;int e;int n;int n;int s;int s;int t,k,j;int t,k,j;t=es;t=es;k=s;j=2*k+1;k=s;j=2*k+1;while(jn)while(jn)if(jn-1&ejej+1)if(jn-1&ejej+1)j+;j+;if(tej)if(t=0;i-)for(i=n/2-1;i=0;i-)sift(e,n,i);sift(e,n,i);for(k=n-1;k=1;k-)for(k=n-1;k=1;k-)t=e0;e0=ek;ek=t;t=e0;e0=ek;ek=t;sift(e,k,0);sift(e,k,0);各种排序算法比较k=j;各种排序算法比较几种排序算法的比较和选择几种排序算法的比较和选择几种排序算法的比较和选择几种排序算法的比较和选择:1 1）选取排序方法需要考虑的因素：）选取排序方法需要考虑的因素：(1)(1)待排序的元素数目待排序的元素数目n n；(2)(2)元素本身信息量的大小；元素本身信息量的大小；(3)(3)关键字的结构及其分布情况；关键字的结构及其分布情况；(4)(4)语言工具的条件，辅助空间的大小等。语言工具的条件，辅助空间的大小等。2 2）小结：）小结：(1)(1)若若n n较小较小(n=50)(n=50)，则可以采用直接插入排序或直接选，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。序多，因而当记录本身信息量较大时，用直接选择排序较好。(2)(2)若文件的初始状态已按关键字基本有序，则选用直接插若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。入或冒泡排序为宜。各种排序算法比较几种排序算法的比较和选择:各种排序算法比较(3)(3)若若n n较大，则应采用时间复杂度为较大，则应采用时间复杂度为O(nlog2n)O(nlog2n)的排序方法：快的排序方法：快速排序、堆排序或归并排序。速排序、堆排序或归并排序。快速排序是目前基于比较的内部快速排序是目前基于比较的内部排序法中被认为是最好的方法。排序法中被认为是最好的方法。(4)(4)在基于比较排序方法中，每次比较两个关键字的大小之后，在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的判定过程，由此可以证明：当文件的n n个关键字随机分布时，任个关键字随机分布时，任何借助于何借助于“比较比较”的排序算法，至少需要的排序算法，至少需要O(nlog2n)O(nlog2n)的时间。的时间。(5)(5)当记录本身信息量较大时，为避免耗费大量时间移动记录，当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。可以用链表作为存储结构。各种排序算法比较(3)若n较大，则应采用时间复杂度为O(nl各种排序算法比较比较一下上面谈到的各种内部排序方法：比较一下上面谈到的各种内部排序方法：首先，从时间性能上说：首先，从时间性能上说：1.1.按平均的时间性能来分，有三类排序方法：按平均的时间性能来分，有三类排序方法：时间复杂度为时间复杂度为O(nlogn)O(nlogn)的方法有：快速排序、堆排序和归并排的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；序，其中以快速排序为最好；时间复杂度为时间复杂度为O(n)O(n)的有：直接插入排序、起泡排序和简单选择的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；序的记录序列尤为如此；时间复杂度为时间复杂度为O(n)O(n)的排序方法只有基数排序。的排序方法只有基数排序。2.2.当待排记录序列按关键字顺序有序时，直接插入排序和起泡当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到排序能达到O(n)O(n)的时间复杂度的时间复杂度;而对于快速排序而言，这是最不而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为好的情况，此时的时间性能蜕化为O(n)O(n)，因此是应该尽量避免，因此是应该尽量避免的情况。的情况。3.3.简单选择排序、堆排序和归并排序的时间性能不随记录序列简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。中关键字的分布而改变。各种排序算法比较比较一下上面谈到的各种内部排序方法：