05_6排序和查找ppt课件.pptx

在此输入您的封面副标题05_6排序和查找排序和查找杭州师范大学杭州师范大学 虞歌虞歌 第第2页页Python程序设计基础程序设计基础字符串、列表和元组字符串、列表和元组杭州师范大学杭州师范大学 虞歌虞歌 第第3页页Python程序设计基础程序设计基础字符串、列表和元组字符串、列表和元组排序排序就是给列表中的元素按值从小到大（升序）或从大到小（降序）的顺序就是给列表中的元素按值从小到大（升序）或从大到小（降序）的顺序重新存放的过程重新存放的过程。虽然提供虽然提供了了sort方法和方法和sorted函数，但了解和掌握函数，但了解和掌握排序算法的实现排序算法的实现过程还是过程还是颇有益处颇有益处的。的。杭州师范大学杭州师范大学 虞歌虞歌 第第4页页Python程序设计基础程序设计基础字符串、列表和元组字符串、列表和元组冒泡排序冒泡排序（Bubble Sort）。假设被排序的列表垂直竖立，将列表中的每个元素看作有重量的气泡，根据轻气泡假设被排序的列表垂直竖立，将列表中的每个元素看作有重量的气泡，根据轻气泡（小数）不能在重气泡（大数）之下的原则，扫描列表，凡扫描到违反本原则的轻（小数）不能在重气泡（大数）之下的原则，扫描列表，凡扫描到违反本原则的轻气泡，就使其向上气泡，就使其向上“漂浮漂浮”，如此反复进行多趟扫描，直至最后任何两个气泡都是，如此反复进行多趟扫描，直至最后任何两个气泡都是轻者在上，重者在下为止。由于在排序过程中总是轻气泡往前放，重气泡往后放，轻者在上，重者在下为止。由于在排序过程中总是轻气泡往前放，重气泡往后放，相当于气泡往上升，所以称作冒泡排序。相当于气泡往上升，所以称作冒泡排序。 杭州师范大学杭州师范大学 虞歌虞歌 第第5页页Python程序设计基础程序设计基础字符串、列表和元组字符串、列表和元组下图显示下图显示了如何用冒泡排序算法对列表了如何用冒泡排序算法对列表lst进行升序排序的过程。图中，实线箭头表进行升序排序的过程。图中，实线箭头表示交换数据，虚线箭头表示没有交换数据。假设列表示交换数据，虚线箭头表示没有交换数据。假设列表lst中的值为中的值为7, 6, 8, 5。对含有对含有n个元素的列表进行冒泡排序，要作个元素的列表进行冒泡排序，要作n-1趟扫描。趟扫描。 杭州师范大学杭州师范大学 虞歌虞歌 第第6页页Python程序设计基础程序设计基础字符串、列表和元组字符串、列表和元组排序过程是用两重for循环完成的。对有len(lst)个元素的列表，进行len(lst)-1趟扫描（i从1到 len(lst)-1）；每趟扫描要进行len(lst)-i次比较（j从0到len(lst)-i-1）。每次比较，若lstjlstj+1，则交换lstj和lstj+1。标志exchange的作用：若某趟扫描未发生交换，说明列表实际上已排好序了，排序过程应该在此趟扫描后终止。杭州师范大学杭州师范大学 虞歌虞歌 第第7页页Python程序设计基础程序设计基础字符串、列表和元组字符串、列表和元组查找查找就是在列表中寻找一个指定元素的过程就是在列表中寻找一个指定元素的过程。虽然提供虽然提供了了in运算符，但了解和掌握运算符，但了解和掌握查找算法的实现查找算法的实现过程还是颇有益处过程还是颇有益处的的。常用查找常用查找算法有：顺序查找（算法有：顺序查找（Linear Search）和二分查找（）和二分查找（Binary Search）。）。 杭州师范大学杭州师范大学 虞歌虞歌 第第8页页Python程序设计基础程序设计基础字符串、列表和元组字符串、列表和元组顺序顺序查找就是将要查找的元素（称为关键字）顺序与列表中的每个元素一一进查找就是将要查找的元素（称为关键字）顺序与列表中的每个元素一一进行比较，直至关键字与列表某个元素匹配；或者与所有列表元素都比较完毕，行比较，直至关键字与列表某个元素匹配；或者与所有列表元素都比较完毕，未找到与关键字匹配的列表元素未找到与关键字匹配的列表元素。顺序查找的优点是列表中元素排列顺序可以是任意的，缺点是查找时间随着列表中顺序查找的优点是列表中元素排列顺序可以是任意的，缺点是查找时间随着列表中元素数目的增长而线性增长，对于大列表查找效率不高。元素数目的增长而线性增长，对于大列表查找效率不高。杭州师范大学杭州师范大学 虞歌虞歌 第第9页页Python程序设计基础程序设计基础字符串、列表和元组字符串、列表和元组将关键字key与列表lst中的每个元素一一进行比较，如果找到匹配者，返回与关键字匹配的第一个列表元素的下标；如果未找到匹配者，返回-1。杭州师范大学杭州师范大学 虞歌虞歌 第第10页页Python程序设计基础程序设计基础字符串、列表和元组字符串、列表和元组二分查找，又称折半查找，对于大列表查找效率高，但列表中元素必须排序二分查找，又称折半查找，对于大列表查找效率高，但列表中元素必须排序存放。存放。假设列表中的元素按升序存放。将关键字与列表的中间元素进行比较，比较假设列表中的元素按升序存放。将关键字与列表的中间元素进行比较，比较结果有三种情况：结果有三种情况：如果如果关键字小于中间元素，则在列表的前半部分（小于中间元素的那一半中）关键字小于中间元素，则在列表的前半部分（小于中间元素的那一半中）进行查找，且从该部分列表的中间元素开始比较。进行查找，且从该部分列表的中间元素开始比较。如果如果关键字与中间元素相等，则查找结束，找到匹配的列表元素。关键字与中间元素相等，则查找结束，找到匹配的列表元素。如果如果关键字大于中间元素，则在列表的后半部分（大于中间元素的那一半中）关键字大于中间元素，则在列表的后半部分（大于中间元素的那一半中）进行查找，且从该部分列表的中间元素开始比较进行查找，且从该部分列表的中间元素开始比较。每经过一次查找，二分查找算法会将查找范围缩小一半每经过一次查找，二分查找算法会将查找范围缩小一半。杭州师范大学杭州师范大学 虞歌虞歌 第第11页页Python程序设计基础程序设计基础字符串、列表和元组字符串、列表和元组下图显示下图显示了如何用二分查找算法在列表了如何用二分查找算法在列表lst中查找关键字中查找关键字11的过程。用的过程。用low和和high分别表示当前要查找的列表的首下标和尾下标，分别表示当前要查找的列表的首下标和尾下标，low的初始值为的初始值为0，high的初始值的初始值为列表长度减为列表长度减1；用；用mid表示列表中间元素的下标，表示列表中间元素的下标，mid的值为的值为(low+high)/2。杭州师范大学杭州师范大学 虞歌虞歌 第第12页页Python程序设计基础程序设计基础字符串、列表和元组字符串、列表和元组将key与要查找的列表lst的首下标low（初始值为0）和尾下标high（初始值为len(lst)-1）之间的中间元素lstmid进行比较，mid的值为(low+high)/2。若keylstmid，low的值为mid+1，high的值不变；重复上述查找过程，直至lowhigh。若lowhigh，表明未找到匹配者，返回-1。