青少年Python编程系列36排序算法和查找算法入门

　　上一节课我们已经讲了算法的基础知识，这节课我们讲一下算法中两个最为经典的类型：排序算法和查找算法。排序和查找我们之前直接使用列表的内置方法，那实现排序和查找最底层的原理是什么呢？我们正式开始这节课的内容吧。一、排序算法1。1冒泡排序
　　冒泡排序是最简单的一种排序方法，它的原理是将一列数据中较大（或较小）的数据逐次向右推移的一种排序方法。冒泡排序分为内外两层循环。外层是总共要跑的遍数，2个数据比较一遍，3个数据比较一遍，以此类推，n个数据就跑了n1遍。内层循环真正比较数据。以升序为例，每次比较把较大的放到后面。由于每一遍都是将本遍最大的数据移动到最右边。就像是水中的气泡一样，小的气泡上升，就排到最上面，就像是冒泡一样，所以我们称它为冒泡排序。
　　下面我们以升序为例，讲一下冒泡排序的基本思想：
　　第一遍从第1个元素开始，让它和第2个元素进行比较，如果大数在前就交换；然后让2个元素和第3个元素比较，大数在前就交换；依次类推，直到比较完最后一个元素为止。第一遍排序结束时，最后一个元素是所有元素中的最大值。
　　第二遍从第一个元素开始，让它和第2个元素进行比较，如果大数在前就交换；然后让2个元素和第3个元素比较，大数在前就交换；依次类推，直到比较到倒数第二个元素为止。第二遍排序结束时，倒数第二个数为第二大的数。
　　n个数排序共需要n1遍。
　　我们看一下模拟的实例：
　　39216原始数据
　　39216将3和9比较，不交换位置
　　32916将9和2比较，交换位置
　　32196将1和9比较，交换位置
　　32169将9和6比较，交换位置。第一轮结束
　　23149将3和2比较，交换位置
　　21349将3和1比较，交换位置
　　21349将3和4比较，不交换位置。第二轮结束
　　下面我们看一下冒泡排序的Python代码实现：a〔3，9，2，1，6〕countlen（a）foriinrange（0，count1）：外层循环forjinrange（0，count1i）：内层循环ifa〔j〕a〔j1〕：a〔j〕，a〔j1〕a〔j1〕，a〔j〕两个数交换print（a）1。2选择排序
　　选择排序对冒泡排序的改进。选择排序是在参加排序的所有元素中找出数值最小或最大的元素，如果它不是左侧第一个元素，就让它和左侧第一个元素交换位置；然后在余下的元素中找出数值最小或最大的元素，如果它不是左侧第二个元素，就与左侧第二个元素交换位置；依次类推，直到所有元素构成有序的序列。
　　比起冒泡排序，选择排序更符合人们日常的排序习惯。它的比较次数与冒泡排序相通，但是交换的次数比冒泡排序要少，因此具有更高的效率。
　　下面我们以升序为例，讲一下选择排序的基本思想：
　　第一遍从第1个元素到第n个元素中找出一个最小的元素，如果它不是第1个元素，就让它和第1个元素交换位置。第一遍排序结束时，第1个元素为所有元素中的最小值。
　　第二遍从第2个元素到第n个元素中找出一个最小的元素，如果它不是第2个元素，就让它和第2个元素交换位置。第二遍排序结束时，第2个元素为所有元素中第二小的值。
　　下面我们看看如何实现最小元素的交换位置：
　　第i遍排序开始时，先假设第i个位置上的数是最小的数，用k标记。让k位置上的数（a〔k〕）与i后面的数（a〔j〕）逐个比较，当找到一个比k位置上小的数，用k记录j的值。当j到达最后一个数时，一遍比较结束，k指向最小的数，即k记录最小的数的位置。当ik时，交换a〔i〕与a〔k〕的值。
　　我们看一下选择排序的Python代码实现：a〔3，9，2，1，6〕countlen（a）foriinrange（0，count1）：kiforjinrange（i1，count）：ifa〔k〕a〔j〕：kjifk！i：a〔k〕，a〔i〕a〔i〕，a〔k〕print（a）1。3插入排序
　　插入排序是先将待排序的数列中的第1个元素看成一个有序的子数列，然后从第2个元素开始，将数据逐个插入这个有序的子数列中，以此类推到最后一个数据。整个排序的过程类似于玩扑克牌时一边抓牌一遍理牌的过程，每抓一张牌就把它插入到应有的位置上。
　　插入排序的整个过程如下图所示：
　　插入排序
　　第1次插入，将第2个元素与第1个元素比较。先将要插入到数a〔1〕放入一个空的变量key；将key与前面已经排好序的元素比较，如果key
　　第2次插入，前面两个元素已经排好序，将第3个元素放入一个空的变量key，将key与前面排好序的元素比较，再将它插入对应的位置中。
　　依次类推。
　　我们看一下插入排序的Python代码实现：a〔3，9，2，1，6〕countlen（a）foriinrange（1，count）：keya〔i〕ji1whilej0anda〔j〕key：a〔j1〕a〔j〕j1a〔j1〕keyprint（a）1。4其他排序算法
　　以上三种排序的算法外，还有归并排序、快速排序、堆排序、计数排序、桶排序、希尔排序等等，快速排序的思想下节课我们会讲解，归并排序这里就略去不讲了，大家可以自己研究。别的排序算法相对较为复杂，目前阶段不需要大家掌握。有兴趣的同学可查阅相关资料。
　　相对好理解一些的是归并排序（暂时不需要掌握代码），大家可以看动画的图片做相应的理解：
　　归并排序二、查找算法2。1顺序查找
　　顺序查找是一种最为常用的查找算法。我们生活中也经常会用到，比如我们要从一堆书里面找到我们想要的书，我们会从第一本开始一本一本地看，直到找到我们想要的那本书。
　　顺序查找的基本思想是从第一个元素开始，按顺序逐个将数据与给定的数据进行比较，如果某个数据与给定的数据相等，则查找成功，输出所查数据；反之则未找到。
　　顺序查找的代码使用Python实现也非常简单：data〔12，23，1，89，34，13，78，67，54〕key34要查找的元素x1要查找元素的索引countlen（data）foriinrange（0，count）：ifdata〔i〕key：xibreakifx1：1代表元素未找到print（元素不存在）else：print（x）2。2对分查找
　　对分查找又称二分查找，是一种高效的查找方法。对分查找的前提是被查找的序列是有序的。
　　我们思考一个问题，从1到100中随机一个数字，猜出这个数是多少。如果我们从1开始一个个往后猜，每次只能排除一个数字，最坏的情况我们可能要猜100次。但是如果第一次猜50，告诉你大了或者小了。下次再猜25，再下次猜12，以此类推，不管是哪个数字，最多7次之内就能猜出来了。这样比起顺序查找要省了很多的时间。这就是对分查找算法。
　　我们看看对分查找的思路：
　　如果key是我们需要查找的值，列表a中存放了n个已经升序排列的元素，m为查找范围〔i，j〕的中间位置。我们查找的过程中必然是以下三种情况之一：如果keya〔m〕，key在前半部分，新的查找范围在〔i，m1〕中如果keya〔m〕，找到需要对数据如果keya〔m〕，key在后半部分，新的查找范围在〔m1，j〕中
　　我们看一下对分查找的Python代码实现：data〔2，34，36，47，51，53，59，62，75，79，82〕key47需要查找的元素countlen（data）i，j0，count1x1whileij：m（ij）2ifkeydata〔m〕：xmbreakelifkeydata〔m〕：im1else：jm1ifx1：print（未找到元素）else：print（x）三、课后思考题
　　1、选择题
　　列表l〔9，2，8，6，3，4〕，采用选择排序进行升序排序，第二遍排序之后的结果是（）
　　A。〔2，3，8，6，9，4〕
　　B。〔2，8，6，3，4，9〕
　　C。〔2，6，3，4，8，9〕
　　D。〔2，3，4，6，8，9〕
　　2、选择题
　　列表l〔5，2，6，3，7〕，利用插入排序进行升序排序，第二次插入排序的结果是（）
　　A。〔5，2，3，6，7〕
　　B。〔2，5，3，6，7〕
　　C。〔2，5，6，3，7〕
　　D。〔2，3，5，6，7〕
　　3、选择题
　　某个列表中有7个元素，依次为19、28、30、35、39、42、48。如果采用对分查找法在列表中查找元素48，需要查找的次数是（）
　　A。1B。2C。3D。4四、上节课思考题答案
　　1、C
　　2、C
　　3、参考代码n0统计个数foriinrange（100，1000）：ai100百位数bi10010十位数ci10个位数ifa3b3c3i：n1print（i）print（合计个数：，n）