对分查找算法及程序实现

对分查找算法及程序实现一、设计思想对分查找是计算机科学中的一个基础算法。

对于一个基础算法的学习，同样可以让学生在一定的情境下，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程。

本堂课以一个游戏暖场，同时激活学生的思维，引导学生去探索游戏或生活背后的科学原理。

为了让学生在教师的引导下能自我解析算法的形成过程，本课分解了问题动作，找出问题的全部可能情况，在对全部可能情况总结归纳的情况下，得出对分查找的基础算法，最后在程序中得到实现，从而使学生建立起对分查找算法形成的科学逻辑结构。

二、教材分析本课的课程标准内容：（一）计算机解决问题的基本过程（1）结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。

（三）算法与问题解决例举 C 查找、排序与问题解决（2）通过实例，掌握使用数据查找算法设计程序解决问题的方法。

本课的《学科教学指导意见》内容：基本要求：1.初步掌握对分查找算法。

2.初步掌握对分查找算法的程序实现。

教材内容：第二章算法实例2.4.3对分查找和第五章5.4查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个课时，第一课时着重是对分查找算法的形成和初步程序实现，第二课时利用对分查找算法解决一些实际问题的程序实现，本教学设计为第一课时。

从《课程标准》和《学科教学指导意见》对本课教学内容的要求来看，要求学生能从问题出发，通过相应的科学步骤形成对分查找的算法。

对学生来说，要求通过这一课时的学习能初步掌握或了解对分查找的前提条件、解决问题的对象，明确对分查找算法结构和对分查找的意义。

三、学情分析学生应该已经掌握程序设计的基本思想，掌握赋值语句、选择语句、循环语句的基本用法和VB基本操作，这节课学生可能会遇到的最大问题是：如何归纳总结对分查找解决不同情况问题的一般规律，鉴于此，在教学中要积极引导学生采取分解动作、比较迁移等学习策略。

《对分查找算法的程序实现》一、案例主题：浙江教育出版社《算法与程序设计》（选修），《对分查找算法的程序实现》二、背景材料：（一）教学内容分析：1.对分查找算法是《算法与程序设计》（选修）《5.4节查找算法的程序实现》中的内容，是结合流程图实现程序的课型。

本课内容是选修教材中对所学语句结构和代码理解的一个总结性应用，具有很强的实用性。

2.本课内容应用性较强，具有一定的难度，体现在对流程图理解和代码实现的过程中，但应用丰富，拓展性强，有很高的研究价值。

（二）学生分析：通过前面一个月算法的学习，学生已经逐步熟悉visual basic6.0的编程环境，掌握了顺序结构、分支结构、循环语句的用法，在前期教学中学生已经初步了解算法基础及算法表示，抽象思维相对较好。

对分查找的算法对学生来说比较抽象，学生能否清晰的想象比较关键，所以学习难度比较大，需要教师合理的引导帮助其来解决问题。

本课中学生可能会出现的情况：1.掌握三种基本结构，但是在综合思想算法上缺乏一定的掌握度。

解决策略：先介绍对分查找思想，然后再引入流程图和程序。

2.刚学过顺序查找，给他们的感觉是实现简单，容易思想上放松。

解决策略：要让学生从根本上区别顺序查找，以免混淆算法。

3.因为对分查找比较抽象，如果直接以代码的形式出现，学生会难以理解和接受。

解决策略：以生动形象的例子进行导入然后再进行教学，提高课堂效率。

三、教学设计：（一）教学设计思想：对分查找在整个选修教材中是一个重点和难点，本课以生动的实例做为课堂导入，强调教学重点，以动态的指针演示，让算法思路更具体化，并且逐个击破难点并得以程序实现，以半成品加工策略提高课堂效率。

本课主要通过“思维导图”的形式和任务驱动等教学方式引导学生自主探究探索、解决问题，通过小组同学的探讨实现对本课知识的掌握，教师通过合理的引导帮助学生理解，创设学生自主和互助学习的良好气氛，以达到理解对分查找算法和实现相应程序的目标。

