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

【算法与数据结构】--高级算法和数据结构--排序和搜索

一、常见排序算法

以下是一些常见的排序算法,包括冒泡排序、选择排序、插入排序、快速排序和归并排序。每种排序算法的讲解以及附带C#和Java示例:

1.1 冒泡排序 (Bubble Sort)

讲解: 冒泡排序是一种简单的比较排序算法。它多次遍历待排序的元素列表,比较每一对相邻元素,如果它们的顺序不正确,就交换它们,直到没有需要交换的元素。
C# 示例:

using System;public class BubbleSort
{public static void Sort(int[] arr){int n = arr.Length;for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){// 交换 arr[j] 和 arr[j+1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}public static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };Sort(arr);Console.WriteLine("Sorted array:");foreach (int num in arr){Console.Write(num + " ");}}
}

Java 示例:

public class BubbleSort {public static void sort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {// 交换 arr[j] 和 arr[j+1]int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}public static void main(String[] args) {int[] arr = { 64, 34, 25, 12, 22, 11, 90 };sort(arr);System.out.println("Sorted array:");for (int num : arr) {System.out.print(num + " ");}}
}
1.2 选择排序 (Selection Sort)

讲解: 选择排序是一种简单的排序算法。它将待排序列表分为已排序和未排序两部分,然后从未排序部分选择最小的元素,与已排序部分的最后一个元素交换位置,直到整个列表排序完成。
C# 示例:

using System;public class SelectionSort
{public static void Sort(int[] arr){int n = arr.Length;for (int i = 0; i < n - 1; i++){int minIndex = i;for (int j = i + 1; j < n; j++){if (arr[j] < arr[minIndex]){minIndex = j;}}// 交换 arr[i] 和 arr[minIndex]int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}public static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };Sort(arr);Console.WriteLine("Sorted array:");foreach (int num in arr){Console.Write(num + " ");}}
}

Java 示例:

public class SelectionSort {public static void sort(int[] arr) {int n = arr.length;for (int i = 0; i < n - 1; i++) {int minIndex = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 交换 arr[i] 和 arr[minIndex]int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}public static void main(String[] args) {int[] arr = { 64, 34, 25, 12, 22, 11, 90 };sort(arr);System.out.println("Sorted array:");for (int num : arr) {System.out.print(num + " ");}}
}

1.3 插入排序 (Insertion Sort)

讲解: 插入排序是一种简单的排序算法。它将待排序列表分为已排序和未排序两部分,然后逐个将未排序部分的元素插入到已排序部分的合适位置,直到整个列表排序完成。
C# 示例:

using System;public class InsertionSort
{public static void Sort(int[] arr){int n = arr.Length;for (int i = 1; i < n; i++){int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key){arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}}public static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };Sort(arr);Console.WriteLine("Sorted array:");foreach (int num in arr){Console.Write(num + " ");}}
}

Java 示例:

public class InsertionSort {public static void sort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}arr[j + 1] = key;}}public static void main(String[] args) {int[] arr = { 64, 34, 25, 12, 22, 11, 90 };sort(arr);System.out.println("Sorted array:");for (int num : arr) {System.out.print(num + " ");}}
}

1.4 快速排序 (Quick Sort)

讲解: 快速排序是一种高效的分治排序算法。它选择一个基准元素,将列表分为小于基准和大于基准的两部分,然后递归地对这两部分进行排序。
C# 示例:

using System;public class QuickSort
{public static void Sort(int[] arr, int low, int high){if (low < high){int pivot = Partition(arr, low, high);Sort(arr, low, pivot - 1);Sort(arr, pivot + 1, high);}}public static int Partition(int[] arr, int low, int high){int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++){if (arr[j] < pivot){i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp2 = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp2;return i + 1;}public static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };int n = arr.Length;Sort(arr, 0, n - 1);Console.WriteLine("Sorted array:");foreach (int num in arr){Console.Write(num + " ");}}
}

Java 示例:

public class QuickSort {public static void sort(int[] arr, int low, int high) {if (low < high) {int pivot = partition(arr, low, high);sort(arr, low, pivot - 1);sort(arr, pivot + 1, high);}}public static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp2 = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp2;return i + 1;}public static void main(String[] args) {int[] arr = { 64, 34, 25, 12, 22, 11, 90 };int n = arr.length;sort(arr, 0, n - 1);System.out.println("Sorted array:");for (int num : arr) {System.out.print(num + " ");}}
}

1.5 归并排序 (Merge Sort)

讲解: 归并排序是一种高效的分治排序算法。它将列表递归地分为较小的子列表,然后合并这些子列表以获得排序的结果。
C# 示例:

