当前位置: 首页 > news >正文

主流排序算法

  1. 冒泡排序(Bubble Sort):

    • 基本思想:通过比较相邻元素的大小,不断交换相邻元素的位置,使得较大的元素逐渐“浮”到数组的最后。
    • 时间复杂度:O(n^2)。
  2. 选择排序(Selection Sort):

    • 基本思想:每一次从未排序的部分中选择最小的元素,将其放在已排序部分的末尾。
    • 时间复杂度:O(n^2)。
  3. 插入排序(Insertion Sort):

    • 基本思想:将数组分为已排序和未排序两部分,每次从未排序部分选择一个元素插入到已排序部分的合适位置。
    • 时间复杂度:O(n^2)。
  4. 快速排序(Quick Sort):

    • 基本思想:通过选择一个基准元素,将数组划分为左右两部分,左边的元素都小于基准,右边的元素都大于基准,然后递归地对左右两部分进行排序。
    • 时间复杂度:平均情况下为O(n log n)。
  5. 归并排序(Merge Sort):

    • 基本思想:将数组分成两个部分,分别对这两个部分进行排序,然后合并这两个有序的部分。
    • 时间复杂度:始终为O(n log n),但需要额外的空间。
  6. 堆排序(Heap Sort):

    • 基本思想:利用堆的数据结构,将数组看作一个二叉堆,然后利用堆的性质进行排序。
    • 时间复杂度:O(n log n)。
  7. 计数排序(Counting Sort):

    • 基本思想:对每一个输入元素x,确定小于x的元素个数,从而确定x在输出序列中的位置。
    • 时间复杂度:O(n + k),其中k是最大元素的范围。
  8. 基数排序(Radix Sort):

    • 基本思想:从低位到高位,对输入元素进行多次排序,每次都是根据某一位上的数值进行排序。
    • 时间复杂度:O(d * (n + k)),其中d是最大数字的位数,k是进制。

简单代码示例:

  1. 冒泡排序(Bubble Sort):
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]# 示例
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("冒泡排序结果:", arr)
  1. 选择排序(Selection Sort):
def selection_sort(arr):n = len(arr)for i in range(n):min_index = ifor j in range(i+1, n):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]# 示例
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("选择排序结果:", arr)
  1. 插入排序(Insertion Sort):
def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and key < arr[j]:arr[j + 1] = arr[j]j -= 1arr[j + 1] = key# 示例
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("插入排序结果:", arr)
  1. 快速排序(Quick Sort):
def quick_sort(arr):if len(arr) <= 1:return arrpivot = 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]
result = quick_sort(arr)
print("快速排序结果:", result)
  1. 堆排序(Heap Sort):
def heapify(arr, n, i):largest = ileft = 2 * i + 1right = 2 * i + 2if left < n and arr[i] < arr[left]:largest = leftif right < n and arr[largest] < arr[right]:largest = rightif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n = len(arr)for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)for i in range(n - 1, 0, -1):arr[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)# 示例
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("堆排序结果:", arr)
  1. 归并排序(Merge Sort):
def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]merge_sort(left_half)merge_sort(right_half)i = j = k = 0while i < len(left_half) and j < len(right_half):if left_half[i] < right_half[j]:arr[k] = left_half[i]i += 1else:arr[k] = right_half[j]j += 1k += 1while i < len(left_half):arr[k] = left_half[i]i += 1k += 1while j < len(right_half):arr[k] = right_half[j]j += 1k += 1# 示例
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print("归并排序结果:", arr)
  1. 计数排序(Counting Sort):
def counting_sort(arr):output = [0] * len(arr)count = [0] * (max(arr) + 1)for i in arr:count[i] += 1for i in range(1, len(count)):count[i] += count[i - 1]i = len(arr) - 1while i >= 0:output[count[arr[i]] - 1] = arr[i]count[arr[i]] -= 1i -= 1for i in range(len(arr)):arr[i] = output[i]# 示例
arr = [4, 2, 2, 8, 3, 3, 1]
counting_sort(arr)
print("计数排序结果:", arr)
  1. 基数排序(Radix Sort):
