第14节 排序与查找.pptVIP

考试要求 本节不要求大家能够编写程序，但是需要大家理解排序算法和查找算法的思想。 往年，在考试的时候是以填空题的形式出现的，每个题目大概占5分到10分。 查找算法 常用算法是二分查找法。二分查找法是一种高效的查找方法，它可以明显减少比较次数，提高查找效率。 注意：二分查找法的先决条件时数据必须有序排序。 它的基本思想是将有序数列的中点设置为比较对象，如果要查找的数小于该中点，则将待查序列缩小为左半部分，否则为右半部分。即通过一次比较，将查找区间缩小一半。 二分查找法的基本思想 第1步：循环当low≤high ①计算整个查找区间的中间位置：mid=(left+right)/2 ②用待查关键字值与中间位置的关键字值进行比较， 若相等，则查找成功，跳出循环； 若大于，则在后半区域继续进行二分查找，low=mid+1; 若小于，则在前半区域继续进行二分查找，high=mid-1; 第二步，如果lowhigh,查找不成功；否则查找的数放在mid位置。 例题 在一个含10个数的有序数列A{3,16,20,27,35,39,46,48,55,73}中查找20及71。 第14节 排序和查找法 引言 日常生活中，你会经常同各种各样的数据打交道，无论是年龄、学号、还是价格、书目，都是数据。自从有了计算机后，这些数据便可以使用计算机来存储和处理，其中不乏对数据进行排序（sort）和查找(search)。 冒泡排序 冒泡法的思想是： 1、假设有从左到右排列的n个数，将其从上到下排列。 2、先从上到下依次比较相邻的相邻的两个数，使小的在上，大的在下，那么第一趟比较n-1次后，把最大数排到了最下边。 3、第二趟排序在前面n-1个数中进行，比较n-2次后把次大的数排到了倒数第二位， 4、依次类推，直到第n-1趟排序将次小的数排在了第二位，剩下一个数不用比较，排序结束。 算法的整体思路是逐次让大的数往下沉，让小的数像气泡一样不断向上冒，所以该算法被形象地称为“冒泡法”。 例如，下面是对5个数9，5，3，8，1进行排序的过程： 第一趟排序 过程如下，一共进行了4次比较，每次较大的数向下移动，第一趟排序结束后最大数9移动到最下面的位置。 第1次 第2次 第3次 第4次 结果 9 5 5 5 5 5 9 3 3 3 3 3 9 8 8 8 8 8 9 1 1 1 1 1 9 活动一 分析比赛成绩排序算法并编写程序 9的位置确定后，接下来对5，3，8，1再进行排序，各趟排序的结果如下： 第1趟排序确定9的位置，第2趟确定8的位置，第3趟确定5的位置，第4趟确定3的位置，还剩下一个数不需要排序，排序结束。 第1趟 第2趟 第3趟 第4趟 5 3 3 1 3 5 1 3 8 1 5 5 1 8 8 8 9 9 9 9 思考 如果用冒泡法对10个数排序，要进行几趟排序？ （16，9，4，25,1），要按递增顺序排序，采用冒泡排序法，第二趟冒泡后的结果是什么 ？请把整个冒泡排序的结果写出来。