IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 数据结构和算法学习(python实现) -> 正文阅读

[数据结构与算法]数据结构和算法学习(python实现)

算法与数据结构

时间复杂度

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n^3)

空间复杂度

内存占用(空间换时间)

递归

  • 调用自身
  • 结束条件

经典汉诺塔问题

h(n) = 2h(n-1) + 1

def hanoi(n, a, b, c):
    if n > 0:
        hanoi(n-1, a, c, b)
        print("moving from %s to %s" %(a, c))
        hanoi(n-1, b, a, c)

1. 查找

查找目标值的索引

python内置查找函数index()(使用线性查找)

1.1 顺序查找(线性查找)Linear Search

def linear_search(li, val):
    for i in range(range(li)):
        if li[i] == val:
            return i
    return

时间复杂度O(n)

1.2 二分查找 Binary Search

二分查找首要条件序列有序

def binary_search(li, val):
    left = 0
    right = len(li) - 1
    while left < right:
        mid = (left + right) // 2
        if li[mid] == val:
            return mid
        elif li[mid] > val:
            right = mid -1
        else:
            left = mid +1
    else:
        return None

时间复杂度O(logn)

2. 排序

内置函数sort()

  • sort:改变原序列

  • sorted:不改变原序列

1.1 冒泡排序 Bubble Sort

  • 分为无序区和有序区
  • 列表每两个相邻的数,如果前面比后面的数大,则交换两个数的位置
  • 完成一轮排序之后,无序区减少一个数,有序区增加一个数
def bubble_sort(li):
    for i in range(len(li)-1):
        exchange = False
        for j in range(len(li)-i-1):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
            	exchange = True
        if not exchange:
            return 

时间复杂度O(n^2)

1.2 选择排序 Select Sort

  • 将无序区第一个数与全序列比较大小,与最小的数交换位置
  • 将第一轮排序最小的数,放到第一个位置
  • 再一轮排序纪录无序区最小的数放入第二个位置,依次类推
  • 算法关键点:有序区和无序区、无序区最小数的位置
def select_sort(li):
    for i in range(len(li)-1):
        min_loc = i
        for j in range(i+1, len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
        if min_loc != i:
            li[i], li[min_loc] = li[min_loc], li[i]
            

时间复杂度O(n^2)

1.3 插入排序 Insert Sort

  • 将初始待排序序列第一个元素划入有序区,后面的全部划为无序区
  • 从头到位依次扫描无序区,将扫描到的每个元素插入有序区的适当位置(如果待插入元素与有序区中某个元素相等,则将其插入到相等元素的后面)
def insert_sort(li):
    for i in range(1, len(li)-1):    #抽取的第i个数的索引
        tmp = li[i]
        j = i-1     #初始有序区的索引
        while j >= 0 and li[j] > tmp:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp

时间复杂度O(n^2)

1.4 快速排序 Quick Sort

使用分治法

  • 先从序列中抽取一个数作为基准数
  • 分区,将比这个数大的全放在它的右边,小于等于的全放左边
  • 左右区间重复以上操作,知道各区间只剩下一个为止
def partition(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] >= tmp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] <= tmp:
            left += 1
        li[right] = li[left]
    li[left] = tmp
    return left

def quick_sort(li, left, right):
    if left < right:
        mid = partition(li, left, right)
        quick_sort(li, left, mid-1)
        quick_sort(li, mid+1, right)

时间复杂度O(nlogn)

1.5 堆排序 heap_sort

1.5.1 树与二叉树

树是一种可以递归定义的数据结构

树是由n个节点组成的集合

  • 如果n=0,那这是一棵空树
  • 如果n>0,那存在1个节点作为树的根节点,其他节点可以分为m个集合,每个集合本身又是一棵树

满二叉树:每层节点数都达到最大值

完全二叉树:叶子节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

1.5.2 二叉树的存储方式

  • 链式存储方式
  • 顺序存储方式(列表)

父节点和左子节点的编号下标的关系 2i+1

父节点和右子节点的编号下标的关系 2i+2

1.5.3 堆

堆是一种特殊的完全二叉树

  • 大根堆:一棵完全二叉树,满足任一节点都比子节点大
  • 小根堆:一棵完全二叉树,满足任一节点都比子节点小

堆下调整的性质

  • 假设根节点的左右子树都是堆,但根节点不满足堆的性质
  • 可以通过一次向下调整来将其变成一个堆

1.5.4 堆排序过程

  • 建立堆
  • 得到堆顶元素,为最大元素
  • 去掉堆顶,将堆最后一个元素放到堆顶,此时可通过一次调整使堆重新有序(保证完全二叉树)
  • 堆顶元素为第二大元素
  • 重复步骤三,直到堆空

构造堆(农村包围城市)

def sift(li, low, high):
    """
    :param li:
    :param low:初始堆顶
    :param high:
    :return:
    """
    i = low
    j = 2 * i + 1
    tmp = li[i]
    while j <= high:
        if j < high and li[j] < li[j+1]:
            j += 1
        if tmp < li[j]:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            break
    li[i] = tmp

def heap_sort(li):
    n = len(li)
    for i in range(n//2-1, -1, -1):
        sift(li, i, n-1)
    for i in range(n-1, -1, -1):
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i-1)
li = [i for i in range(1000)]
import random
random.shuffle(li)

heap_sort(li)
print(li)

时间复杂度O(nlogn)

1.5.5 内置模块 heapq

常用函数

heapify(x) 建堆

heappush(heap,item)

heappop(heap)

1.5.6 topk问题

现有n个数,设计算法得到前k大的数(k<n)

解决思路:

  • 排序后切片 O(nlogn)
  • 冒泡,插入,选择 O(mn)
  • 使用堆排序 O(mlogn)
    • 取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数
    • 依次向后遍历原列表,对于列表中的元素,如果小于堆顶,则忽略该元素;如果大于堆顶,则将堆顶更换为该元素,并且对堆进行一次调整
    • 遍历列表所有元素后,倒序弹出堆顶
def sift(li, low, high):
    i = low
    j = 2 * i + 1
    tmp = li[i]
    while j <= high:
        if j + 1 <= high and li[j] > li[j+1]:
            j += 1
        if tmp > li[j]:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            break
    li[i] = tmp

def topk(li, k):
    # 建堆
    heap = li[0:k]
    for i in range((k-2)//2, -1, -1):
        sift(heap, i, k-1)
    # 遍历
    for i in range(k, len(li)-1):
        if li[i] > heap[0]:
            heap[0] = li[i]
            sift(heap, 0, k-1)
    # 出数
    for i in range(k-1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        sift(heap, 0, i-1)
    return heap

li = [i for i in range(100)]
import random
random.shuffle(li)
print(li)

print(topk(li, 10))
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-08-19 19:31:09  更:2022-08-19 19:34:15 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/28 18:53:00-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计