def counting_sort_for_radix(arr, exp):n = len(arr)output = [0] * ncount = [0] * 10for i in range(n):index = arr[i] // expcount[index % 10] += 1for i in range(1, 10):count[i] += count[i - 1]i = n - 1while i >= 0:index = arr[i] // expoutput[count[index % 10] - 1] = arr[i]count[index % 10] -= 1i -= 1for i in range(n):arr[i] = output[i]def radix_sort(arr):max_num = max(arr)exp = 1while max_num // exp > 0:counting_sort_for_radix(arr, exp)exp *= 10# 示例
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("基数排序结果:", arr)

相关文章:

主流排序算法

冒泡排序&#xff08;Bubble Sort&#xff09;&#xff1a; 基本思想&#xff1a;通过比较相邻元素的大小&#xff0c;不断交换相邻元素的位置&#xff0c;使得较大的元素逐渐“浮”到数组的最后。时间复杂度&#xff1a;O(n^2)。 选择排序&#xff08;Selection Sort&#xf…...

MySql的使用方法

一.什么是MySql MySql是一种数据库管理系统&#xff0c;是用来存储数据的&#xff0c;可以有效的管理数据&#xff0c;数据库的存储介质为硬盘和内存。 和文件相比&#xff0c;它具有以下优点&#xff1a; 文件存储数据是不安全的&#xff0c;且不方便数据的查找和管理&#xf…...

C#,数据检索算法之三元搜索(Ternary Search)的源代码

数据检索算法是指从数据集合&#xff08;数组、表、哈希表等&#xff09;中检索指定的数据项。 数据检索算法是所有算法的基础算法之一。 本文发布 三元搜索&#xff08;Ternary Search&#xff09;的源代码。 1 文本格式 using System; namespace Legalsoft.Truffer.Algo…...

windbg:常用指令

windbg 调试 参考文档 1、viewing-and-editing-global-variables-in-windbg WinDBG 常用调试命令 加载符号 .sympath // 查看当前符号查找路径 .sympath c:\symbols // 将符号查找路径设为&#xff1a;c:\symbols .sympath c:\symbols // 将c:\symbols添加…...

23. 集合类

集合 1. 概述2. 分类2.1 单列集合&#xff08;Collection&#xff09;2.2 双列集合&#xff08;Map&#xff09; 单列集合 Collection、List、Set、ArrayList、LinkedList’、Vector、HashSet、TreeSet、LinkedHashSet双列集合 Map、HashTable、HashMap、TreeMap、Properties、…...

OpenAI平台:引领人工智能的创新与应用

在当今迅速发展的技术世界中&#xff0c;OpenAI已成为人工智能&#xff08;AI&#xff09;研究和应用的先驱。作为一个致力于确保人工智能的安全和广泛受益的组织&#xff0c;OpenAI通过其平台提供了一系列强大的工具和API&#xff0c;这些工具和API正在重塑我们与技术的互动方…...

redis原理(五)Lua语言

一、介绍&#xff1a; 1、背景&#xff1a; 在 Redis 的 2.6 以上版本中&#xff0c;除了可以使用命令外&#xff0c;还可以使用 Lua 语言操作 Redis。 Redis 命令的计算能力并不算很强大&#xff0c;而使用 Lua 语言则在很大程度上弥补了 Redis 的这个不足。 2、特点&#…...

SOHO外贸怎么建网站?做海洋建站的步骤?

SOHO外贸如何做跨境独立站&#xff1f;搭建外贸自建站的策略&#xff1f; 一位成功的SOHO外贸从业者不仅需要精湛的贸易技能&#xff0c;还需要一个优质的网站来展示产品、与客户互动&#xff0c;并建立强大的在线品牌形象。海洋建站将探讨在SOHO外贸领域如何建立一个成功的网…...

[论文阅读] |RAG评估_Retrieval-Augmented Generation Benchmark

写在前面 检索增强能够有效缓解大模型存在幻觉和知识时效性不足的问题&#xff0c;RAG通常包括文本切分、向量化入库、检索召回和答案生成等基本步骤。近期组里正在探索如何对RAG完整链路进行评估&#xff0c;辅助阶段性优化工作。上周先对评估综述进行了初步的扫描&#xff0…...

【Linux】动态库和静态库——动态库和静态库的打包和使用、gcc编译、拷贝到系统默认的路径、建立软连接

