15分钟学Python 第19天：算法基础

🕗 发布于 2024-09-30 14:44 算法 python 排序算法后端 人工智能

Day19：算法基础

1. 算法基础概述

算法是解决问题的一系列步骤。在计算机科学中，算法通常用于处理数据、执行计算以及完成任务。了解算法的基本概念是编程的重要组成部分，它可以帮助我们解决问题、优化程序和提高运行效率。

2. 时间复杂度和空间复杂度

在分析算法的效率时，时间复杂度和空间复杂度是两个重要的指标。

表示	描述
$O (n)$	线性时间复杂度
$O(n^2)$	平方时间复杂度
$O(\log n)$	对数时间复杂度
$O (1)$	常数时间复杂度

时间复杂度：表示算法执行所需时间，相对于输入规模的增长率。
空间复杂度：表示算法运行所需内存空间的大小，相对于输入规模的增长率。

3. 排序算法

排序算法在数据处理领域至关重要。我们将介绍几种常见的排序算法。

3.1 冒泡排序

冒泡排序是最简单的排序算法，基本思想是通过交换相邻的逆序元素，将最大（或最小）的元素“冒泡”到序列的一端。

冒泡排序示例代码

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 示例运行
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = bubble_sort(arr)
print("Sorted array:", sorted_arr)

运行流程图

开始
  |
  V
初始化 n = len(arr)
  |
  V
外层循环 i 从 0 到 n-1
  |
  V
  内层循环 j 从 0 到 n-i-1
    |
    V
    如果 arr[j] > arr[j+1]
      |
      V
      交换 arr[j] 和 arr[j+1]
  |
  V
结束

3.2 插入排序

插入排序通过构建一个有序序列，逐步将元素插入到正确的位置。它的效率较高，尤其是在处理几乎排好序的数据时。

插入排序示例代码

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 示例运行
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Sorted array:", sorted_arr)

运行流程图

开始
  |
  V
外层循环 i 从 1 到 len(arr)-1
  |
  V
设置 key = arr[i]
  |
  V
内层循环 j 从 i-1 到 0
  |
  V
如果 key < arr[j]
  |
  V
  arr[j+1] = arr[j]
  |
  V
结束

3.3 选择排序

选择排序通过选择未排序部分的最小元素，将其放在已排序序列的末尾。

选择排序示例代码

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 示例运行
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("Sorted array:", sorted_arr)

运行流程图

开始
  |
  V
外层循环 i 从 0 到 n-1
  |
  V
设置 min_idx = i
  |
  V
内层循环 j 从 i+1 到 n
  |
  V
如果 arr[j] < arr[min_idx]
  |
  V
  min_idx = j
结束

3.4 快速排序

快速排序是分治法的一种应用。它通过一个基准元素将数据分为左右两部分，左边是小于基准的元素，右边是大于基准的元素。

快速排序示例代码

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 示例运行
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)

运行流程图

开始
  |
  V
如果 len(arr) <= 1 返回 arr
  |
  V
选择 pivot
  |
  V
创建 left, middle, right 列表
  |
  V
递归调用 quick_sort
  |
  V
合并并返回结果
结束

3.5 归并排序

归并排序也是分治法。它将数组分成两个部分，分别排序后再合并。

归并排序示例代码

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    sorted_array = []
    while left and right:
        if left[0] < right[0]:
            sorted_array.append(left.pop(0))
        else:
            sorted_array.append(right.pop(0))
    sorted_array.extend(left)
    sorted_array.extend(right)
    return sorted_array

# 示例运行
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Sorted array:", sorted_arr)

运行流程图

开始
  |
  V
如果 len(arr) <= 1 返回 arr
  |
  V
找到 mid
  |
  V
分别对左右两部分递归调用 merge_sort
  |
  V
合并两个有序数组
  |
  V
返回合并结果
结束

4. 搜索算法

搜索算法用于在数据结构中查找特定元素。我们将介绍两种常见的搜索算法：线性搜索和二分搜索。

4.1 线性搜索

线性搜索是从数组的一个端开始，逐个比较元素，直到找到目标元素。

线性搜索示例代码

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# 示例运行
arr = [2, 3, 4, 10, 40]
target = 10
result = linear_search(arr, target)
print("Element found at index:", result)

运行流程图

开始
  |
  V
外层循环 i 从 0 到 len(arr)-1
  |
  V
如果 arr[i] == target
  |
  V
返回 i
  |
  V
结束

4.2 二分搜索

二分搜索适用于已排序的数组。通过比较中间元素，并决定在左半部分还是右半部分继续查找，达到快速查找的目的。

二分搜索示例代码

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < target:
            low = mid + 1
        elif arr[mid] > target:
            high = mid - 1
        else:
            return mid
    return -1

# 示例运行
arr = [2, 3, 4, 10, 40]
target = 10
result = binary_search(arr, target)
print("Element found at index:", result)