查找算法——顺序、对分查找在到学习、工作和生活中我们经常需要在一系列数据中查找出是否有某个特定数据，如在图书馆按书目查找某本书，在运动会上查寻某运动员的比赛成绩，在网上搜索信息、使用QQ查找好友等，这时就会用到查找算法了。

•问题提出一、采用何种方法进行查找？1.顺序查找顺序查找是最容易想到，也是最容易实现的一种查找算法，方法是将要找的数据与数组中的每个数据从第一个开始逐一进行比较，直到找到或者全部找完。

（1）顺序查找算法流程图（3）编写程序代码。

Dim d(1 To 8) As Integer ‘有8个数据Private Sub Command6_Click() '顺序查找Dim i As Integer, key As Integerkey = Val( _______ ) '获取查找的数据For i = 1 To _______ '依次查找If __________ Then '找到了数据Label5.Caption = "在数组的第" + Str(i) + "个位置"Exit For ‘中断当前For循环End IfNextIf i =_______ ThenLabel5.Caption = "在数组中没有找到数据" + Str(key)End Sub如果数组中有n个元素，那么顺序查找的平均查找次数是（n+1）/2次，有没有效率更高的查找算法呢？对分查找2.对分查找算法：首先将查找键与有序数组内处于中间位置的元素进行比较，如果中间位置上的元素内的数值与查找键不同，根据数组元素的有序性，就可确定应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。

对分查找的前提条件数组中的数据是已经排序的。

对分查找算法流程图（3）编写程序代码。

Private Sub Command4_Click() '对分查找Dim i As Integer, j As Integer, key As Integer, m As Integer Dim nc,flag As Integerflag=0 ‘flag 用于标志是否找到 key = Val(Text2.Text) '输入查找的数据 i = 1 j = 18nc = 0 '查找次数nc Do While i <= j '对分查找 nc =—————— '查找次数增加1m = __________ ‘求中间下标，若有小数,只保留整数 If __________Then ‘找到了 Label6.Caption = "在数组的第" + Str(m) + "个位置，共查找了" + Str(___) + "次"flag=_____Exit do ‘强制退出循环’End IfIf key < d(m) Then '未找到，继续查找 j=__________ Elsei = __________ End IfLoopIf flag==____ thenLabel6.Caption = "在数组中没有找到数据" + Str(key) + "，共查找了" + Str(nc) + "次"EndifEnd Sub使用对分查找，每次都把规模缩小一半，效率比顺序查找要高，但在进行对分查找前，需要将它排好序。

第2轮复习对分查找算法顺序查找次数在1和n之间对分查找成功，最少查找1；对分查找无论是否找的到，最多查找[log2n]+1对分查找不成功，则最少查找[log2n]次比如 1 2 3 4 5 key=0.5(1) i=1 j=5 循环比较（i<=j）m=3 if比较（key<d(3)）i=1 j=2(2) i=1 j=2 循环比较（i<=j）m=1 if比较（key<d(1)）i=1 j=0(3) i=1 j=0 循环比较（i<=j）不成立，直接退出所以总共查找了2次，即[log2n]次1 2 3 4 5 6 7对分查找次数 3 2 3 1 3 2 31 2 3 4 5 6 7 8对分查找次数 3 2 3 1 3 2 3 4 平均查找次数=19/81 2 3 4 5 6 7 8 9对分查找次数 3 2 3 4 1 3 2 3 4 平均查找次数=25/9'对分查找原数组递减（1）i = 1: j = 6: nc = 0Do While i <= jnc = nc + 1·m = Int((i + j) / 2)If a(m) = Key ThenExit DoEnd IfIf Key>a(m) Thenj = m - 1Elsei = m + 1End If等价于Find=falsei = 1: j = 6: nc = 0Do While i <= j and not findnc = nc + 1m = Int((i + j) / 2)If a(m) = Key ThenFind=trueEnd IfIf Key>a(m) Thenj = m - 1Elsei = m + 1End IfIf find=true then print原数组递减以下代码能找到If Key>a(m) Thenj = m – 1Elsei = m + 1End If相关参考题目名卷精编2018A版 P11-18 P13-11 P31-11 P17-11P加试题训练4-11 此题没有简便方法P加试题训练10-12 此题没有简便方法变式题目1：Private Sub Command1_Click()Dim a(1 To 10) As Integera(1) = 8: a(2) = 15: a(3) = 26: a(4) = 30: a(5) = 37: a(6) = 50: a(7) = 55: a(8) = 68: a(9) = 83: a(10) = 106i = 1: j = 10Key = 15Text1.Text = ""Do While i < jm = (i + j + 1) \ 2 '注意取中值范围If Key = a(m) Then Exit DoIf Key < a(m) Then j = m - 1 Else i = m + 1Text1.Text = Str(a(m)) + Text1.Text '注意输出顺序答案 26 50LoopEnd Sub'i=1 j=10 m=6 a(m)=50'i=1 j=5 m=3 a(m)=26'i=1 j=2 m=2 a(2)=key 这一步很关键变式题目2：对分查找的递归函数表示方法Dim a(1 To 100) As IntegerDim k As IntegerFunction search(key As Integer, left As Integer, right As Integer) As Integer middle = (left + right) \ 2If left > right Thensearch = -1ElseIf a(middle) > key Thenk = k + 1: search = search(key, left, middle - 1)ElseIf a(middle) < key Thenk = k + 1: search = search(key, middle + 1, right)ElseIf a(middle) = key Thenk = k + 1: search = middle: Exit FunctionEnd IfEnd IfEnd FunctionPrivate Sub Command1_Click()k = 0a(1) = 2: a(2) = 4: a(3) = 6: a(4) = 8: a(5) = 10: a(6) = 13: a(7) = 15Print Str(search(6, 1, 7))'【6】表示查找数组元素值是6，【1】数组的开始下标为1，【7】数组的结束下标为7 'search函数的返回值是值为6的数组元素的下标Print k'值为6的数组元素查找次数End Sub。

