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

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

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

折半查找

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

看我用python编程实现:

def BinSearch(array, key, low, high):
 mid = int((low+high)/2)
 if key == array[mid]: # 若找到
  return array[mid]
 if low > high:
  return False

 if key < array[mid]:
  return BinSearch(array, key, low, mid-1) #递归
 if key > array[mid]:
  return BinSearch(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写的归并排序算法:

def merge_sort(array): # 递归分解
 mid = int((len(array)+1)/2)
 if len(array) == 1: # 递归结束的条件,分解到列表只有一个数据时结束
  return array
 list_left = merge_sort(array[:mid])
 list_right = merge_sort(array[mid:])
 print(">>>list_left:", list_left)
 print(">>>list_right:", list_right)
 return merge(list_left, list_right) # 进行归并

def merge(list_left, list_right): # 进行归并
 final = []
 while list_left and list_right:
  if list_left[0] <= list_right[0]: # 如果将"<="改为"<",则归并排序不稳定
   final.append(list_left.pop(0))
  else:
   final.append(list_right.pop(0))

 return final+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 }进行归并排序的实例如下:

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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Python使用回溯法子集树模板解决迷宫问题示例

    本文实例讲述了Python使用回溯法解决迷宫问题.分享给大家供大家参考,具体如下: 问题 给定一个迷宫,入口已知.问是否有路径从入口到出口,若有则输出一条这样的路径.注意移动可以从上.下.左.右.上左.上右.下左.下右八个方向进行.迷宫输入0表示可走,输入1表示墙.为方便起见,用1将迷宫围起来避免边界问题. 分析 考虑到左.右是相对的,因此修改为:北.东北.东.东南.南.西南.西.西北八个方向.在任意一格内,有8个方向可以选择,亦即8种状态可选.因此从入口格子开始,每进入一格都要遍历这8种状态.

  • Python基于回溯法子集树模板解决取物搭配问题实例

    本文实例讲述了Python基于回溯法子集树模板解决取物搭配问题.分享给大家供大家参考,具体如下: 问题 有5件不同的上衣,3条不同的裤子,4顶不同的帽子,从中取出一顶帽子.一件上衣和一条裤子作为一种搭配,问有多少种不同的搭配? 分析 换个角度看,现有头.身.腿三个元素,每个元素都有各自的几种状态. 头元素有['帽1', '帽2', '帽3', '帽4']共4种状态,身元素有['衣1', '衣2', '衣3', '衣4', '衣5']共5种状态,腿元素有['裤1', '裤2', '裤3']共3种状

  • python回溯法实现数组全排列输出实例分析

    本文实例讲述了python回溯法实现数组全排列输出的方法.分享给大家供大家参考.具体分析如下: 全排列解释:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列.当m=n时所有的排列情况叫全排列. from sys import stdout #code from http://www.jb51.net/ def perm(li, start, end): if(start == end): for elem in li: stdout.wr

  • 用Python实现随机森林算法的示例

    拥有高方差使得决策树(secision tress)在处理特定训练数据集时其结果显得相对脆弱.bagging(bootstrap aggregating 的缩写)算法从训练数据的样本中建立复合模型,可以有效降低决策树的方差,但树与树之间有高度关联(并不是理想的树的状态). 随机森林算法(Random forest algorithm)是对 bagging 算法的扩展.除了仍然根据从训练数据样本建立复合模型之外,随机森林对用做构建树(tree)的数据特征做了一定限制,使得生成的决策树之间没有关联,

  • Python基于回溯法子集树模板解决数字组合问题实例

    本文实例讲述了Python基于回溯法子集树模板解决数字组合问题.分享给大家供大家参考,具体如下: 问题 找出从自然数1.2.3.....n中任取r个数的所有组合. 例如,n=5,r=3的所有组合为: 1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5 分析 换个角度,r=3的所有组合,相当于元素个数为3的所有子集.因此,在遍历子集树的时候,对元素个数不为3的子树剪枝即可. 注意,这里不妨使用固定长度的解. 直接套用子集树模板.

  • Python基于递归算法实现的走迷宫问题

    本文实例讲述了Python基于递归算法实现的走迷宫问题.分享给大家供大家参考,具体如下: 什么是递归? 简单地理解就是函数调用自身的过程就称之为递归. 什么时候用到递归? 如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法. 迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题. 在python中可以使用list

  • Python实现的文本简单可逆加密算法示例

    本文实例讲述了Python实现的文本简单可逆加密算法.分享给大家供大家参考,具体如下: 其实很简单,就是把一段文本每个字符都通过某种方式改变(比如加1) 这样就实现了文本的加密操作,解密就是其逆运算 # -*-coding:utf-8 -*- import sys reload(sys) sys.setdefaultencoding('utf8') #加密 def jiami(): filename=raw_input('please input file:\n') while True: tr

  • Python基于回溯法子集树模板解决0-1背包问题实例

    本文实例讲述了Python基于回溯法子集树模板解决0-1背包问题.分享给大家供大家参考,具体如下: 问题 给定N个物品和一个背包.物品i的重量是Wi,其价值位Vi ,背包的容量为C.问应该如何选择装入背包的物品,使得放入背包的物品的总价值为最大? 分析 显然,放入背包的物品,是N个物品的所有子集的其中之一.N个物品中每一个物品,都有选择.不选择两种状态.因此,只需要对每一个物品的这两种状态进行遍历. 解是一个长度固定的N元0,1数组. 套用回溯法子集树模板,做起来不要太爽!!! 代码 '''0-

  • Python多线程经典问题之乘客做公交车算法实例

    本文实例讲述了Python多线程经典问题之乘客做公交车算法.分享给大家供大家参考,具体如下: 问题描述: 乘客乘坐公交车问题,司机,乘客,售票员协同工作,通过多线程模拟三者的工作. 司机:开车,停车 售票员:打开车门,关闭车门 乘客:上车,下车 用Python的Event做线程同步通信,代码如下: # *-* coding:gb2312 *-* import threading import time stationName=("车站0","车站1","车

  • Python基于回溯法子集树模板实现8皇后问题

    本文实例讲述了Python基于回溯法子集树模板实现8皇后问题.分享给大家供大家参考,具体如下: 问题 8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 分析 为了简化问题,考虑到8个皇后不同行,则每一行放置一个皇后,每一行的皇后可以放置于第0.1.2.....7列,我们认为每一行的皇后有8种状态.那么,我们只要套用子集树模板,从第0行开始,自上而下,对每一行的皇后,遍历它的8个状态即可. 代码: ''' 8皇后问题 '''

随机推荐