运行流程图

开始
  |
  V
设置 low = 0, high = len(arr) - 1
  |
  V
循环条件 low <= high
  |
  V
设置 mid = (low + high) // 2
  |
  V
比较 arr[mid] 与 target
  |
  V
根据结果调整 low 或 high
  |
  V
结束

5. 练习题

实现一个选择排序算法，给定任意整数数组，返回排序后的数组。
编写一个快速排序算法，使用递归来分治。
编写线性搜索和二分搜索的对比代码，给定一个随机整数数组及目标值，比较两种搜索的效率。
想象你是一名数据分析师，给定一个包含学生成绩的数组，请使用归并排序来对成绩进行排序，并使用二分搜索来查找某个特定的成绩。

6. 项目作业

请尝试完成以下项目作业：

选择一个数据集（如电子商务网站的商品价格），实现合适的排序算法对其进行排序，并结合搜索算法查找特定商品的价格。
尝试实现一个图形用户界面（GUI），允许用户输入一组数字，选择排序算法，然后查看排序和搜索结果。

怎么样今天的内容还满意吗？再次感谢观众老爷的观看。
最后，祝您早日实现财务自由，还请给个赞，谢谢！

原文地址：https://blog.csdn.net/weixin_40780178/article/details/142478916

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：C++ VECTOR容器
下一篇：滚雪球学MySQL[7.1讲]：安全管理

window10解决 docker is starting 问题
win10 需要开启 Hyper-V。在程序和功能中开启服务Server (不开启的话，安装完会报错)安装toolbox 最新版 Toolbox 下载地址：访问，注册一个账号，然后登录。点击 Get
阅读更多2024-11-06
JavaScript数据类型- BigInt详解（处理任意大小整数的终极指南）
随着ECMAScript 11（ES11）引入了BigInt，JavaScript开发者现在可以轻松地处理超出传统Number类型限制的大整数。本文全面解析了BigInt的使用方法、核心特性和限制条件
阅读更多2024-11-06
ubuntu下使用pocketsphinx进行语音识别
由于工作需要语音识别的功能，环境是在linux arm版上，所以想先在ubuntu上跑起来看一看，就找了一下语音识别的开源框架，选中了很多框架可以看编译vosk那篇文章，现在一一试验一下。网上对于po
阅读更多2024-11-06
时间段比较与 SQL 实现：交集、并集与补集
时间段比较是一个非常常见的操作，尤其是在涉及调度、事件分析和时间管理的应用中。通过掌握 SQL 中关于时间段交集、并集和补集的查询方式，我们能够高效地处理时间段相关的数据。希望本文的示例和分析能帮助你
阅读更多2024-11-06
flink 内存配置（四）：内存调优和问题处理
本节解释如何根据用例设置内存，以及每种用例中哪些选项是重要的。
阅读更多2024-11-06
深度学习：解密图像、音频和视频数据的“理解”之道20241105
深度学习是一个充满无限可能的领域。无论是图像、音频还是视频数据，深度学习模型都能找到最有效的方式进行处理和理解。希望这篇文章让你对深度学习背后的数据解析过程有了更清晰的认识。你有什么见解或疑问？欢迎留
阅读更多2024-11-06
TOSHIBA 74VHC00FT COMS汽车、工业企业的选择
74VHC00FT集成了四个独立的 NAND 门，每个门都有两个输入。NAND 门是数字逻辑电路中的基本构建模块，只有当所有输入都为高时输出为低。该芯片可以在各种设备中执行逻辑操作，包括计算机、计算器
阅读更多2024-11-06
19. 架构重要需求
对架构师来说，并非所有需求都是同等重要的。有些需求对架构的影响比其他需求大得多。一个 “**架构重要需求（ASR）**” 是一个将对架构产生深远影响的需求 —— 也就是说，如果没有这样的需求，架构很可
阅读更多2024-11-06
[大模型]视频生成-Sora简析
Sora模型的简述
阅读更多2024-11-06
Kubernetes的概述与架构
Kubernetes的概述与架构。
阅读更多2024-11-06

15分钟学Python 第19天 ： 算法基础

Day19： 算法基础

目录

1. 算法基础概述

2. 时间复杂度和空间复杂度

3. 排序算法

3.1 冒泡排序

冒泡排序示例代码

运行流程图

3.2 插入排序

插入排序示例代码

运行流程图

3.3 选择排序

选择排序示例代码

运行流程图

3.4 快速排序

快速排序示例代码

运行流程图

3.5 归并排序

归并排序示例代码

运行流程图

4. 搜索算法

4.1 线性搜索

线性搜索示例代码

运行流程图

4.2 二分搜索

二分搜索示例代码

运行流程图

5. 练习题

6. 项目作业

相关文章

15分钟学Python 第19天：算法基础

Day19：算法基础