对分查找算法及程序实现一、设计思想对分查找是计算机科学中的一个基础算法。

对于一个基础算法的学习，同样可以让学生在一定的情境下，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程。

本堂课以一个游戏暖场，同时激活学生的思维，引导学生去探索游戏或生活背后的科学原理。

为了让学生在教师的引导下能自我解析算法的形成过程，本课分解了问题动作，找出问题的全部可能情况，在对全部可能情况总结归纳的情况下，得出对分查找的基础算法，最后在程序中得到实现，从而使学生建立起对分查找算法形成的科学逻辑结构。

二、教材分析本课的课程标准内容：（一）计算机解决问题的基本过程（）结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。

（三）算法与问题解决例举查找、排序与问题解决（）通过实例，掌握使用数据查找算法设计程序解决问题的方法。

本课的《学科教学指导意见》内容：基本要求：.初步掌握对分查找算法。

.初步掌握对分查找算法的程序实现。

教材内容：第二章算法实例对分查找和第五章查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个课时，第一课时着重是对分查找算法的形成和初步程序实现，第二课时利用对分查找算法解决一些实际问题的程序实现，本教学设计为第一课时。

从《课程标准》和《学科教学指导意见》对本课教学内容的要求来看，要求学生能从问题出发，通过相应的科学步骤形成对分查找的算法。

对学生来说，要求通过这一课时的学习能初步掌握或了解对分查找的前提条件、解决问题的对象，明确对分查找算法结构和对分查找的意义。

三、学情分析学生应该已经掌握程序设计的基本思想，掌握赋值语句、选择语句、循环语句的基本用法和基本操作，这节课学生可能会遇到的最大问题是：如何归纳总结对分查找解决不同情况问题的一般规律，鉴于此，在教学中要积极引导学生采取分解动作、比较迁移等学习策略。

四、教学目标知识与技能：理解对分查找的概念和特点，通过分步解析获取对分查找的解题结构，初步掌握对分查找算法的程序实现。

二分查找算法1. 算法简介二分查找算法，也称为折半查找算法，是一种在有序数组中查找特定元素的高效算法。

它通过将数组分成两部分，并重复比较目标值与数组中间元素的大小关系，从而缩小搜索范围，最终定位到目标元素的位置。

2. 算法原理二分查找算法的基本思想是不断将待搜索区间缩小一半，直到确定目标值的位置或者确定不存在目标值为止。

