数据结构小测试:排序算法

目录

1、请简述数据结构八大排序算法的思路。

2、常用排序算法手写

冒泡排序:

选择排序:

快速排序:

归并排序:

堆排序:

3、额外再加一个二分查找吧


1、请简述数据结构八大排序算法的思路。

冒泡排序:将相邻元素之间的比较和交换,使得每一轮比较后,最大的元素能够到达数组的末尾。重复这个过程,直到整个数组有序。

选择排序:在每一轮中,找到数组中最小的元素,并将其与当前轮的第一个元素交换位置。重复这一操作,使得每一轮过后,都有一个元素被放到了正确的位置上。

插入排序:将数组分为已排序部分和未排序部分,每次从未排序部分取出一个元素,插入到已排序部分的正确位置上。

希尔排序:首先确定一个间隔序列,按此间隔将数组元素分组并进行插入排序。随后逐渐缩小间隔并重复排序过程,直到间隔为1。

快速排序:选一个基准元素,通过一趟排序将整体数据分割成两部分,基准元素左边的数据比基准元素小,右边的数据比基准元素大,然后再按此方法对这两部分数据分别进行快速排序,递归进行,直至完成。

归并排序:先将数组分成两半,分别对这两半进行排序,然后将它们合并成一个有序数组。重复递归这一操作,直至数组有序

堆排序:将待排序的序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个序列重新构造成一个堆,这样会得到n个元素中的次大值。重复以上操作。

计数排序:对输入数据中的每个元素进行计数,确定每个元素出现的次数;然后利用计数结果将元素放到输出序列的正确位置上。

2、常用排序算法手写

冒泡排序:

将相邻元素之间的比较和交换,使得每一轮比较后,最大的元素能够到达数组的末尾。重复这个过程,直到整个数组有序。时间复杂度:O(n^2)

代码:

public static void sort(int[] arr) {for(int j=0;j<arr.length;j++) {for(int i=0;i<arr.length-1-j;i++) {if(arr[i]>arr[i+1]) {int temp=arr[i];arr[i] =arr[i+1];arr[i+1]=temp;}}}}

选择排序:

在每一轮中,找到数组中最小的元素,并将其与当前轮的第一个元素交换位置。重复这一操作,使得每一轮过后,都有一个元素被放到了正确的位置上。 时间复杂度:O(nlogn)

代码:

public static void simpleswap(int[] arr) {for(int i=0; i<arr.length; i++) {  //负责遍历索引int index =i ;//index负责找最小的索引for(int j=i+1; j<arr.length; j++) { //负责找剩余元素中的最小值if(arr[j]<arr[index]) {index = j;}}//每找到一次就与前面的交换一次if(i != index){int temp = arr[index];arr[index] = arr[i];arr[i] = temp;}}
}

快速排序:

选一个基准元素,通过一趟排序将整体数据分割成两部分,基准元素左边的数据比基准元素小,右边的数据比基准元素大,然后再按此方法对这两部分数据分别进行快速排序,递归进行,直至完成。

时间复杂度:O(nlogn)

代码:

public static void quicksort(int[] arr,int left,int right) {//递归出口if(left>=right) {return;}//定义变量保存基准数int base=arr[left];//定义j游标指向最右边int j=right;//定义i游标指向最左边int i=left;while(i!=j) {//j从后往前找比基准数小的while(arr[j]>=base&&i<j) {j--;}//i从前往后找比基准数大的while(arr[i]<=base&&i<j) {i++;}//i、j两数都停下,交换位置int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}//i和j相等(跳出循环)//交换基数和ij相遇位置的数据arr[left]=arr[i];arr[i]=base;//排序基准数的左边quicksort(arr,left,i-1);//排序基准数的右边quicksort(arr,i+1,right);}

归并排序:

先将数组分成两半,分别对这两半进行排序,然后将它们合并成一个有序数组。重复递归这一操作,直至数组有序。时间复杂度:O(nlogn)

底层逻辑:先拆分,拆到不能再拆分,然后进行合并,合并的时候进行排序

代码: 

public class MergeSort {public static void main(String[] args) {int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };int[] newNums = mergeSort(nums, 0, nums.length - 1);System.out.println(Arrays.toString(newNums));}public static int[] mergeSort(int[] nums, int left, int right) {if (left == right)//已经拆分彻底,拆分递归的终止条件return new int[] { nums[left] };//拆分int mid = left + (right - left) / 2;int[] leftArr = mergeSort(nums, left, mid); //左有序数组int[] rightArr = mergeSort(nums, mid + 1, right); //右有序数组int[] newNum = new int[leftArr.length + rightArr.length]; //新有序数组//合并,将拆分的数按大小放到新有序数组里面int m = 0, i = 0, j = 0;while (i < leftArr.length && j < rightArr.length) {newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];}while (i < leftArr.length)newNum[m++] = leftArr[i++];while (j < rightArr.length)newNum[m++] = rightArr[j++];return newNum;}
}

堆排序:

利用完全二叉树构建大顶堆,此时,整个序列的最大值就是堆顶的根节点。

将堆顶元素与堆底元素进行交换,此时堆底元素就为最大值。

然后将剩余n-1个序列重新构造成一个大顶堆。重复以上操作。

时间复杂度:O(nlogn)

大顶堆:父节点的值大于等于其左右孩子的值 等价于 arr[i]>=arr[2i+1] && arr[i]>=arr[2i+2]

流程图示:

构建大顶堆:

堆顶元素与堆底元素交换,堆底元素不再参与构建,剩下的再次重新构建大顶堆、交换

这一次重新构建时,直接让parent指向堆顶元素,再判断即可

java代码:


public class 堆排序 {public static void main(String[] args) {// TODO Auto-generated method stubint[] arr= {5,7,4,2,0,3,1,6};//1、构建大顶堆for(int i=arr.length-1;i>=0;i--) {//从下往上,每个节点以此判断为大顶堆;从length-1节点到0节点adjust(arr,i,arr.length);}System.out.println(Arrays.toString(arr));//输出第一次构建的大顶堆//2、堆顶堆底元素交换,除堆底外其余元素继续构建大顶堆for(int j=arr.length-1;j>=0;j--) {int temp=arr[j];arr[j]=arr[0];arr[0]=temp;//System.out.println(Arrays.toString(arr));//剩余元素继续构建大顶堆adjust(arr,0,j);//parent游标直接指向堆顶元素即可,最后一个元素不再参与构建//System.out.println(Arrays.toString(arr));}System.out.println(Arrays.toString(arr));}public static void adjust(int[] arr,int parent,int length) {int child = parent*2+1;//定义左孩子while(child<length) {//如果有孩子节点int rchild=child+1;//定义右孩子//这部分单纯为了让child指向最大childif(rchild<length && arr[child]<arr[rchild]) {//如果有右孩子,且右孩子比较大child++;//child指向较大的孩子节点(右孩子节点)}//如果父节点小于其孩子节点if(arr[parent]<arr[child]) {int temp=arr[parent];arr[parent]=arr[child];arr[child]=temp;//父子结点交换后parent指向childparent=child;child=2*parent+1;//再次进行循环比较}else {//如果该parent没有孩子节点或者父节点大于孩子节点,直接返回,此节点判断完毕break;}}}}

3、额外再加一个二分查找吧

时间复杂度:O(logn)

代码:

public class 二分查找 {public static void main(String[] args) {// TODO Auto-generated method stubint[] arr= {3,45,56,57,67,88};System.out.println(search(arr,11));}public static int search(int[] arr,int target) {int left = 0;int right = arr.length-1;while(left<=right) {int middle = (left+right)/2;if(target==arr[middle]) {System.out.println("找到了");return middle;}else if(target<arr[middle]){right=middle-1;}else {left=middle+1;}}System.out.println("没有这个数据");return -1;}}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/379776.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

亚信安全发布2024年第24期《勒索家族和勒索事件监控报告》

本周态势快速感知 本周&#xff0c;勒索软件LockBit涉嫌对美国一家生产乙烯基产品的公司&#xff08;Homeland Vinyl&#xff09;进行攻击。LockBit声称他们已窃取了销售、库存、财务交易数据及其他公司记录&#xff0c;并声明将于2024年7月19日公开这些被盗信息。本周全球共监…

【iOS】OC类与对象的本质分析

目录 前言clang常用命令对象本质探索属性的本质对象的内存大小isa 指针探究 前言 OC 代码的底层实现都是 C/C代码&#xff0c;OC 的对象都是基于 C/C 的数据结构实现的&#xff0c;实际 OC 对象的本质就是结构体&#xff0c;那到底是一个怎样的结构体呢&#xff1f; clang常用…

AI算法17-贝叶斯岭回归算法Bayesian Ridge Regression | BRR

贝叶斯岭回归算法简介 贝叶斯岭回归&#xff08;Bayesian Ridge Regression&#xff09;是一种回归分析方法&#xff0c;它结合了岭回归&#xff08;Ridge Regression&#xff09;的正则化特性和贝叶斯统计的推断能力。这种方法在处理具有大量特征的数据集时特别有用&#xff…

安全入门day01

一、常用名词 1、前后端 &#xff08;1&#xff09;前端 前端主要负责用户界面的展示和交互。它通常包括HTML、CSS和JavaScript等技术的使用&#xff0c;也可能使用各种前端框架和库&#xff0c;如React、Vue.js、Angular等&#xff0c;来构建更加复杂和动态的用户界面。前端…

校验el-table中表单项

需求&#xff1a; 表格中每一行都有几个必填项&#xff0c;如用户提交时有未填的选项&#xff0c;将该选项标红且给出提示&#xff0c;类似el-form 的那种校验 el-table本身并没有校验的方法&#xff0c;而且每一行的输入框也是通过插槽来实现的&#xff0c;因此我们要自己跟…

log4js node日志插件

最近不是特别忙在用express搭建后台项目&#xff0c;在开发过程中遇到了需要输入日志的问 本来想直接用node自带的console来实现&#xff0c;后来发现console输出的日志达不到自己希望的 日志格式&#xff0c;后来各种百度发现了log4js插件&#xff0c;本文来记录log4js插件使用…

一文-深入了解Ansible常见模块、安装和部署

1 Ansible 介绍 Ansible是一个配置管理系统configuration management system, python 语言是运维人员必须会的语言, ansible 是一个基于python 开发的&#xff08;集合了众多运维工具 puppet、cfengine、chef、func、fabric的优点&#xff09;自动化运维工具, 其功能实现基于ss…

django实现用户的注册、登录、注销功能

创建django项目的步骤&#xff1a;Django项目的创建步骤-CSDN博客 一、前置工作 配置数据库&#xff0c;设置数据库引擎为mysql 1、在settings文件中找到DATABASES, 配置以下内容 DATABASES {"default": {ENGINE: django.db.backends.mysql, # 数据库引擎NAME: dja…

基于springboot和mybatis的RealWorld后端项目实战二之实现tag接口

修改pom.xml 新增tag数据表 SET FOREIGN_KEY_CHECKS0;-- ---------------------------- -- Table structure for tags -- ---------------------------- DROP TABLE IF EXISTS tags; CREATE TABLE tags (id bigint(20) NOT NULL AUTO_INCREMENT,name varchar(255) NOT NULL,PR…

【hadoop大数据集群 2】

【hadoop大数据集群 2】 文章目录 【hadoop大数据集群 2】1. 虚拟机克隆2. 时间同步3. 环境变量配置、启动集群、关闭集群 1. 虚拟机克隆 克隆之后一定要重新生成新虚拟机唯一的MAC地址和UUID等&#xff0c;确保新虚拟机与源虚拟机在网络拓扑中不发生冲突。 注意1.生成新的MA…

IDEA关联数据库

《IDEA破解、配置、使用技巧与实战教程》系列文章目录 第一章 IDEA破解与HelloWorld的实战编写 第二章 IDEA的详细设置 第三章 IDEA的工程与模块管理 第四章 IDEA的常见代码模板的使用 第五章 IDEA中常用的快捷键 第六章 IDEA的断点调试&#xff08;Debug&#xff09; 第七章 …

Spring Boot2(Spring Boot 的Web开发 springMVC 请求处理 参数绑定 常用注解 数据传递)

目录 一、Spring Boot 的Web开发 1. 静态资源映射规则 2. enjoy模板引擎 二、springMVC 1. springMVC-请求处理 测试&#xff1a; 以post方式请求 限制请求携带的参数 GetMapping 查询 PostMapping 新增 DeleteMapping删除 PutMapping 修改 2. springMVC-参…

电子画册制作攻略:如何让你的作品吸引眼球

随着数字化时代的到来&#xff0c;电子画册作为一种新兴的传播媒介&#xff0c;已经越来越受到人们的青睐。它不仅能够以生动的形式展现内容&#xff0c;还可以轻松地实现互动和分享。然而&#xff0c;如何让你的电子画册作品在众多竞争中脱颖而出&#xff0c;吸引更多眼球呢&a…

景联文科技构建高质量心理学系知识图谱,助力大模型成为心理学科专家

心理大模型正处于快速发展阶段&#xff0c;在临床应用、教育、研究等多个领域展现出巨大潜力。 心理学系知识图谱能够丰富心理大模型的认知能力&#xff0c;使其在处理心理学相关问题时更加精确、可靠和有洞察力。这对于提高心理健康服务的质量和效率、促进科学研究以及优化教育…

【MySQL进阶篇】SQL优化

1、插入数据 insert优化 批量插入&#xff1a; insert into tb_user values(1,tom),(2,cat),(3,jerry); 如果插入数据过大&#xff0c;可以将业务分割为多条insert语句进行插入。 手动提交事务&#xff1a; start transaction; insert into tb_user values(1,tom),(2,cat),(3…

Linux——多路复用之select

目录 前言 一、select的认识 二、select的接口 三、select的使用 四、select的优缺点 前言 在前面&#xff0c;我们学习了五种IO模型&#xff0c;对IO有了基本的认识&#xff0c;知道了select效率很高&#xff0c;可以等待多个文件描述符&#xff0c;那他是如何等待的呢&a…

视频活码如何在线制作?分享快速制作二维码的方法

视频想要快速的分享现在有很多的人会选择二维码的方式&#xff0c;将视频转换成二维码通过手机扫码就能够快速在线查看视频内容&#xff0c;这样可以不占用扫码者自身的内存&#xff0c;随时扫码从云端调取内容查看&#xff0c;更加的方便快捷便于内容的分享。那么具体该如何实…

搭建个人智能家居 7 - 空气颗粒物检测

搭建个人智能家居 7 - 空气颗粒物检测 前言说明PMS5003ESPHomeHomeAssistant结束 前言 到目前为止&#xff0c;我们这个智能家居系统添加了4个外设&#xff0c;分别是&#xff1a;LED灯、RGB灯、DHT11温度传感器和SGP30。今天继续添加环境测量类传感器“PMS5003空气颗粒物检测…

【Leetcode】二十一、前缀树 + 词典中最长的单词

文章目录 1、背景2、前缀树Trie3、leetcode208&#xff1a;实现Trie4、leetcode720&#xff1a;词典中最长的单词 1、背景 如上&#xff0c;以浏览器搜索时的自动匹配为例&#xff1a; 如果把所有搜索关键字放一个数组里&#xff0c;则&#xff1a;插入、搜索一个词条时&#x…

VisualRules-Web案例展示(一)

VisualRules单机版以其卓越的功能深受用户喜爱。现在&#xff0c;我们进一步推出了VisualRules-Web在线版本&#xff0c;让您无需安装任何软件&#xff0c;即可在任何浏览器中轻松体验VisualRules的强大功能。无论是数据分析、规则管理还是自动化决策&#xff0c;VisualRules-W…