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

算法.1-三大排序算法-对数器-二分

三大排序算法&对数器

1.选择排序

Java版

package class01;import java.util.Arrays;public class Code01_SelectionSort {public static void selectionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}// 0 ~ N-1  找到最小值,在哪,放到0位置上// 1 ~ n-1  找到最小值,在哪,放到1 位置上// 2 ~ n-1  找到最小值,在哪,放到2 位置上for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标 minIndex = arr[j] < arr[minIndex] ? j : minIndex;}swap(arr, i, minIndex);}}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {// Math.random()   [0,1)  // Math.random() * N  [0,N)// (int)(Math.random() * N)  [0, N-1]int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {// [-? , +?]arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr == null) {return null;}int[] res = new int[arr.length];for (int i = 0; i < arr.length; i++) {res[i] = arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {return false;}if (arr1 == null && arr2 == null) {return true;}if (arr1.length != arr2.length) {return false;}for (int i = 0; i < arr1.length; i++) {if (arr1[i] != arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr == null) {return;}for (int i = 0; i < arr.length; i++) {System.out.print(arr[i] + " ");}System.out.println();}// for testpublic static void main(String[] args) {int testTime = 500000;int maxSize = 100;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr1 = generateRandomArray(maxSize, maxValue);int[] arr2 = copyArray(arr1);selectionSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}System.out.println(succeed ? "Nice!" : "Wrong!");int[] arr = generateRandomArray(maxSize, maxValue);printArray(arr);selectionSort(arr);printArray(arr);}}

C++ 

#include <iostream>
#include <algorithm>
#include <vector>using namespace std;void selectionSort(vector<int>& arr) {if (arr.size() < 2) {return;}for (int i = 0; i < arr.size() - 1; i++) {int minIndex = i;for (int j = i + 1; j < arr.size(); j++) { // i ~ N-1 上找最小值的下标 minIndex = arr[j] < arr[minIndex] ? j : minIndex;}swap(arr[i], arr[minIndex]);}
}// for test
void comparator(vector<int>& arr) {sort(arr.begin(), arr.end());
}// for test
vector<int> generateRandomArray(int maxSize, int maxValue) {vector<int> arr((size_t)((maxSize + 1) * (double)rand() / RAND_MAX));for (int i = 0; i < arr.size(); i++) {arr[i] = (int)((maxValue + 1) * (double)rand() / RAND_MAX) - (int)(maxValue * (double)rand() / RAND_MAX);}return arr;
}// for test
vector<int> copyArray(const vector<int>& arr) {if (arr.empty()) {return {};}vector<int> res(arr.size());for (size_t i = 0; i < arr.size(); i++) {res[i] = arr[i];}return res;
}// for test
bool isEqual(const vector<int>& arr1, const vector<int>& arr2) {if ((arr1.empty() && !arr2.empty()) || (!arr1.empty() && arr2.empty())) {return false;}if (arr1.empty() && arr2.empty()) {return true;}if (arr1.size() != arr2.size()) {return false;}for (size_t i = 0; i < arr1.size(); i++) {if (arr1[i] != arr2[i]) {return false;}}return true;
}// for test
void printArray(const vector<int>& arr) {if (arr.empty()) {return;}for (const auto& val : arr) {cout << val << " ";}cout << endl;
}// for test
int main() {srand(time(nullptr));int testTime = 500000;int maxSize = 100;int maxValue = 100;bool succeed = true;for (int i = 0; i < testTime; i++) {vector<int> arr1 = generateRandomArray(maxSize, maxValue);vector<int> arr2 = copyArray(arr1);selectionSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed = false;printArray(arr1);printArray(arr2);break;}}cout << (succeed ? "Nice!" : "Wrong!") << endl;vector<int> arr = generateRandomArray(maxSize, maxValue);printArray(arr);selectionSort(arr);printArray(arr);return 0;
}

对数器

1,你想要测的方法a(最优解)

2,实现复杂度不好但是容易实现的方法b(暴力解)

3,实现一个随机样本产生器(长度也随机、值也随机)

4,把方法a和方法b跑相同的输入样本,看看得到的结果是否一样