具体步骤如下：1.初始化待搜索区间的左边界left和右边界right，初始时left = 0，right = n-1。

2.计算待搜索区间的中间位置mid = (left + right) / 2。

3.比较目标值与中间元素的大小关系：–如果目标值等于中间元素，则返回中间元素的索引。

–如果目标值小于中间元素，则更新右边界为mid - 1，继续在左半部分进行查找。

–如果目标值大于中间元素，则更新左边界为mid + 1，继续在右半部分进行查找。

4.重复步骤2和步骤3，直到找到目标元素或者确定不存在目标元素。

3. 算法实现以下是二分查找算法的Python实现：def binary_search(nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midelif nums[mid] < target:left = mid + 1else:right = mid - 1return -14. 算法分析时间复杂度二分查找算法的时间复杂度为 O(logn)，其中 n 是数组的长度。

每次比较都将搜索范围缩小一半，因此最多需要进行 logn 次比较。

空间复杂度二分查找算法的空间复杂度为 O(1)，因为只需要使用常数级别的额外空间。

算法特点•只适用于有序数组：由于二分查找算法依赖有序性，所以只能应用于有序数组。

对分查找算法程序实现【学科核心素养】能理解对分查找的原理，利用VB6.0程序设计软件编写简单的对分查找程序，实现在递增整数序列中查找指定整数，剖析对分查找算法的易错点。

（计算思维）。

了解对分查找在学习和生活中的应用。

（数字化学习与创新）。

【课程标准要求】根据“课程标准”中提出的要求：通过实例，掌握使用数据查找算法设计程序解决问题的方法。

【学业要求】理解对分查找算法的思维，编写简单对分查找程序。

【教学内容分析】本课将教材第二章第4节的“查找”和第五章第4节的“查找算法的程序实现”两节合并起来学习，通过理论与实践结合，以加深学生对对分查找算法和程序设计的关系的体会。

对分查找要在数据已经排序的基础上进行，因此这节的学习即是对前面学习的排序算法的应用，也为进一步学习数据查询技术打下基础。

【学生主体分析】通过算法与程序设计基础及枚举、解析、排序等算法的学习，学生已经掌握了基础算法和基础数据结构等知识，具备对数据的分析、处理的基本能力。

但将这些算法利用VB程序实现是学习的疑难点。

考虑到湖州中学选考11班学生具备良好的理工科基础，本节课要求学生直接编写简单的VB二分查找程序，不提供填空、文字提示的形式。

【教学目标】1、了解对分查找的概念，初步掌握对分查找算法。

2、熟悉VB的程序设计步骤和方法，提高将算法转换成程序的能力。

3、培养学生对程序设计的兴趣，对分查找算法的规律，认识对分查找的易错点，并能将所学知识应用于现实生活中。

【教学重、难点】对分查找算法的VB程序实现【教学准备】网络机房；VB6.0，office办公软件；【教学策略分析】教法：问题导学（以问题引领学生探究）、任务驱动。

学法：以小组合作探究为主。

分成4人一组，在学习过程中形成合力，组内交流、组间竞争。

【教学过程】环节过程与内容学生活动设计意图引入：5分钟回顾二分查找算法：展示在9个升序整数列中利用二分查找算法查找某个key的过程（PPT，或者手写，随便）1.观察与思考。

VB查找专题班级姓名知识点回顾：1、查找概念及意义：到一组有序或无序的数（如果数据是有规律的就可以不用数组）中找符合条件的数据。

意义：生活中查找应用广泛，所以研究查找算法很有必要。

2、顺序查找算法：从第一个元素开始，按顺序依次将数据与需查找的给定值比较，若某次发现数据相等，则退出查找，提示查找成功、数据所处位置或值等信息。

如所有数据查完，没找到，则查找不成功。

3、关于顺序查找需理解：※字符串也能查找与被查找，字符串相等的判断标准是从前往后每一个字符都相等※被查找的一组数据可以是无序的，当然有序也可以。

※实现要点是循环加选择，一般是for 加if语句，注意与枚举算法的区别。

※到N个数据中用顺序查找找一个数，最少查找次数1，最多查找次数n，平均查找次数（n+1)/25、对分查找算法：又名二分查找，高效，但前提是背查找的数据必须是有序的。

