Python数据结构与算法(六)–归并排序、排序总结、二分查找

587-王同学

发表文章数:79

首页 » 数据结构 » 正文

归并排序

  • 思想

简单地将原始序列划分成两个子序列,分别对每个子序列递归排序,最后将排好序的子序列合并为一个有序序列

先拆成一个一个的,然后两个合并一起,并排好序

两个两个的合并成四个的时候,需要左边一个指针left指向左边第一个元素,右边一个指针right指向右边第一个元素,两个元素比较,谁小放到左边,然后挪一下指针

  • 性质

稳定

时间复杂度:

O(nlogn)

(最优、最坏一样)

#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: Caramel
@file: 6.1_merge_sort.py
@time: 2020/02/12
@desc:归并排序
"""
def merge_sort(alist):
    n = len(alist)
    if n <= 1:
        return alist
    mid = n // 2
    '''采用归并排序后形成的新的列表'''
    left_li = merge_sort(alist[:mid])
    right_li = merge_sort(alist[mid:])
    '''将两个有序的子序列合并成一个整体'''
    left_index = 0
    right_index = 0
    result = []
    while left_index < len(left_li) and right_index < len(right_li):
        if left_li[left_index] <= right_li[right_index]:
            '''等号保证稳定性'''
            result.append(left_li[left_index])
            left_index += 1
        else:
            result.append(right_li[right_index])
            right_index += 1
    result += left_li[left_index:]
    result += right_li[right_index:]
    return result
if __name__ == '__main__':
    il = [15, 15, 65, 16, 86, 10, 63]
    print(il)
    sorted = merge_sort(il)
    print(sorted)
  • 执行过程

先是对左边的进行递归,分裂直到剩最后一个元素54,然后执行两个元素[54, 26]的右边递归,得到第一个两个的右边元素26

他们两个执行合并操作,变成[26, 54]。以此类推。

Python数据结构与算法(六)--归并排序、排序总结、二分查找

  • 执行结束后不是在原有的列表上进行改动,而是在重新生成一个等大的有序列表。虽然时间复杂度降低,但是代价是空间。

排序比较

Python数据结构与算法(六)--归并排序、排序总结、二分查找

搜索

  • 二分法查找

前提:

数据已是有序的

操作对象支持下标索引

即是有序顺序表

 

先预处理数据,顺序由小到大排列。取中值,关键码与其比较,若果大于就在大的那一部分找,同理。

计算下标时,用第一个和最后一个的下标计算

#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: Caramel
@file: 6.2_binary_search.py
@time: 2020/02/12
@desc:二分查找
"""
def binary_search(alist, item):
    '''递归'''
    n = len(alist)
    if n >= 2:
        mid = n//2
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            return binary_search(alist[:mid], item)
        else:
            return binary_search(alist[mid:], item)
    return False
def binary_search_2(alist, item):
    '''非递归'''
    n = len(alist)
    fir = 0
    last = n - 1
    while fir <= last:
        mid = (last + fir) // 2
        if alist[mid] == item:
            return True
        elif item < alist[mid]:
            last = mid - 1
        else:
            fir = mid + 1
    return False
if __name__ == '__main__':
    li = [10, 15, 15, 16, 63, 65, 86]
    print(binary_search(li, 65))
    print(binary_search(li, 98))
    print(binary_search_2(li, 65))
    print(binary_search_2(li, 98))

ASL:

log2(n+1)-1

 

成功检索:

log2(n+1)向上取整

 

失败检索:

log2(n+1)向上或者向下取整

 

时间复杂度:

最坏:

O(logn)

最好:

O(1)

 

拜师教育学员文章:作者:587-王同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Python数据结构与算法(六)–归并排序、排序总结、二分查找》 发布于2020-02-12

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录