锐客网

  1. 首页 > 睿知 > it技术 > >

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

IT技术归并

python实现折半查找和归并排序算法python实现折半查找和归并排序算法
今天依旧是学算法，前几天在搞bbs项目，界面也很丑 ， 评论功能好像也有BUG 。现在不搞了，得学下算法和数据结构，笔试过不了 ， 连面试的机会都没有……
今天学了折半查找算法 ， 折半查找是蛮简单的 ， 但是归并排序我就挺懵比，看教材C语言写的归并排序看不懂，后来参考了别人的博客，终于搞懂了 。
折半查找
先看下课本对于 折半查找的讲解 。注意了，折半查找是对于有序序列而言的 。每次折半，则查找区间大约缩小一半 。low,high分别为查找区间的第一个下标与最后一个下标 。出现lowhigh时，说明目标关键字在整个有序序列中不存在，查找失败 。
看我用python编程实现:
defBinSearch(array, key, low, high): mid=int((low high)/2) ifkey==array[mid]:# 若找到returnarray[mid] iflowhigh:returnFalseifkeyarray[mid]:returnBinSearch(array, key, low, mid-1)#递归 ifkeyarray[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))输出:
【python归并排序函数 归并排序函数代码】输出：
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/pythonimport sysdef 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 = 0r = 0for i in range(first, last 1):if lnums[l]rnums[r]:nums[i] = lnums[l]l =1else:nums[i] = rnums[r]r =1def merge_sort(nums, first, last):''''' merge sortmerge_sort函数中传递的是下标，不是元素个数'''if firstlast:middle = (firstlast)/2merge_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:', numsmerge_sort(nums, 0, 7)print 'merge sort:', nums
稳定，时间复杂度 O(nlog n)
插入排序
代码如下：
#!/usr/bin/pythonimportsysdefinsert_sort(a):''''' 插入排序有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序 。刚开始 一个元素显然有序，然后插入一个元素到适当位置，然后再插入第三个元素，依次类推'''a_len = len(a)if a_len = 0 and a[j]key:a[j 1] = a[j]j-=1a[j 1] = keyreturn aif __name__ == '__main__':nums = [10,8,4,-1,2,6,7,3]print 'nums is:', numsinsert_sort(nums)print 'insert sort:', nums
稳定，时间复杂度 O(n^2)
交换两个元素的值python中你可以这么写：a, b = b, a ， 其实这是因为赋值符号的左右两边都是元组
（这里需要强调的是，在python中，元组其实是由逗号“,”来界定的 ， 而不是括号） 。
选择排序
选择排序(Selection sort)是一种简单直观的排序算法 。它的工作原理如下 。首先在未排序序列中找到最?。ù螅┰兀娣诺?
排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最?。ù螅┰兀?然后放到已排序序列的末尾 。以此类推，直到所
有元素均排序完毕 。
关于python归并排序函数和归并排序函数代码的介绍到此就结束了 ， 不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站 。

    推荐阅读


    上一篇：如何找到隐藏的服务器？ 怎么样追查不到服务器

    下一篇：如何在IIS服务器上进行文件上传？ iis服务器怎么上传