在有序的一组数据中，先将处于中间位置的数据与查找数据比较，若相等则提示成功；否则根据数组的有序性（升序或降序）判断要查找的数据在前半部分还是后半部分，然后缩小范围按以上方法继续查找，直到找到或找一遍发现数据不存在。

6、关于对分查找需理解：※到N个数据中用经典对分查找某数，最少查找次数1，最多查找次数int（log2n)+1，平均查找次数为：※被查找的一组数据必须是有序的，查找过程中注意其升序还是降序。

※查找次数不定，一般用do while 语句实现循环，请部分同学尝试将语句改为用for语句实现。

7、对分查找经典算法：（被查找数据以升序为例）巩固练习1、在数组22、54、7、61、33、9、15中查找数字9，采用从后往前顺序查找，需要查找（）A.2次B.6次C.1次D.7次2、数组 a(1 to 6)中保存的字符串依次为oil，car,boe,all,web,log，在数组中查找”boy”，执行知识点回顾4中顺序查找经典算法结果是（）A.没有找到B.在数组第1位置上找到数据boyC.在数组第3位置上找到数据boyD.在数组第6位置上找到数据boy3、小海同学用VB设计了一个模拟高考查分系统的软件。

对分查找算法及程序实现一、二分查找算法二分查找又称折半查找，是一种在有序数组中查找其中一特定元素的算法。

它的基本思想是：将数组的中间位置的数与要查找的数据比较，如果查找数据比中间位置的数小，则在数组的低半部分继续进行查找；如果查找数据比中间位置的数大，则在数组的高半部分继续查找；直到找到该数据或者查找范围为空为止。

二分查找的时间复杂度为O(log n)，由于其基本思想是二分法，所以称之为二分查找。

二、二分查找算法的实现1、二分查找的实现//二分查找// arr：被查找的有序数组// item：要查找的项int binary_search(int arr[], int size, int item)int low = 0;int high = size;int middle;while(low <= high)middle = (low + high)/2;return middle;else if (arr[middle] < item)low = middle + 1;elsehigh = middle - 1;}return -1; // 表示没有找到2、二分查找的递归实现//二分查找的递归实现// arr：被查找的有序数组// item：要查找的项// low ：数组的低位下标// high：数组的高位下标int binary_search_recursive(int arr[], int item, int low, int high)if (low > high)return -1; // 表示没有找到int middle = (low + high) / 2;return middle;else if (arr[middle] < item)return binary_search_recursive(arr, item, middle + 1, high);elsereturn binary_search_recursive(arr, item, low, middle - 1);三、二分查找算法程序实现#include <iostream>using namespace std;//二分查找// arr：被查找的有序数组// item：要查找的项int binary_search(int arr[], int size, int item)int low = 0;int high = size;。

一、顺序查找算法回顾1、顺序查找思路：1) 将被查的数存放到数组中（比如数组d ），待查的数据存放在某变量中（比如变量key ）2) 从数组第1个元素开始，逐个与要查找的数比较2、顺序查找过程 1）将被查的10个数存放到数组d ，将待查的数据存放到变量key 2）从数组第1个元素开始，逐个与变量key 比较，对于某个数组元素若d(i)=key，表示查找成功，输出该数组元素的下标 i ，并停止比较 若d(i)<>key ，则数组的下一个元素d(i+1)继续与key 比较...... 3）若找遍了所有元素，没有一个元素d(i)=key ，表示3、顺序查找方法归纳：笨拙4、上次课堂结尾的几个话题话题1：如何查英文词典（不可能采用顺序查找的！）话题2：如何在最短时间猜中1000元以内商品的价格？（每次猜中间价格！）话题3：如何在10个有序的数“98、88、82、78、70、67、65、56、49、28”中查找 49 这个数 如何在10个有序的数“28、49、56、65、67、70、78、82、88、98”中查找 99 这个数 有序数据采用“对分查找”方法（取中间的数进行比较）核心要点：区间（i,j)的中间数编号m=Int((i+j)/2)二、对分查找：前提是被查找的数据必须是有序的（递增/递减）1、对分查找的基本思想：每次将查找内容与有序数组内中间的那个数进行比较！第二章：算法实例—对分查找算法1(13)算法与程序设计1) 将被查找的数存放到数组中(必须有序！)，待查数据存放在某变量中（比如变量key）2) 区间（i,j）的起始为（1，n)，即初始值：i=1，j=n，(注意i<=j)3）每次将查找内容与有序数组内中间那个数比较。

