Python数据结构与算法学习第七天

一.归并排序

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
代码实现：

**代码执行流程：**当输入li = [54,26,93,17,77,31,44,55,20]进入函数后，先计算n=9，mid=4，则alist[:4]=[54,26,93,17]，alist[4:]=[31,44,55,20]第一次递归后，计算n=4，mid=2，所以alist[:2]=[54,26],在进行第二次递归，n=2，mid=1，alist[:1]=54,当进行第三地递归时，因为n=1，所以return alist，即left_li=54，而 right_li=merge_sort(alist[1:])，进行递归，因为n=1，所以return alist，即right_li=26，进入循环与判断，最后return result=[26,54]，即left_li=[26,54]。接下来进行 right_li=merge_sort(alist[2:])，即完成alist[2:]=[93,17]的排序。结束这个排序后 right_li=[17,93]。然后将现在的left_li=[26,54]与 right_li=[17,93]进行合并，最后为[17,26，54,93]，即完成了left_li=alist[:4]=[54,26,93,17]的排序，接下同要完成 right_li=alist[4:]=[31,44,55,20]的排序，同理，结果为[20,31,44,55]，再讲left_li=[54,26,93,17]与right_li=[20,31,44,55]进行合并，最后成为有序序列。

二.搜索

搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的，因为该项目是否存在。 搜索的几种常见方法：顺序查找、二分法查找、二叉树查找、哈希查找

二分法查找： 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

代码实现：

上图代码为利用递归的二分法进行查找。

上图为一般方法。