using System;public class MergeSort
{public static void Sort(int[] arr){int n = arr.Length;if (n > 1){int mid = n / 2;int[] left = new int[mid];int[] right = new int[n - mid];for (int i = 0; i < mid; i++){left[i] = arr[i];}for (int i = mid; i < n; i++){right[i - mid] = arr[i];}Sort(left);Sort(right);int i = 0, j = 0, k = 0;while (i < left.Length && j < right.Length){if (left[i] < right[j]){arr[k] = left[i];i++;}else{arr[k] = right[j];j++;}k++;}while (i < left.Length){arr[k] = left[i];i++;k++;}while (j < right.Length){arr[k] = right[j];j++;k++;}}}public static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };Sort(arr);Console.WriteLine("Sorted array:");foreach (int num in arr){Console.Write(num + " ");}}
}

Java 示例:

public class MergeSort {public static void sort(int[] arr) {int n = arr.length;if (n > 1) {int mid = n / 2;int[] left = new int[mid];int[] right = new int[n - mid];for (int i = 0; i < mid; i++) {left[i] = arr[i];}for (int i = mid; i < n; i++) {right[i - mid] = arr[i];}sort(left);sort(right);int i = 0, j = 0, k = 0;while (i < left.length && j < right.length) {if (left[i] < right[j]) {arr[k] = left[i];i++;} else {arr[k] = right[j];j++;}k++;}while (i < left.length) {arr[k] = left[i];i++;k++;}while (j < right.length) {arr[k] = right[j];j++;k++;}}}public static void main(String[] args) {int[] arr = { 64, 34, 25, 12, 22, 11, 90 };sort(arr);System.out.println("Sorted array:");for (int num : arr) {System.out.print(num + " ");}}
}

这些是常见的排序算法,每种排序算法都有其独特的方式来对数据进行排序。无论使用C#还是Java,你可以根据需要选择合适的算法来排序你的数据。

二、搜索算法

以下是一些常见的搜索算法,包括线性搜索、二分搜索和哈希表查找。每种搜索算法的讲解以及附带C#和Java示例:

2.1 线性搜索 (Linear Search)

讲解: 线性搜索是一种简单的搜索算法,它从列表的开头开始逐个检查元素,直到找到目标元素或搜索整个列表。
C# 示例:

using System;public class LinearSearch
{public static int Search(int[] arr, int target){for (int i = 0; i < arr.Length; i++){if (arr[i] == target){return i; // 返回目标元素的索引}}return -1; // 未找到目标元素}public static void Main(){int[] arr = { 64, 34, 25, 12, 22, 11, 90 };int target = 22;int result = Search(arr, target);if (result != -1){Console.WriteLine("Element found at index: " + result);}else{Console.WriteLine("Element not found in the array.");}}
}

Java 示例:

public class LinearSearch {public static int search(int[] arr, int target) {for (int i = 0; i < arr.length; i++) {if (arr[i] == target) {return i; // 返回目标元素的索引}}return -1; // 未找到目标元素}public static void main(String[] args) {int[] arr = { 64, 34, 25, 12, 22, 11, 90 };int target = 22;int result = search(arr, target);if (result != -1) {System.out.println("Element found at index: " + result);} else {System.out.println("Element not found in the array.");}}
}
2.2 二分搜索 (Binary Search)

讲解: 二分搜索是一种高效的搜索算法,前提是待搜索的列表必须是已排序的。它通过将目标值与中间元素进行比较,然后排除一半的列表,继续在剩余的一半中搜索,以此类推,直到找到目标元素或确定它不存在。
C# 示例:

using System;public class BinarySearch
{public static int Search(int[] arr, int target){int left = 0;int right = arr.Length - 1;while (left <= right){int mid = left + (right - left) / 2;if (arr[mid] == target){return mid; // 返回目标元素的索引}if (arr[mid] < target){left = mid + 1;}else{right = mid - 1;}}return -1; // 未找到目标元素}public static void Main(){int[] arr = { 11, 12, 22, 25, 34, 64, 90 };int target = 22;int result = Search(arr, target);if (result != -1){Console.WriteLine("Element found at index: " + result);}else{Console.WriteLine("Element not found in the array.");}}
}

Java 示例:

public class BinarySearch {public static int search(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid; // 返回目标元素的索引}if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1; // 未找到目标元素}public static void main(String[] args) {int[] arr = { 11, 12, 22, 25, 34, 64, 90 };int target = 22;int result = search(arr, target);if (result != -1) {System.out.println("Element found at index: " + result);} else {System.out.println("Element not found in the array.");}}
}

2.3 哈希表查找 (Hash Table Lookup)

讲解: 哈希表查找是一种使用哈希函数将键映射到值的数据结构。它允许快速查找键对应的值,通常具有恒定的查找时间。
C# 示例:

using System;
using System.Collections.Generic;public class HashTableLookup
{public static void Main(){Dictionary<string, int> phonebook = new Dictionary<string, int>();// 添加元素到哈希表phonebook["Alice"] = 123456789;phonebook["Bob"] = 987654321;phonebook["Charlie"] = 555555555;// 查找元素if (phonebook.ContainsKey("Bob")){int phoneNumber = phonebook["Bob"];Console.WriteLine("Bob's phone number is: " + phoneNumber);}else{Console.WriteLine("Bob's phone number not found.");}}
}

Java 示例:

import java.util.HashMap;
import java.util.Map;public class HashMapLookup {public static void main(String[] args) {Map<String, Integer> phonebook = new HashMap<>();// 添加元素到哈希表phonebook.put("Alice", 123456789);phonebook.put("Bob", 987654321);phonebook.put("Charlie", 555555555);// 查找元素if (phonebook.containsKey("Bob")) {int phoneNumber = phonebook.get("Bob");System.out.println("Bob's phone number is: " + phoneNumber);} else {System.out.println("Bob's phone number not found.");}}
}

这些是常见的搜索算法,每种算法都适用于不同的情况。线性搜索适用于未排序的列表,二分搜索适用于已排序的列表,而哈希表查找适用于键值对的存储和检索。你可以根据你的需求选择适当的搜索算法。

三、总结

本文介绍了常见的排序算法和搜索算法。排序算法包括冒泡排序、选择排序、插入排序、快速排序和归并排序,它们分别用于按不同方式对数据进行排序。每个算法都伴随着C#和Java的示例代码。搜索算法包括线性搜索、二分搜索和哈希表查找,用于在数据集中查找特定元素。这些算法有各自的优点和适用场景,可以根据需求选择合适的算法。

相关文章:

【算法与数据结构】--高级算法和数据结构--排序和搜索

一、常见排序算法 以下是一些常见的排序算法&#xff0c;包括冒泡排序、选择排序、插入排序、快速排序和归并排序。每种排序算法的讲解以及附带C#和Java示例&#xff1a; 1.1 冒泡排序 (Bubble Sort) 讲解&#xff1a; 冒泡排序是一种简单的比较排序算法。它多次遍历待排序的…...

【Java】jvm 元空间、常量池(了解)

JDK1.8 以前的 HotSpot JVM 有方法区&#xff0c;也叫永久代&#xff08;permanent generation&#xff09;方法区用于存放已被虚拟机加载的类信息&#xff0c;常量、静态遍历&#xff0c;即编译器编译后的代码JDK1.7 开始了方法区的部分移除&#xff1a;符号引用&#xff08;S…...

Spring Boot自动加载

问&#xff1a;自动装配如何实现的&#xff1f; 答&#xff1a;简单来说就是自动去把第三方组件的Bean装载到IOC容器中&#xff0c;不需要开发人员再去写Bean相关的配置&#xff0c;在springboot应用里面只需要在启动类上去加上SpringBootApplication注解&#xff0c;就可以去实…...

MPNN 模型:GNN 传递规则的实现

首先&#xff0c;假如我们定义一个极简的传递规则 A是邻接矩阵&#xff0c;X是特征矩阵&#xff0c; 其物理意义就是 通过矩阵乘法操作&#xff0c;批量把图中的相邻节点汇聚到当前节点。 但是由于A的对角线都是 0.因此自身的节点特征会被过滤掉。 图神经网络的核心是 吸周围…...

Flink kafka 数据汇不指定分区器导致的问题

背景 在flink中&#xff0c;我们经常使用kafka作为flink的数据汇&#xff0c;也就是目标数据的存储地&#xff0c;然而当我们使用FlinkKafkaProducer作为数据汇连接器时&#xff0c;我们需要注意一些注意事项&#xff0c;本文就来记录一下 使用kafka数据汇连接器 首先我们看…...

【软考】14.1 面向对象基本概念/分析设计测试

《面向对象开发》 对象 现实生活中实际存在的一个实体&#xff1b;构成系统的一个基本单位由对象名、属性和方法组成 类 实体的形式化描述&#xff1b;对象是类的实例&#xff0c;类是对象的模板可分为&#xff1a;实体类&#xff1a;现实世界中真实的实体接口类&#xff08;边…...

MFC-对话框

目录 1、模态和非模态对话框&#xff1a; &#xff08;1&#xff09;、对话框的创建 &#xff08;2&#xff09;、更改默认的对话框名称 &#xff08;3&#xff09;、创建模态对话框 1&#xff09;、创建按钮跳转的界面 2&#xff09;、在跳转的窗口添加类 3&#xff0…...

Essential Steps in Natural Language Processing (NLP)

&#x1f497;&#x1f497;&#x1f497;欢迎来到我的博客&#xff0c;你将找到有关如何使用技术解决问题的文章&#xff0c;也会找到某个技术的学习路线。无论你是何种职业&#xff0c;我都希望我的博客对你有所帮助。最后不要忘记订阅我的博客以获取最新文章&#xff0c;也欢…...

Flink中KeyBy、分区、分组的正确理解

1.Flink中的KeyBy 在Flink中&#xff0c;KeyBy作为我们常用的一个聚合类型算子&#xff0c;它可以按照相同的Key对数据进行重新分区&#xff0c;分区之后分配到对应的子任务当中去。 源码解析 keyBy 得到的结果将不再是 DataStream&#xff0c;而是会将 DataStream 转换为 Key…...

QT6集成CEF3--01 准备工作

QT6集成CEF3--01 准备工作 一、所有使用到的工具软件清单:二、准备工作三、cefclient示例程序四、特别注意 一、所有使用到的工具软件清单: CEF 二进制发行包 cef_binary_117.2.5gda4c36achromium-117.0.5938.152_windows64.tar.bz2 CMake 编译工具 cmake-3.22.6-windows-x86_…...

随机误差理论与测量

文章目录 第1节 随机误差的性质和特点第2节 随机误差的数字特性标准差的估计 第3节 单次测量结果的精度指标第4节 多次测量结果的精度指标算数平均值的分布特性与标准差算数平均值的置信度算数平均值的精度指标&#xff08;常用的有4个) 第5节 非等精度测量 第1节 随机误差的性…...

树莓派4b配置通过smbus2使用LCD灯

出现报错&#xff1a; FileNotFoundError: [Errno 2] No such file or directory: ‘/dev/i2c-1’ 则说明没有打开I2C&#xff0c;可通过如下步骤进行设置 1、打开树莓派配置 sudo raspi-config2、进入Interface Options&#xff0c;配置I2C允许 目前很多python3版本已经不…...

UPS 原理和故障案例分享

摘要:不间断电源UPS (Uninterruptible Power System)&#xff0c;主要是由整流器、 逆变器、静态旁路和储能装置等组成;具备高可靠性、高可用性和高质量的独立 电源。通过对收集的 UPS 故障案例进行分析&#xff0c;从施工&#xff0c;调试和运行三个方面筛选 出四个故障案例与…...

Stream流中的 max()和 sorted()方法

需求&#xff1a;某个公司的开发部门&#xff0c;分为开发 一部 和 二部 &#xff0c;现在需要进行年中数据结算。分析&#xff1a; 员工信息至少包含了&#xff08;名称、性别、工资、奖金、处罚记录&#xff09;开发一部有 4 个员工、开发二部有 5 名员工分别筛选出 2 个部门…...

云上攻防-云原生篇Docker安全权限环境检测容器逃逸特权模式危险挂载

文章目录 前言1、Docker是干嘛的&#xff1f;2、Docker对于渗透测试影响&#xff1f;3、Docker渗透测试点有那些&#xff1f;4、前渗透-判断在Docker中方式一&#xff1a;查询cgroup信息方式二&#xff1a;检查/.dockerenv文件方式三&#xff1a;检查mount信息方式四&#xff1…...

PDE数值解中,为什么要引入弱解(weak solution)的概念?

See https://www.zhihu.com/question/24243246?utm_sourceqq&utm_mediumsocial&utm_oi1315073218793488384...

使用pdfjs实现在线预览pdf

在工作中可能会遇到前端展示pdf文件进行预览并提供下载的需求场景,例如操作指引,这个时候需要寻找一款实现该功能的插件,以pdjjs举例子 1. 安装pdf.js npm install pdfjs-dist2. 引入pdf.js import pdfjsLib from pdfjs-dist3.加载pdf文件流 这个地方区分是请求后端接口还是…...

汇编语言基础

引言 汇编语言是直接在硬件之上工作的编程语言&#xff0c;首先要了解硬件系统的结构&#xff0c;才能有效的应用汇编语言对其编程。汇编课程的研究重点放在如何利用硬件系统的编程结构和指令集有效灵活的控制系统进行工作。 基础知识 1.1机器语言 机器语言是机器指令的集合…...

格式工厂怎么把两个视频合并在一起

免费的工具谁不喜欢呢&#xff0c;今天为大家介绍的是格式工厂这款多功能视频转换软件&#xff0c;然而今天主要为大家介绍的是格式工厂的视频合并功能。 是的&#xff0c;你没有听错&#xff0c;格式工厂除了转换之外&#xff0c;还可以视频合适、视频剪辑、视频分割、去水印…...

2.MySQL表的操作

个人主页&#xff1a;Lei宝啊 愿所有美好如期而遇 表的操作 (1)表的创建 CREATE TABLE table_name ( field1 datatype, field2 datatype, field3 datatype ) character set 字符集 collate 校验规则 engine 存储引擎; 存储引擎的不同会导致创建表的文件不同。 换个引擎。 t…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...