区间（i,j)的中间数编号m=Int((i+j)/2)如果二者相等，则查找成功若二者不同，则根据数组的有序性可以确定在数组的前半部分还是后半部分继续进行查找。

4）直到找到，或者无法组成新的查找区间（即找不到）为止！2、对分查找过程示例1：在递增的数组d中寻找key=35这个数第3次末数3、对分查找过程示例2：在递减的数组d中寻找key=66这个数第3次第1次第2次第1次第2次第3次末数三、对分查找算法的程序实现！1、算法要点（从前面的练习中去感觉！）1、初值i=1,j=n2、循环条件：i<=j3、根据i,j计算m=Int((i+j)/2) 或者 m=Fix((i+j)/2)4、比较key与d(m)若key=d(m)查找成功，输出m若key<d(m)，则在上半区继续查找（增序为例），只要修改j=m-1即可若key>d(m)，则在下半区继续查找（增序为例），只要修改i=m+1即可思考：对分查找该用什么类型的循环呢？2、对分查找的程序理解!假设有10个数据已经按照升序存放在数组 D中，要查找的数据通过文本框Text1输入Dim d( 1 to 10) As Integerkey=Val(Text1.Text)i=1 : j=10 '查找区间初始化xb=0 '记忆查找成功时的下标nc=0 '统计查找次数Do While i<=j '为何不用For循环？nc=nc+1 'nc记录查找次数m=Fix((i+j)/2) '计算出中间位置，或m=Int((i+j)/2)If d(m)=key Then '查找成功立即终止循环xb=m'查找成功时变量xb记忆住数组下标Exit DoEnd IfIf key<d(m) Then'准备在上半区继续查找j=m-1Else'准备在下半区继续查找i=m+1End IfLoopIf xb<>0 Then '查找成功，输出下标xbPrint xbElse '查找不成功Print "没有找到"End If3、对分查找的程序流程图（略）四、对分查找算法巩固练习1、启动D：\下的“课堂练习.exe”，完成第27套课堂练习2、做完后将"批改27.批改"上传到班级FTP自己的文件夹内（ftp://10.7.3.100）中（比如变量key）不到的结论。

浙教版《算法与程序设计经典算法对分查找及VB实现知识点及课后练习对分查找是一种高效的搜索算法，常用于在有序数组中查找某一特定元素。

在浙教版《算法与程序设计》中，对分查找是一个重要的知识点。

下面将对分查找及VB实现的知识点及课后练习进行介绍。

知识点介绍：1、对分查找的基本思想：将有序数组分成两半，每次取中间值与目标值进行比较，根据比较结果确定继续在左半边还是右半边查找，直到找到目标值或查找范围为空。

2、对分查找的算法流程：（1）将数组按升序排列；（2）初始化两个指针，left指向数组的第一个元素，right指向数组的最后一个元素；（3）当left <= right时，执行以下步骤：a.计算中间位置mid=（left+right）/2；b.如果mid元素等于目标值，则返回mid；c.如果mid元素大于目标值，则在左半边继续查找；d.如果mid元素小于目标值，则在右半边继续查找。

3、VB实现：使用VB编写对分查找的代码，需要注意数组的索引是从0开始的，因此在计算中间位置时需要使用（left+right）/2，而不需要加1。

课后练习：1、对于以下数组：{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}，使用对分查找查找元素13，输出查找过程。

2、对于以下数组：{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}，使用对分查找查找元素2，输出查找过程。

3、对于以下数组：{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}，使用对分查找查找元素-1，输出查找过程。

4、对于以下数组：{100, 200, 300, 400, 500}，使用对分查找查找元素300，输出查找过程。

在计算机科学中，冒泡排序是一种简单的排序算法。

这种算法通过重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。