Python—算法——-归并排序,二分查找

1146-陶同学

发表文章数:37

首页 » 数据结构 » 正文

归并排序:

归并排序将数组分解最小之后,然后合并两个有序数组,基本思路是比较两个数组的最前面的数,谁小就先取谁,取了后相应的指针就往后移一位。然后再比较,直至一个数组为空,最后把另一个数组的剩余部分复制过来即可。

最优时间复杂度位:O(nlogn)

最坏时间复杂度位:O(nlogn)

稳定性:稳定

def merge_sort(alist):
    n = len(alist)
    if n <= 1:
        return alist
    mid = n // 2
    # left,right 采用归并排序后形成的有序的新的列表
    left_li = merge_sort(alist[:mid])
    right_li = merge_sort(alist[mid:])
    # 将两个有序的子序列合并为一个新的整体
    # merge(left,right)
    left_pointer, right_pointer = 0, 0
    result = []
    while left_pointer < len(left_li) and right_pointer < len(right_li):
        if left_li[left_pointer] < right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]
    return result

二分查找:

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难

最优时间复杂度:O(1)

最坏时间复杂度:O(logn)

def binary_search(alist, item):
      first = 0
      last = len(alist)-1
      while first<=last:
          midpoint = (first + last)/2
          if alist[midpoint] == item:
              return True
          elif item < alist[midpoint]:
              last = midpoint-1
          else:
              first = midpoint+1
    return False
def binary_search(alist, item):
    n = len(alist)
    if n > 0:
        mid = n // 2
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            return binary_search(alist[:mid])
        else:
            return binary_search(alist[mid:])
    return False

 

未经允许不得转载:作者:1146-陶同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python—算法——-归并排序,二分查找》 发布于2020-07-04

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录