5,如果有一个随机样本使得比对结果不一致,打印这个出错的样本进行人工干预,改对方法a和方法b

6,当样本数量很多时比对测试依然正确,可以确定方法a(最优解)已经正确。

关键是第5步,找到一个数据量小的错误样本,便于你去带入debug

然后把错误例子带入代码一步一步排查

Print大法、断点技术都可以

对数器的门槛其实是比较高的,因为往往需要在两种不同思路下实现功能相同的两个方法,暴力一个、想象中的最优解是另一个。

以后的很多题目都会用到对数器,几乎可以验证任何方法,尤其在验证贪心、观察规律方面很有用

到时候会丰富很多对数器的实战用法,这里只是一个简单易懂的示例

2.冒泡排序

public class Code02_BubbleSort {public static void bubbleSort(int[] arr) {if (arr == null || arr.length < 2) {return;}// 0 ~ N-1// 0 ~ N-2// 0 ~ N-3for (int e = arr.length - 1; e > 0; e--) { // 0 ~ efor (int i = 0; i < e; i++) {if (arr[i] > arr[i + 1]) {swap(arr, i, i + 1);}}}}// 交换arr的i和j位置上的值public static void swap(int[] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}

3.插入排序(类似打扑克时摸到牌插牌的感觉)

public static void insertionSort(int[] arr) {if (arr == null || arr.length < 2) {return;}// 不只1个数for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {swap(arr, j, j + 1);}}}// i和j是一个位置的话,会出错public static void swap(int[] arr, int i, int j) {arr[i] = arr[i] ^ arr[j];arr[j] = arr[i] ^ arr[j];arr[i] = arr[i] ^ arr[j];}

二分

1.在有序数组中确定num存在还是不存在

指针来到中间位置,中间值比n大意味着n-n-1位置都不可能,右指针来到mid-1,在左右之间再次取中间值递归

package class01;import java.util.Arrays;public class Code04_BSExist {public static boolean exist(int[] sortedArr, int num) {if (sortedArr == null || sortedArr.length == 0) {return false;}int L = 0;int R = sortedArr.length - 1;int mid = 0;// L..Rwhile (L < R) { // L..R 至少两个数的时候mid = L + ((R - L) >> 1);if (sortedArr[mid] == num) {return true;} else if (sortedArr[mid] > num) {R = mid - 1;} else {L = mid + 1;}}return sortedArr[L] == num;}// for testpublic static boolean test(int[] sortedArr, int num) {for(int cur : sortedArr) {if(cur == num) {return true;}}return false;}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr = new int[(int) ((maxSize + 1) * Math.random())];for (int i = 0; i < arr.length; i++) {arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}public static void main(String[] args) {int testTime = 500000;int maxSize = 10;int maxValue = 100;boolean succeed = true;for (int i = 0; i < testTime; i++) {int[] arr = generateRandomArray(maxSize, maxValue);Arrays.sort(arr);int value = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());if (test(arr, value) != exist(arr, value)) {succeed = false;break;}}System.out.println(succeed ? "Nice!" : "fuck!");}}

2.在有序数组中找>=num的最左位置

/ 在arr上,找满足>=value的最左位置public static int nearestIndex(int[] arr, int value) {int L = 0;int R = arr.length - 1;int index = -1; // 记录最左的对号while (L <= R) { // 至少一个数的时候int mid = L + ((R - L) >> 1);if (arr[mid] >= value) {index = mid;R = mid - 1;} else {L = mid + 1;}}return index;}

3.最右 

	// 在arr上,找满足<=value的最右位置public static int nearestIndex(int[] arr, int value) {int L = 0;int R = arr.length - 1;int index = -1; // 记录最右的对号while (L <= R) {int mid = L + ((R - L) >> 1);if (arr[mid] <= value) {index = mid;L = mid + 1;} else {R = mid - 1;}}return index;}

4.寻找最小值,二分搜索不一定发生在有序数组上, 

package class01;public class Code06_BSAwesome {public static int getLessIndex(int[] arr) {if (arr == null || arr.length == 0) {return -1; // no exist}if (arr.length == 1 || arr[0] < arr[1]) {return 0;}if (arr[arr.length - 1] < arr[arr.length - 2]) {return arr.length - 1;}int left = 1;int right = arr.length - 2;int mid = 0;while (left < right) {mid = (left + right) / 2;if (arr[mid] > arr[mid - 1]) {right = mid - 1;} else if (arr[mid] > arr[mid + 1]) {left = mid + 1;} else {return mid;}}return left;}}

相关文章:

算法.1-三大排序算法-对数器-二分

三大排序算法&对数器 1.选择排序 Java版 package class01;import java.util.Arrays;public class Code01_SelectionSort {public static void selectionSort(int[] arr) {if (arr null || arr.length < 2) {return;}// 0 ~ N-1 找到最小值&#xff0c;在哪&#xf…...

Midjourney新功能介绍:风格参考(Style References)详解

引言 对于追求创意和一致性的艺术家和设计师们来说&#xff0c;Midjourney的最新功能——风格参考&#xff08;Style References&#xff09;&#xff0c;无疑是一个激动人心的消息。这项测试算法的发布&#xff0c;让我们得以通过简单的URL引用&#xff0c;将特定的风格应用于…...

C++ 11/14/17 智能指针

1. 简介 为了更加容易&#xff08;更加安全&#xff09;的使用动态内存&#xff0c;引入了智能指针的概念。智能指针的行为类似常规指针&#xff0c;重要的区别是它负责自动释放所指向的对象。 标准库提供的两种智能指针的区别在于管理底层指针的方法不同&#xff1a;shared_p…...

C++入门【37-C++ 拷贝构造函数】

拷贝构造函数是一种特殊的构造函数&#xff0c;它在创建对象时&#xff0c;是使用同一类中之前创建的对象来初始化新创建的对象。拷贝构造函数通常用于&#xff1a; 通过使用另一个同类型的对象来初始化新创建的对象。复制对象把它作为参数传递给函数。复制对象&#xff0c;并…...

[UI5 常用控件] 06.Splitter,ResponsiveSplitter

文章目录 前言1. Splitter1.1 属性 2. ResponsiveSplitter 前言 本章节记录常用控件Splitter,ResponsiveSplitter。主要功能是分割画面布局。 其路径分别是&#xff1a; sap.ui.layout.Splittersap.ui.layout.ResponsiveSplitter 1. Splitter 1.1 属性 orientation &#x…...

C遗漏知识(个人向)

之前C语言遗漏的一些。 数据在内存中的存储 原码、反码、补码 整数的2进制表⽰⽅法有三种&#xff0c;即 原码、反码和补码 正整数的原、反、补码都相同。 负整数的三种表⽰⽅法各不相同。 原码&#xff1a;直接将数值按照正负数的形式翻译成⼆进制得到的就是原码。 反码&…...

ERR_SSL_VERSION_OR_CIPHER_MISMATCH

我在namesilo买的域名&#xff0c;coludflare做的解析&#xff0c;华为云的SSL&#xff0c;用宝塔部署的SSL&#xff0c;访问https报错&#xff0c;http却正常&#xff1a; 报错&#xff1a;此网站无法提供安全连接www.hongkong.ioyunxin.top 使用了不受支持的协议。 ERR_SSL_…...

2.5作业

一 、程序阅读题 1、给出下面程序输出结果。 #include <iostream.h> class example {int a; public: example(int b5){ab;} void print(){aa1;cout <<a<<"";} void print()const {cout<<a<<endl;} }; void main() {example x; const e…...

linux系统lvs命令的使用

Lvs命令 LVS ipvsadm 命令的使用LVS-server安装lvs管理软件命令选项 LVS ipvsadm 命令的使用 LVS-server安装lvs管理软件 yum -y install ipvsadm 程序包&#xff1a;ipvsadm&#xff08;LVS管理工具&#xff09; 主程序&#xff1a;/usr/sbin/ipvsadm 规则保存工具&#x…...

PoEAA笔记-7.分布策略

本文摘抄自PoEAA&#xff0c;详细信息请阅读本书 7.1 分布对象的诱惑 透明性非常有用&#xff0c;但虽然有很多东西在分布对象中可以是透明的&#xff0c;但性能却不在其中&#xff0c;尽管上面的架构师是为了提高性能而使用分布组件的&#xff0c;但他的设计只会影响性能&…...

Spring Boot 整合 Redis 使用教程

作为开发者&#xff0c;相信大家都知道 Redis 的重要性。Redis 是使用 C 语言开发的一个高性能键值对数据库&#xff0c;是互联网技术领域使用最为广泛的存储中间件&#xff0c;它是「Remote Dictionary Service」的首字母缩写&#xff0c;也就是「远程字典服务」。 Redis 以超…...

用友U8 Cloud ReportDetailDataQuery SQL注入漏洞复现(QVD-2023-47860)

0x01 产品简介 用友U8 Cloud 提供企业级云ERP整体解决方案,全面支持多组织业务协同,实现企业互联网资源连接。 U8 Cloud 亦是亚太地区成长型企业最广泛采用的云解决方案。 0x02 漏洞概述 用友U8 cloud ReportDetailDataQuery 接口处存在SQL注入漏洞,攻击者未经授权可以访…...

docker镜像命令

docker images 列表本机上的镜像 - REPOSITORY&#xff1a;表示镜像的仓库源 - TAG&#xff1a;镜像的标签 - IMAGE ID&#xff1a;镜像 - ID CREATED&#xff1a;镜像创建时间 - SIZE&#xff1a;镜像大小 同一仓库源可以有多个 TAG&#xff0c;代表这个仓库源的不同个版本&am…...

通义千问上线春节新应用,AI帮你免费拍全家福

2月5日&#xff0c;春节将至年味渐浓&#xff0c;阿里云通义千问APP上线多项免费新应用&#xff0c;涵盖全家福、拜新年、万物成龙等图像生成的新玩法&#xff0c;共提供超300套照片模板&#xff0c;用户上传照片即可生成全家福、团圆照、拜年照、千里江山主题照&#xff1b;此…...

RabbitMQ 安装

下载erlang语言&#xff1a; erlang语言 下载RabbitMQ rabbitmq 安装erlang 1.以管理员身份安装erlang 2.弹出框选择next 3.选择安装路径&#xff0c;亦可以安装在默认路径 4.接下来一路点击下一步&#xff0c;无需任何修改&#xff0c;直到 install安装为止&#xff…...

如何让MySQL从部署到稳定运行?

如何让MySQL从部署到稳定运行&#xff1f; 1. 安装MySQL 8保姆级教程 2. 《从菜鸟到大师之路 MySQL 篇》 3. 关于MySQL的66个问题 4. MySQL 的学习资源史上最全 5. 掌握 SQL 这些核心知识点&#xff0c;出去吹牛逼再也不担心了...

go 内存二进制数据操作

go 内存二进制数据操作 go 内存二进制数据直接操作 以数字类型为例 int(linux/macos 为int32,windows 为int64). 如果不清楚可以使用unsafe.Sizeof函数来查看(函数出来的值*8就是int位数) 若不使用内存二进制数据操作&#xff0c;你需要在每次获取数字内容时调用binary.Big…...

Antd+React+react-resizable实现表格拖拽功能

1、先看效果 2、环境准备 在package.json 引入相关的依赖 "dependencies": {"antd": "^5.4.0","react-resizable": "^3.0.4",},"devDependencies": {"types/react": "^18.0.33","types…...

StringBuilder类常用方法(Java)

StringBuilder类常用方法 StringBuilder 是 Java 中常用的字符串缓冲区类&#xff0c;适用于频繁修改字符串的场景。 1. append(): 将指定字符串、字符、布尔值或其他数据类型的表示追加到字符串缓冲区的末尾。 StringBuilder sb new StringBuilder("Hello"); sb.…...

Iceberg从入门到精通系列之二十一:Spark集成Iceberg

Iceberg从入门到精通系列之二十一&#xff1a;Spark集成Iceberg 一、在 Spark 3 中使用 Iceberg二、添加目录三、创建表四、写五、读六、Catalogs七、目录配置八、使用目录九、替换会话目录十、使用目录特定的 Hadoop 配置值十一、加载自定义目录十二、SQL 扩展十三、运行时配置…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...