python归并排序函数 归并排序函数代码

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

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

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

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

折半查找

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

看我用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]:# 如果将"="改为"",则归并排序不稳定 final.append(list_left.pop(0)) else: final.append(list_right.pop(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 }进行归并排序的实例如下:

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

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

python实现归并排序时报错

因为merge_sort函数没有返回值,所以l1=merge_sort(left)和r1=merge_sort(right)中出l1和r1没有类型的错误,加一个返回值return li就没问题了.

完整的Python程序如下(改动的地方见注释)

def merge_sort(li):

 if len(li)==1:

  return li  #这里return改成return li

 mid=len(li)//2

 left=li[:mid]

 right=li[mid:]

 l1=merge_sort(left)

 r1=merge_sort(right)

 return merge(l1,r1)

def merge(left,right):

 result=[]

 while len(left)0 and len(right)0:

  if left[0]=right[0]:

   result.append(left.pop(0))

  else:

   result.append(right.pop(0))

 result+=left

 result+=right

 return result

a=[2,39,92,19,28,32,85,53]

print(merge_sort(a))

源代码(注意源代码的缩进)

在python中,如i=

归并排序

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

具体的归并排序就是，将一组无序数按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]      lnums.append(sys.maxint)      rnums.append(sys.maxint)      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)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到

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

有元素均排序完毕。

关于python归并排序函数和归并排序函数代码的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。