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讲]：安全管理

MySQL数据库基础
在过去的mysql中主要是使用的utf8mb3，但是mysql显示的就是utf8，中mysql8中区分显示了。类似于不同的编译器，虽然C/C++的代码是一样的，但是预处理、编译、汇编、链接这些过程却不
阅读更多2024-09-30
Percona Monitoring and Management
Percona Monitoring and Management (PMM)是一款开源的专用于管理和监控MySQL、MongoDB、PostgreSQL。
阅读更多2024-09-30
鸿蒙开发（NEXT/API 12）【已连接穿戴设备查询】手机侧应用开发
Wear Engine提供查询用户已连接的穿戴设备列表（即支持Wear Engine能力且与手机侧运动健康App处于连接状态的穿戴设备）的接口。
阅读更多2024-09-30
Redis数据库
本篇文章介绍了redis的相关知识，并使用springboot集成redis，实现缓存和分布式锁，后续会对文章勘误及更新~~
阅读更多2024-09-30
旧版的存档
【代码】旧版的存档。
阅读更多2024-09-30
Spring Boot 封装统一返回结果及全局异常处理
为了更细致地控制异常处理，我们可以定义一些自定义异常。然后，在全局异常处理器中添加对自定义异常的处理。通过封装统一的返回结果和全局异常处理，我们可以让Spring Boot应用更加健壮和易于维护。这种
阅读更多2024-09-30
【C++】IO流
C++IO流，包含输入输出流、文件流、字符流
阅读更多2024-09-30
低至1元/小时：国庆七天，30元通关《黑神话：悟空》！
随着《黑神话：悟空》自8月20日全球同步上线，正式登陆PC、PS5平台以来，以其精湛的画面和流畅的战斗体验，在发售三天后，该作的全平台销量超过1000万套，打破中国游戏历史记录，被媒体称为“中国首款3
阅读更多2024-09-30
阿里巴巴国际站获取商品详情item_get接口技术分享
item_get API接口是阿里巴巴开放平台提供的一个重要接口，它允许商家通过API调用，获取阿里巴巴平台上的商品详细信息。这些信息包括商品标题、价格、库存、属性、描述等，为商家提供了全面、准确的商
阅读更多2024-09-30
软件测试谣言二三事，认真你就输了
软件测试的职业寿命，取决于互联网行业能存活多久，至少目前看来，这个职业没有消失的风险，至于你能在这个职业待多久，那取决于你自己的能力，我见过不少超过35岁的老员工还在测试的职位上兢兢业业。以广州为例，
阅读更多2024-09-30

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：算法基础