python实现折半查找和归并排序算法

python实现折半查找和归并排序算法

今天依旧是学算法，前几天在搞bbs项目，界面也很丑，评论功能好像也有BUG。现在不搞了，得学下算法和数据结构，笔试过不了，连面试的机会都没有……

今天学了折半查找算法，折半查找是蛮简单的，但是归并排序我就挺懵比，看教材C语言写的归并排序看不懂，后来参考了别人的博客，终于搞懂了。

折半查找

先看下课本对于 折半查找的讲解。注意了，折半查找是对于有序序列而言的。每次折半，则查找区间大约缩小一半。low,high分别为查找区间的第一个下标与最后一个下标。出现low>high时，说明目标关键字在整个有序序列中不存在，查找失败。

看我用python编程实现:

defBinSearch(array, key, low, high): mid=int((low+high)/2) ifkey==array[mid]:# 若找到 returnarray[mid] iflow > high: returnFalse ifkey < array[mid]: returnBinSearch(array, key, low, mid-1)#递归 ifkey > array[mid]: returnBinSearch(array, key, mid+1, high) if__name__=="__main__": array=[4,13,27,38,49,49,55,65,76,97] ret=BinSearch(array,76,0,len(array)-1)# 通过折半查找，找到65 print(ret)

输出: 在列表中查找76

76

时间复杂度：O(logn)

归并排序算法

先阐述一下排序思路：

首先归并排序使用了二分法，归根到底的思想还是分而治之。归并排序是指把无序的待排序序列分解成若干个有序子序列，并把有序子序列合并为整体有序序列的过程。长度为1的序列是有序的。因此当分解得到的子序列长度大于1时，应继续分解，直到长度为1

(下图是分解过程，图自python编程实现归并排序)

合并的过程如下:

很好，你现在可以和别人说，老子会归并排序了。但是让你写代码出来，相信你是不会的……

来来来，看我用python写的归并排序算法:

defmerge_sort(array):# 递归分解 mid=int((len(array)+1)/2) iflen(array)==1:# 递归结束的条件，分解到列表只有一个数据时结束 returnarray list_left=merge_sort(array[:mid]) list_right=merge_sort(array[mid:]) print(">>>list_left:", list_left) print(">>>list_right:", list_right) returnmerge(list_left, list_right)# 进行归并 defmerge(list_left, list_right):# 进行归并 final=[] whilelist_leftandlist_right: iflist_left[0] <=list_right[0]:# 如果将"<="改为"<",则归并排序不稳定 finalappend(list_leftpop(0)) else: finalappend(list_rightpop(0)) returnfinal+list_left+list_right# 返回排序好的列表 if__name__=="__main__": array=[49,38,65,97,76] print(merge_sort(array))输出:

输出：

>>>list_left: [49]

>>>list_right: [38]

>>>list_left: [38, 49]

>>>list_right: [65]

>>>list_left: [97]

>>>list_right: [76]

>>>list_left: [38, 49, 65]

>>>list_right: [76, 97]

[38, 49, 65, 76, 97]

时间度杂度: 平均情况＝最好情况＝最坏情况＝O(nlogn)

空间复杂度:O(n)

稳定性:稳定

对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }进行归并排序的实例如下:

使用归并排序为一列数字进行排序的宏观过程:

以上就是本文的全部内容，希望对大家的学习有所帮助

归并排序

归并排序也称合并排序，是分治法的典型应用。分治思想是将每个问题分解成个个小问题，将每个小问题解决，然后合并。

具体的归并排序就是，将一组无序数按n/2递归分解成只有一个元素的子项，一个元素就是已经排好序的了。然后将这些有序的子元素进行合并。

合并的过程就是 对 两个已经排好序的子序列，先选取两个子序列中最小的元素进行比较，选取两个元素中最小的那个子序列并将其从子序列中

去掉添加到最终的结果集中，直到两个子序列归并完成。

代码如下：

#!/usr/bin/python  import sys    def merge(nums, first, middle, last):      ''''' merge '''      # 切片边界,左闭右开并且是了0为开始      lnums = nums[first:middle+1]      rnums = nums[middle+1:last+1]      lnumsappend(sysmaxint)      rnumsappend(sysmaxint)      l = 0      r = 0      for i in range(first, last+1):          if lnums[l] < rnums[r]:              nums[i] = lnums[l]              l+=1          else:              nums[i] = rnums[r]              r+=1  def merge_sort(nums, first, last):      ''''' merge sort    merge_sort函数中传递的是下标，不是元素个数    '''      if first < last:          middle = (first + last)/2          merge_sort(nums, first, middle)          merge_sort(nums, middle+1, last)          merge(nums, first, middle,last)    if __name__ == '__main__':      nums = [10,8,4,-1,2,6,7,3]      print 'nums is:', nums      merge_sort(nums, 0, 7)      print 'merge sort:', nums

稳定，时间复杂度 O(nlog n)

插入排序

代码如下：

#!/usr/bin/python  importsys    definsert_sort(a):      ''''' 插入排序    有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，    但要求插入后此数据序列仍然有序。刚开始 一个元素显然有序，然后插入一    个元素到适当位置，然后再插入第三个元素，依次类推    '''      a_len = len(a)      if a_len = 0 and a[j] > key:              a[j+1] = a[j]              j-=1          a[j+1] = key      return a    if __name__ == '__main__':      nums = [10,8,4,-1,2,6,7,3]      print 'nums is:', nums      insert_sort(nums)      print 'insert sort:', nums

稳定，时间复杂度 O(n^2)

交换两个元素的值python中你可以这么写：a, b = b, a，其实这是因为赋值符号的左右两边都是元组

（这里需要强调的是，在python中，元组其实是由逗号“,”来界定的，而不是括号）。

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到

排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所

有元素均排序完毕。

Hello，大家好，我是程序汪小成~

虽然python是一个易入门的语言，但是很多人依然还是会问到底怎么样学 Python 才最快，答案当然是实战各种小项目， 只有自己去想与写，才记得住规则 。本文写的是 10 个极简任务，初学者可以尝试着自己实现；本文同样也是 10段代码，Python 开发者也可以看看是不是有没想到的用法。

以下方法可以检查给定列表是不是存在重复元素，它会使用 set() 函数来移除所有重复元素。

给定具体的大小，定义一个函数以按照这个大小切割列表。

这个方法可以将布尔型的值去掉，例如（False，None，0，“”），它使用 filter() 函数。

我们常用 For 循环来遍历某个列表，同样我们也能枚举列表的索引与值。

如下代码段可以将打包好的成对列表解开成两组不同的元组。

该方法将通过递归的方式将列表的嵌套展开为单个列表。

该方法将返回第一个列表的元素，且不在第二个列表内。如果同时要反馈第二个列表独有的元素，还需要加一句 set_bdifference(set_a)。

如下代码块可以用来计算执行特定代码所花费的时间。

该算法会打乱列表元素的顺序，它主要会通过 Fisher-Yates 算法对新列表进行排序：

不需要额外的 *** 作就能交换两个变量的值。

以上，是我简单列举的十个python极简代码，拿走即用，希望对你有所帮助！

以上就是关于python实现折半查找和归并排序算法全部的内容，包括:python实现折半查找和归并排序算法、在python中,如i=、10个极简python代码，拿走即用等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！