算法练习-排序(一)
算法练习-排序(一)
文章目录
- 算法练习-排序(一)
- 1 排序算法
- 1.1 冒泡排序
- 1.1.1代码
- 1.2插入排序
- 1.2.1代码
- 1.3 选择排序
- 1.3.1代码
- 1.4归并排序
- 1.4.1代码
- 1.5 快速排序
- 1.5.1 思路
- 1.5.2 代码
- 2 题目
- 2.1 特殊排序
- 2.1.1 题目
- 2.1.2 题解
- 2.2 数组中的第k个最大元素
- 2.2.1 题目
- 2.2.2 题解
- 2.3 对链表进行插入排序
- 2.3.1 题目
- 2.3.2 题解
- 2.4 排序预处理
- 2.4.1 题目
1 排序算法
1.1 冒泡排序
1.1.1代码
void bubbleSort(int[] a, int n) {if (n <= 1) return;for (int i = 0; i < n; i++) { // 第几趟冒泡boolean flag = false;for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {int tmp = a[j];a[j] = a[j + 1];a[j + 1] = tmp;flag = true; // 表示有数据交换}}if (!flag) break;}
}
1.2插入排序
1.2.1代码
public static void InsertSort(int[] a, int n) {if (n <= 1) return;for (int i = 1; i < n; i++) {int value = a[i];for (int j = i - 1; j >= 0; --j) {if (a[j] > value) {a[j + 1] = a[j];} else {break;}}a[j + 1] = value;}
}
1.3 选择排序
1.3.1代码
public void selectionSort(int[] a, int n) {if (n <= 1) return;for (int i = 0; i < n - 1; i++) {int minPos = i;for (int j = i; j < n; j++) {if (a[j] < a[minPos]) {minPos = j;}}int tmp = a[i];a[i] = a[minPos];a[minPos] = tmp;}
}
1.4归并排序
1.4.1代码
public void mergeSort(int[] a, int n) {mergeSort_r(a, 0, n - 1);
}private void mergeSort_r(int[] a, int p, int r) {if (p >= r) return;int q = p + (r - q) / 2;mergeSort_r(a, p, q);mergeSort_r(a, q + 1, r);merge(a, p, q, r);
}private void merge(int[] a, int p, int q, int r) {int i = p;int j = q + 1;int k = 0;int[] tmp = new int[r - q + 1];while (i <= q && j <= r) {if (a[i] <= a[j]) {tmp[k++] = a[i++];} else {tmp[k++] = a[j++];}}while (i <= q) {tmp[k++] = a[i++];}while (j <= r) {tmp[k++] = a[j++];}for (int i = 0; i < r - p; i++) {a[p + i] = tmp[i];}
}
1.5 快速排序
1.5.1 思路
先把数组中的一个数当作基准数,一般把数组最左面的数当作基准数,然后从两边进行检索。
先从右边检索比基准数小的,再从左边检索比基准数大的。
如果检索到了,就停下,交换这两个元素,然后继续检索
两个指针一旦相遇就停止检索,将基准数和相遇位置进行交换
1.5.2 代码
public static void quickSort(int[] a, int n) {quickSort_r(a, 0, n - 1);
}private void swap(int[] nums, int i ,int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;
}public static void quickSort_r(int[] arr, int left, int right) {if (left >= right) return;// 定义变量保存基准数int base = arr[left];// 定义变量i,指向最左边int i = left;// 定义变量j,指向最右边int j = right;// 当i和j不相遇时,在循环中进行检索while (i != j) {// 现由j从右往左检索while (arr[j] >= base && i < j) j--;while (arr[i] <= base && i < j) i++;// i 和 j都停下了,交换 i 和 j 位置的元素swap(arr, i, j);}swap(arr, left, i);quickSort_r(arr, left, i - 1);quickSort_r(arr, j + 1, right);}
public static void quickSort(int[] a, int n) {quickSort_r(a, 0, n - 1);
}private static void quickSort_r(int[] a, int p, int r) {if (p >= r) return;int q = partition(a, p, r);quickSort_r(a, p, q - 1);quickSort_r(a, q + 1, r);
}private static int partition(int[] a, int p, int r) {int i = p - 1; // [p, i]表示小于pivot值的元素for (int j = p; j < r; j++) {if (a[j] < a[r]) {swap(a, i + 1, j);i++;}}swap(a, i + 1, r);return i + 1;
}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;
}
2 题目
2.1 特殊排序
2.1.1 题目
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分
2.1.2 题解
class Solution {public int[] exchange(int[] nums) {int i = 0;int j = nums.length - 1;while (i < j) {if (nums[i] % 2 == 1) {i++;continue;}if (nums[j] % 2 == 0) {j--;continue;}int tmp = nums[j];nums[i] = nums[j];nums[j] = tmp;i++;j--;}return nums;}
}
2.2 数组中的第k个最大元素
链接:https://leetcode.cn/problems/kth-largest-element-in-an-array
2.2.1 题目
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
2.2.2 题解
class Solution {public int findKthLargest(int[] nums, int k) {if (nums.length < k) return -1;return quickSort(nums, 0, nums.length - 1, k);}private int quickSort(int[] nums, int p, int r, int k) {if (p > r) return -1;int q = partition(nums, p ,r);if (q - p + 1 == k) {return nums[q];} else if (q - p + 1 < k) {return quickSort(nums, q + 1, r, k - (q - p + 1));} else {return quickSort(nums, p, q - 1, k);}}private int partition(int[] nums, int p, int r) {int i = p;int j = r - 1;while (i < j) {while (i < j && nums[i] > nums[r]) {i++;}while (i < j && nums[j] <= nums[r]) {j--;}if (i < j) {swap(nums, i, j);i++;j--;}}if (j >= p && nums[j] < nums[r]) {swap(nums, j , r);return j;} else {swap(nums, j + 1, r);return j + 1;}}private void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}
class Solution {public int findKthLargest(int[] nums, int k) {if (nums.length < k) return -1;return quickSort(nums, 0, nums.length - 1, k);}private int quickSort(int[] nums, int p, int r, int k) {if (p > r) return -1;int q = partition(nums, p ,r);if (q - p + 1 == k) {return nums[q];} else if (q - p + 1 < k) {return quickSort(nums, q + 1, r, k - (q - p + 1));} else {return quickSort(nums, p, q - 1, k);}}private int partition(int[] nums, int p, int r) {int i = p - 1; // [p, i]表示小于pivot值的元素for (int j = p; j < r; j++) {if (nums[j] > nums[r]) {swap(nums, i + 1, j);i++;}}swap(nums, i + 1, r);return i + 1;}private void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}
}
2.3 对链表进行插入排序
链接:https://leetcode.cn/problems/insertion-sort-list
2.3.1 题目
给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。
插入排序 算法的步骤:
插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时,从输入数据中删除一个元素(红色),并就地插入已排序的列表中。
对链表进行插入排序。
示例 1:
输入: head = [4,2,1,3]
输出: [1,2,3,4]
示例 2:
输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]
2.3.2 题解
class Solution {public ListNode insertionSortList(ListNode head) {if (head == null) return null;// 存储已经排序好的节点ListNode newHead = new ListNode(Integer.MIN_VALUE, null);// 遍历节点ListNode p = head;while (p != null) {ListNode tmp = p.next;// 寻找p节点插入的位置,插入到哪个节点后面ListNode q = newHead;while (q.next != null && q.next.val <= p.val) {q = q.next;}p.next = q.next;q.next = p;p = tmp;}return newHead.next;}
}
2.4 排序预处理
2.4.1 题目
有一组无序数据,找到出现次数最多的数据
public int maxCount(int[] data) {Arrays.sort(data);int n = data.length;int pre = -1;int count = 0;int max = -1;for (int i = 0; i < n; ++i) {if (data[i] == pre) {count++;if (max < count) max = count;} else {count = 1;pre = data[i];if (max < count) max = count;}}return max;
}
相关文章:

算法练习-排序(一)
算法练习-排序(一) 文章目录算法练习-排序(一)1 排序算法1.1 冒泡排序1.1.1代码1.2插入排序1.2.1代码1.3 选择排序1.3.1代码1.4归并排序1.4.1代码1.5 快速排序1.5.1 思路1.5.2 代码2 题目2.1 特殊排序2.1.1 题目2.1.2 题解2.2 数组中的第k个最大元素2.2.1 题目2.2.2 题解2.3 对…...

CentOS7.6快速安装Docker
快速安装 官网安装参考手册:https://docs.docker.com/install/linux/docker-ce/centos/ 确定你是CentOS7及以上版本,yum是在线安装! [rootVM-4-5-centos ~]# cat /etc/redhat-releaseCentOS Linux release 7.6.1810 (Core)接下来您只管自上向下执行命令即可&#x…...

CentOS 7安装N卡驱动和CUDA和cuDNN
前言系统一开始是CentOS 7.6,安装依赖时yum给的内核文件的版本号和uname -r的结果不一样,这时不能直接装依赖,装上后后面装驱动时会报错找不到内核头文件(最开始我直接装依赖了,以为高版本兼容低版本,然后装驱动时报错…...

Java开发 - 分页查询初体验
前言在上一篇,我们对es进行了深入讲解,相信看过的小伙伴已经能基本掌握es的使用方法,我们知道,es主要针对的是搜索条件,在这方面es具有无可比拟的优势,但我们也会注意到,有时候搜索条件过于宽泛…...

C语言循环语句do while和嵌套循环语句讲解
C do…while 循环 不像 for 和 while 循环,它们是在循环头部测试循环条件。在 C 语言中,do…while 循环是在循环的尾部检查它的条件。 do…while 循环与 while 循环类似,但是 do…while 循环会确保至少执行一次循环。 语法 C 语言中 do…w…...
【计算机视觉】OpenCV 4高级编程与项目实战(Python版)【7】:拼接图像
我们已经知道,图像是通过数组描述的,那么拼接图像其实就是拼接数组。NumPy提供了2个拼接数组的函数,分别是hstack函数和vstack函数,这两个拼接函数可以将两个数组水平和垂直拼接在一起,也就相当于将两幅图像水平和垂直拼接在一起,本节将详细讲解如何使用这两个函数水平拼…...

王道操作系统课代表 - 考研计算机 第二章 进程与线程 究极精华总结笔记
本篇博客是考研期间学习王道课程 传送门 的笔记,以及一整年里对 操作系统 知识点的理解的总结。希望对新一届的计算机考研人提供帮助!!! 关于对 “进程与线程” 章节知识点总结的十分全面,涵括了《操作系统》课程里的全…...

C++修炼之练气期三层——函数重载
目录 1.引例 2.函数重载的概念 3.C支持函数重载的原理 1.引例 倘若现在要实现一个加法计算器,用C语言实现的话我们会选择这样的方式: int Add_int(int a, int b) {return a b; }double Add_double(double a, double b) {return a b; } 在使用加…...
在linux上运行jar程序操作记录
1.文件传送 使用ftp把打包后的项目jar包上传到linux服务器的目录上(这里有两个文件,一个pengning.jar,一个配置文件application.yml) 2.进入目录并运行程序 打开终端,进入pengning.jar所在的目录 [rootcampus /]# [rootcampu…...
【STM32】入门(十二):实时操作系统RTOS和通用操作系统GPOS的区别
1、简述 实时操作系统(RTOS,Real Time Operating System) 通用操作系统(GPOS,General Purpose Operating System) 2、区别 1)任务 实时操作系统:使用分时设计,其中每个任务被分配一小段时间,在切换到另一…...
2023-3-1刷题情况
在网格图中访问一个格子的最少时间 题目描述 给你一个 m x n 的矩阵 grid ,每个元素都为 非负 整数,其中 grid[row][col] 表示可以访问格子 (row, col) 的 最早 时间。也就是说当你访问格子 (row, col) 时,最少已经经过的时间为 grid[row][…...

Web前端学习:五 - 练习
四二-四八:baidu糯米 44-48 1、写法1 (1)a.movie1 .Navigation .recommend .listbanner a.movie1{background: url(img/h_1.jpg) no-repeat 63px 9px;}表示a标签且class为movie1的元素 如: <a href"#" class&quo…...
软件测试之测试用例设计方法—等价类划分法
测试用例设计方法—等价类划分法 掌握常用测试用例设计方法,再结合测试用例的要素能给快速的实现测试用例的设计和编写.但是由于软件系统大小的不同我们不可能把所有的单个或组合的情况都进行测试,所以我们测试时应该根据不同的场景设计不同的测试用例,尽可能的覆盖到全部需要…...

gdb常用命令详解
gdb常用调试命令概览和说明 run命令 在默认情况下,gdbfilename只是attach到一个调试文件,并没有启动这个程序,我们需要输入run命令启动这个程序(run命令被简写成r)。如果程序已经启动,则再次输入 run 命令…...

2022 年江西省职业院校技能大赛高职组“信息安全管理与评估”赛项样题
2022 年江西省职业院校技能大赛高职组 “信息安全管理与评估”赛项样题 一、 赛项信息 第一场比赛: 竞赛阶段 任务阶 段 竞赛任务 竞赛时 间 分值 第一阶段 任务 1 网络平台搭建 90 平台搭建与安全 任务 2 网络安全设备配置与防护 210 设备配置防护…...

射频调试的习惯
三月开工了,一个月的调试即将开始。其实调试的重心是测试,核心的推动力是做事的习惯和思维。测试很重要,数据不对,能力和时间都浪费了上面了。测试的问题初步解完了,今天吃饭的时候碰到大领导。领导好忙,我…...

centos7上安装mysql8.0
1、检查一下自己电脑上安装了哪些mysql [rootlocalhost ~]# find / -name mysql 2、把安装的mysql全部删掉 [rootlocalhost ~]# rm -rf /usr/lib64/mysql/ [rootlocalhost ~]# rm -rf /usr/local/mysql/ [rootlocalhost ~]# rm -rf /etc/selinux/targeted/active/modules/100…...

如何使用BackupOperatorToDA将Backup Operators用户权限提升为域管理员
关于BackupOperatorToDA BackupOperatorToDA是一款功能强大的红队提权工具,该工具能够在不使用域控制器RDP或WinRM的情况下,帮助广大研究人员将Backup Operators组的成员账号提升为域管理员权限。 如果红队研究人员在渗透测试的过程中,拿到…...

百度文心大模型开发者斩获CCF BDCI大赛唯一『最佳算法能力奖』
2023年2月24日至25日,中国计算机学会(CCF)主办、苏州市吴江区人民政府支持,苏州市吴江区工信局、吴江区东太湖度假区管理办公室、苏州市吴江区科技局、CCF大数据专家委员会及其他专业委员会等多家组织单位共同承办的大数据与AI领…...
合宙Air780E|硬件元数据|LuatOS-SOC接口|官方demo|学习(21):hmeta(本库尚在开发中)
基础资料 基于Air780E开发板:Air780E文档中心 简介:CSDK开发 探讨重点 本系列主要探讨利用合宙平台进行fota_iot差分包升级的基本操作、编译及上传,升级等操作。 硬件准备 Air780E开发板1块,SIM卡1张。 内容参考 官方wi…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...

GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?
FTP(File Transfer Protocol)本身是一个基于 TCP 的协议,理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况,主要原因包括: ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

解析“道作为序位生成器”的核心原理
解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制,重点解析"道作为序位生成器"的核心原理与实现框架: 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...

EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势
一、WebRTC与智能硬件整合趋势 随着物联网和实时通信需求的爆发式增长,WebRTC作为开源实时通信技术,为浏览器与移动应用提供免插件的音视频通信能力,在智能硬件领域的融合应用已成必然趋势。智能硬件不再局限于单一功能,对实时…...