第7章-常用查找与排序算法ppt课件.ppt
第7章-常用查找与排序算法第7章 常用查找与排序算法7.1 算法概述算法概述7.2 查找算法查找算法7.3 排序算法排序算法目录目录7.1 算法概述算法概述7.1.1 算法的描述算法的描述7.1.2 算法的特征算法的特征7.1.3 算法的评估算法的评估7.1.1 7.1.1 算法的描述算法的描述 描述算法有多种不同的工具，采用不同的算法描述工具描述算法有多种不同的工具，采用不同的算法描述工具对算法的质量有很大的影响。对算法的质量有很大的影响。 描述一个算法可以采用自然语言、流程图、描述一个算法可以采用自然语言、流程图、N-S图、伪代图、伪代码语言、计算机程序设计语言等方式。码语言、计算机程序设计语言等方式。7.1.2 7.1.2 算法的特性算法的特性 设计算法应遵循以下设计算法应遵循以下5个特性：个特性：（1）有穷性。）有穷性。（2）确定性。）确定性。（3）有效性。）有效性。（4）零或多个输入。）零或多个输入。（5）一个或多个输出。）一个或多个输出。7.1.3 7.1.3 算法的算法的评估评估 一般从以下四方面对算法进行评价。一般从以下四方面对算法进行评价。（1）正确性。）正确性。（2）可读性。）可读性。（3）健壮性。）健壮性。（4）高效性（低时间复杂度和空间复杂度）。）高效性（低时间复杂度和空间复杂度）。7.2 查找算法查找算法7.2.1 顺序查找算法7.2.2 二分查找算法二分查找算法7.2.1 7.2.1 顺序查找算法顺序查找算法 从数组的第一个元素开始，依次取出各个数组元素与从数组的第一个元素开始，依次取出各个数组元素与X比比较，一旦相等就说明数组中存在数较，一旦相等就说明数组中存在数X，查找过程就可以结，查找过程就可以结束；若直到取出数组的最后一个元素还没有发现和束；若直到取出数组的最后一个元素还没有发现和X相等相等的数，则说明数组中不存在数的数，则说明数组中不存在数X。这种在全部查找范围内。这种在全部查找范围内逐一比较的查找方法称为顺序查找算法。逐一比较的查找方法称为顺序查找算法。7.2.1 7.2.1 顺序查找算法顺序查找算法 顺序查找算法的思路：顺序查找算法的思路： （1）将被查找的）将被查找的N个数存放到数组个数存放到数组A中，将待查找的数存中，将待查找的数存放到变量放到变量X中。中。 （2）从数组的第）从数组的第1个元素开始，逐个与变量个元素开始，逐个与变量X进行比较，进行比较，对于某个数组元素对于某个数组元素A(i)，若，若A(i)=X，表示查找成功，输出，表示查找成功，输出该元素的下标该元素的下标i，并停止比较；若，并停止比较；若A(i)X，则数组的下一，则数组的下一个元素个元素A(i+1)继续与继续与X进行比较进行比较 （3）若找遍了所有元素，没有一个元素）若找遍了所有元素，没有一个元素A(i)=X，表示在，表示在该组数中没找到数该组数中没找到数X，输出，输出“查找不成功查找不成功”的信息。的信息。7.2.1 7.2.1 顺序查找算法顺序查找算法实现该算法的部分关键程序段如下：X=Val(TextBox1.Text)从TextBox1控件读入要查找的数XFori=1ToNIfA(i)=xThen若某数组元素值和X值相同，退出循环ExitForEndIfNextIfi=NThen依据退出循环时的查找位置判断查找结果MsgBox(找到了数值&Str(X)ElseMsgBox(没找到数值&Str(X)EndIf7.2.1 7.2.1 顺序查找算法顺序查找算法顺序查找算法流程图7.2.1 7.2.1 顺序查找算法顺序查找算法【例7-1】设计程序，完整实现顺序查找算法。7.2.2 7.2.2 二分查找算法二分查找算法每次猜中间值，然后根据“猜高了”或“猜低了”的提示再调整范围，重新猜中间值，这就是二分查找算法的思想。二分查找算法的思路描述如下：（1）假设已在数组A(N)中存放了从小到大排列的N个数，而待查找的数字存放于变量X中；（2）初次查找区间为1，N，令L=1，H=N（L和H分别为待查找区间的下界和上界），则区间中点M=(L+H)/2。（3）若查找区间L，H存在，即LX，说明X可能存在于前半区间，则修改区间上界，令H=M-1，即当前实际查找区间变更为1，M-1；若A(M)A(j)Then若第j+1个数比第i+1个数小，则交换它们的位置t=A(i)交换A(i)和A(j)A(i)=A(j)A(j)=tEndIfNextNext选择排序算法选择排序算法实现改进后的算法的关键程序段如下：Fori=0ToN-1外层循环控制查找第i+1个最小数并放置它到A(i)位置P=i一趟比较前，假定第i+1个数是最小数，并记下其位置Forj=i+1ToN内层循环控制第i+1个最小数的查找过程IfA(P)A(j)Then若第j+1个数比第i+1个数小则记下新的位置号P=jEndIfNextIfPiThen一趟比较完成后，判定比较前的假定是否正确若Pi，即最小数不是第i个数，则执行交换操作t=A(i)A(i)=A(P)A(P)=tEndIfNext选择排序算法选择排序算法【例7-3】编写程序，实现选择排序算法。分析：程序界面设计如图7-7所示，“生成原始数组”按钮用于生成原始随机数组a，并在Label2中显示输出，其代码同例7-1，这里不再赘述。选择排序算法使用通用过程xz_sort实现，“选择法排序”按钮实现调用通用过程，并将排序后的数组在Label4中输出。冒泡排序算法冒泡排序算法冒泡排序就是依次比较相邻两个元素，将小数放在前面，大数放在后面。过程描述如下：（1）将数列中的第1个元素与第2个元素进行比较，将小数放前，大数放后，然后比较第2个元素和第3个元素，依然是小数放前，大数放后如此继续，直到比较最后两个数。这样经过第一趟排序之后，此时数列中最大的数将被排在最后的位置（即所谓的沉底）。（2）第1趟比较后，最大的数就被确定在了最后的位置，然后进行第二趟排序。依然是从头开始，比较第1个元素和第2个元素，将小数放前，大数放后如此继续，直到比较到最后一个数的前边两个相邻的数，第二趟排序结束，此时在倒数第二个元素的位置上得到了数列中第二大的数。如此下去，直到最终完成排序。从小到大排序时，最大的数一趟比较就将被交换到A(N)的位置；从大到小排序时，最小的数一趟比较就将被交换到A(N)的位置。若将排序趟数记录为J，则第J趟比较的范围为1NJ。（3）若J=N1，则已进行N1趟比较，排序完成。冒泡排序算法冒泡排序算法冒泡排序算法的通用过程如下所示：Subbubbling_sort()冒泡排序算法Dimi,J,tAsIntegerForJ=1ToN-1Fori=1ToN-JIfa(i)a(i+1)Thent=a(i)a(i)=a(i+1)a(i+1)=tEndIfNextNextEndSub冒泡排序算法冒泡排序算法冒泡排序算法流程图冒泡排序算法冒泡排序算法改进后的冒泡排序算法如下：改进后的冒泡排序算法如下：Subbubbling1_sort()改进的冒泡排序算法Dimi,J,t,PAsIntegerP=1交换标志，初始为1，保证进入循环J=1While(P=1)And(Ja(i+1)Thent=a(i)a(i)=a(i+1)a(i+1)=tP=1有交换发生时，置标志P为1EndIfNextEndWhileEndSub插入排序算法插入排序算法若数组A中T个数据已为有序存放，实现存入第T+1个数后数组中的数据仍符合原排列次序要求的算法，称为插入算法。仍以从小到大排序为例，插入算法可描述如下：（1）读入数X。（2）若X值不是结束标志（因要实现连续插入多个数据并排序成功，所以必须约定一个结束标志，例如当X输入为888888时，表示输入完毕），且T值小于数组下标取值的上界M，则继续执行步骤(3)，否则转步骤(6)。（3）将X和已有的数逐个进行比较，查找应插入存放数X的位置K。（4）将位置K腾空出来，即把从位置K到位置T间所存放的数据依次后移一位。（5）将X放到位置K，记录数组中有效数据个数的计数变量T增值1。（6）为观察插入运算结果，还需要输出插入X后的数组内容。插入排序算法插入排序算法假定数组A和变量i、M、T等均已经定义，数组A和变量M、T已有赋值，插入一个数据X的关键程序段如下：X=InputBox(PleaseInputX:)If(X888888)And(TM)Then这里假设X取值888888为停止插入标志Fori=T-1To0Step-1从已有数据的尾部开始查找插入位置IfXA(i)ThenA(i+1)=A(i)边查找，边进行数据的移位操作ElseExitFor找到了插入位置，则结束循环EndIfNextiA(i+1)=X将X存入找到的插入位置i+1上T=T+1数组有效数据个数计数器T+1EndIf插入排序算法插入排序算法【例7-4】输入若干个数据，要求实现边输入边排序（数据输入以888888作为结束标志）。本章小结 本章从本章从算法的概念算法的概念开始，开始，着重着重介绍介绍了一维数组选择排序和冒泡了一维数组选择排序和冒泡排序算法及排序算法及应用，最后应用，最后简单简单讲述讲述了插入排序算法的应用了插入排序算法的应用。 通过对本章的学习，从整体上加深对通过对本章的学习，从整体上加深对算法算法的认识，培养学生的认识，培养学生利利用算法解决实际问题的用算法解决实际问题的能力，加强学生能力，加强学生对排序算法设计思想的对排序算法设计思想的理解。理解。