文章目录 动态库和静态库1.静态库和动态库的介绍2.静态库的打包和使用2.1生成静态库2.2使用静态库的三种方式2.2.1gcc编译2.2.2拷贝到系统默认的路径2.2.3建立软连接 3.动态库的打包和使用3.1生成动态库3.2使用动态库3.3解决加载不到动态库的方法 动态库和静态库 1.静态库和动…...

【Redis】Redis有哪些适合的场景

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;Redis ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 &#xff08;1&#xff09;会话缓存&#xff08;Session Cache&#xff09; &#xff08;2&#xff09;全页缓存&#xff08;FPC…...

uniapp上传音频文件到服务器

视频教程地址&#xff1a; 【uniapp录音上传组件&#xff0c;将录音上传到django服务器】 https://www.bilibili.com/video/BV1wi4y1p7FL/?share_sourcecopy_web&vd_sourcee66c0e33402a09ca7ae1f0ed3d5ecf7c uniapp 录制音频文件上传到django服务器保存到服务器 &#xf…...

C#-正则表达式

1.C#功能点&#xff1a; 验证格式&#xff1a;通过正则表达式&#xff0c;我们可以检查一个字符串是否符合特定的格式要求&#xff0c;例如验证邮箱、电话号码、身份证号码等。 查找和提取&#xff1a;我们可以使用正则表达式来查找字符串中符合特定模式的部分&#xff0c;并将…...

【word】论文、报告:①插入图表题注,交叉引用②快速插入图表目录③删改后一键更新

【word】①插入图表题注&#xff0c;②删改后一键更新 写在最前面插入题注交叉引用修改插入题注的文字格式快速插入图表目录 插入题注后有删改&#xff0c;实现编号一键更新 &#x1f308;你好呀&#xff01;我是 是Yu欸 &#x1f30c; 2024每日百字篆刻时光&#xff0c;感谢你…...

Spring Security 的TokenStore三种实现方式

博主介绍&#xff1a;✌专注于前后端领域开发的优质创作者、秉着互联网精神开源贡献精神&#xff0c;答疑解惑、坚持优质作品共享。本人是掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战&#xff0c;深受全网粉丝喜爱与支持✌有需要可以联系作者我哦&…...

微信小程序 图片自适应高度 宽度 完美适配原生或者uniapp

-- - - - 查了一下百度看到网上图片高度自适应的解决方案 基本是靠JS获取图片的宽度进行按比例计算得出图片高度。 不是很符合我的需求/ 于是我脑瓜子一转 想到一种新的解决方案 不用JS计算也能完美解决。 我写了一个组件&#xff0c;直接导入可以使用。 - - - 1.新…...

Go语言基础之反射

1.变量的内在机制 Go语言中的变量是分为两部分的: 类型信息&#xff1a;预先定义好的元信息。值信息&#xff1a;程序运行过程中可动态变化的。 2.反射介绍 反射是指在程序运行期间对程序本身进行访问和修改的能力。程序在编译时&#xff0c;变量被转换为内存地址&#xff…...

MySQL十部曲之六:数据操作语句(DML)

文章目录 前言语法约定DELETEINSERTSELECT查询列表SELECT 选项子句FROMWHEREORDER BYGROUP BYHAVINGWINDOWLIMITFOR SELECT ... INTO连接查询CROSS JOIN和INNER JOINON和USINGOUTER JOINNATURE JOIN 子查询标量子查询使用子查询进行比较带有ANY、IN或SOME的子查询带有ALL的子查…...

Quartus生成烧录到FPGA板载Flash的jic文件

简要说明&#xff1a; Altera的FPGA芯片有两种基本分类&#xff0c;一类是纯FPGA&#xff0c;另一类是FPGASoc&#xff08;System on chip)&#xff0c;也就是FPGAHPS&#xff08;Hard Processor System&#xff0c;硬核处理器&#xff09;&#xff0c;对应两种Flash烧录方式&a…...

CSS 多色正方形上升

<template><view class="loop cubes"><view class="item cubes"></view> <!-- 方块1 --><view class="item cubes"></view> <!-- 方块2 --><view class="item cubes"></vie…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

在四层代理中还原真实客户端ngx_stream_realip_module

一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡&#xff08;如 HAProxy、AWS NLB、阿里 SLB&#xff09;发起上游连接时&#xff0c;将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后&#xff0c;ngx_stream_realip_module 从中提取原始信息…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...