Java的时间复杂度和空间复杂度和常见排序
目录
一丶时间复杂度
二丶空间复杂度
三丶Java常见排序
1. 冒泡排序(Bubble Sort)
2.插入排序(Insertion Sort)
3.希尔排序(Shell Sort)
4.选择排序(Selection Sort)
5.堆排序(Heap Sort)
6.归并排序(Merge Sort)
7.快速排序(Quick Sort)
8.计数排序(Counting Sort)、桶排序(Bucket Sort) 和 基数排序(Radix Sort)
简介:时间复杂度和空间复杂度是评估算法性能的两个重要指标,他们分别用于衡量算法执行时间长短和算法所存储空间大小;
一丶时间复杂度
时间复杂度:他描述了算法执行所需时间和数据规模之间的关系。具体来说,时间复杂度是算法中基本操作语句执行的次数,这次次数随着数据规模的增大而增大。时间复杂度通常用大O表示法(Big O notation)来表示,他忽略了常数因子和低阶项,只保留最高阶项,从而简洁明了的表示出算法的时间增长趋势;例如
- O(1):表示算法的执行时间是固定,与输入规模无关;
- O(log n):表示算法的执行时间与输入规模的对数成正比;
- O(n):表示线性时间复杂度,算法的执行时间与输入规模成线性比例增长;
- O(n log n):表示算法的执行时间与输入规模的线性对数比例增长;
- O(n^2):表示平方时间复杂度,算法的执行时间与输入规模的平方成比例增长。
通过分析算法的时间复杂度,可以评估算法的性能,优化算法的效率,从而提高程度的执行速度。
二丶空间复杂度
空间复杂度:它描述了算法在运行过程中临时占用存储空间的大小与数据规模之间的关系。空间复杂度也是用大O表示法来表示,他衡量的是算法运行过程中额外消耗的存储空间。例如
- O(1):表示算法的空间复杂度是固定的,与输入规模无关;
- O(log n):表示线性空间复杂度,算法所需内存与输入规模成线性比例增长
- O(n^2):表示平方空间复杂度,算法所需内存与输入规模的平方成比例增长。
通过分析算法的空间复杂度,可以避免内存的浪费,提高空间利用率,从而降低算法执行成本,提高程序性能;
三丶Java常见排序
1. 冒泡排序(Bubble Sort)
原理:通过重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复的进行直到没有再需要交换,也就是说该数列已经排序完成。
特点:简单,稳定,单效率低。时间复杂度O(n^2),空间复杂度O(1);

//冒泡排序public static void bubbleSort(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]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}
2.插入排序(Insertion Sort)
原理:通过构建有序序列,对于未排序数据,在已排序序序列中从后向前扫描,找到相应位置插入;
特点:稳定排序,适用于少量数据的排序,但是数据接近有序时效率较高。时间复杂度最好的情况下O(n),最坏的情况下O(n^2);空间复杂度O(1);

//直接插入排序public static void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {//取出第二个数据,默认已经排序int key = arr[i];//获取前以为数据的索引int j = i-1;/* 将 arr[0..i-1] 中大于 key 的元素移动到其当前位置的前 1 个位置*/while (j >=0 && arr[j] > key) {arr[j+1] = arr[j];j = j-1;}arr[j+1] = key;}}
3.希尔排序(Shell Sort)
原理:是插入排序的一种更高效的改进版本。希尔排序又称为缩小量排序,它将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录基本有序,在对全体记录进行直接插入排序;
特点:不稳定的排序,时间复杂度依赖于增量序列的选择,但平均性能优于直接插入排序;
时间复杂度:O(n^1.3),空间复杂度O(1);

//直接排序public static void shellSort(int[] arr) {int n = arr.length;for (int gap = n/2; gap > 0; gap /= 2) {for (int i = gap; i < n; i += 1) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}}
4.选择排序(Selection Sort)
原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾;
特点:不稳定排序,时间复杂度:O(n^2),空间复杂度:O(1);

//选择排序public void selectionSort(int[] arr) {int n = arr.length;for (int i = 0; i < n-1; i++) {int min_idx = i;for (int j = i+1; j < n; j++) {if (arr[j] < arr[min_idx]) {min_idx = j;}}// 将找到的 Minimum 元素与第一个元素交换int temp = arr[min_idx];arr[min_idx] = arr[i];arr[i] = temp;}}
5.堆排序(Heap Sort)
原理:是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或大于)他的父节点;
特点:不稳定排序,时间复杂度:O(n log n),空间复杂度:O(1);

// 构建最大堆(辅助函数)
void buildMaxHeap(int arr[]) { int n = arr.length; for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
} // 调整给定的堆
void heapify(int arr[], int n, int i) { int largest = i; // 初始化最大为根 int l = 2 * i + 1; // 左 = 2*i + 1 int r = 2 * i + 2; // 右 = 2*i + 2 // 如果左子节点大于根 if (l < n && arr[l] > arr[largest]) largest = l; // 如果右子节点是最大值 if (r < n && arr[r] > arr[largest]) largest = r; // 如果最大值不是根 if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // 递归地堆化受影响的子树 heapify(arr, n, largest); }
} // 堆排序函数
void heapSort(int arr[]) { int n = arr.length; buildMaxHeap(arr); // 一个个从堆顶取出元素 for (int i = n - 1; i > 0; i--) { // 移动当前根到末尾 int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // 调用max heapify on the reduced heap heapify(arr, i, 0); }
}
6.归并排序(Merge Sort)
原理:是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序;
特点:稳定排序,时间复杂度:O(n log n),空间复杂度:O(n);

public void mergeSort(int[] arr, int l, int r) { if (l < r) { // Same as (l+r)/2, but avoids overflow for // large l and h int m = l+(r-l)/2; // Sort first and second halves mergeSort(arr, l, m); mergeSort(arr, m+1, r); merge(arr, l, m, r); }
} // 合并两个已排序的数组部分
void merge(int arr[], int l, int m, int r) { // Find sizes of two subarrays to be merged int n1 = m - l + 1; int n2 = r - m; /* Create temp arrays */ int L[] = new int[n1]; int R[] = new int[n2]; /*Copy data to temp arrays*/ for (int i=0; i<n1; ++i) L[i] = arr[l + i]; for (int j=0; j<n2; ++j) R[j] = arr[m + 1+ j]; /* Merge the temp arrays */ // Initial indexes of first and second subarrays int i = 0, j = 0; // Initial index of merged subarray array int k = l; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } /* Copy remaining elements of L[] if any */ while (i < n1) { arr[k] = L[i]; i++; k++; } /* Copy remaining elements of R[] if any */ while (j < n2) { arr[k] = R[j]; j++; k++; }
}
7.快速排序(Quick Sort)
原理:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列;
特点:平均时间复杂度:O(n log n),但是最坏的情况下时间复杂度会变成O(n^2)。空间复杂度取决于递归深度,平均为O(n log n),但最坏情况下需要O(n)的额外空间;
public void quickSort(int[] arr, int low, int high) { if (low < high) { // pi is partitioning index, arr[p] is now // at right place int pi = partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); }
} // 该方法用于分区数组,返回分区索引
int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low - 1); // index of smaller element for (int j = low; j < high; j++) { // If current element is smaller than or // equal to pivot if (arr[j] <= pivot) { i++; // swap arr[i] and arr[j] int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // swap arr[i+1] and arr[high] (or pivot) int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp; return i + 1;
}
8.计数排序(Counting Sort)、桶排序(Bucket Sort) 和 基数排序(Radix Sort)
- 这些排序算法是非比较型排序算法,其排序效率在某些情况下会高于比较型排序算法。它们各自适用于一定范围的数据,如计数排序适用于一定范围内的整数排序,桶排序和基数排序则适用于外部排序和大数据排序。

结尾:喜欢的朋友点个赞吧!!!
相关文章:
Java的时间复杂度和空间复杂度和常见排序
目录 一丶时间复杂度 二丶空间复杂度 三丶Java常见排序 1. 冒泡排序(Bubble Sort) 2.插入排序(Insertion Sort) 3.希尔排序(Shell Sort) 4.选择排序(Selection Sort) 5.堆排序&am…...
Qt 学习第十天:标准对话框 页面布局
系统标准对话框 错误对话框 //错误对话框connect(createPro, &QAction::triggered, this, []{//参数1 父亲 参数2 标题 参数3 对话框内显示文本内容 。。。QMessageBox::critical(this, "报错!", "没加头文件!");}); 【运行结果】 信息对话框 co…...
体育数据API纳米足球数据API:足球数据接口文档API示例⑩
纳米体育数据的数据接口通过JSON拉流方式获取200多个国家的体育赛事实时数据或历史数据的编程接口,无请求次数限制,可按需购买,接口稳定高效; 覆盖项目包括足球、篮球、网球、电子竞技、奥运等专题、数据内容。纳米数据API2.0版本…...
[数据集][目标检测]高铁受电弓检测数据集VOC+YOLO格式1245张2类别
数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):1245 标注数量(xml文件个数):1245 标注数量(txt文件个数):1245 标注…...
Vuex:深入理解所涉及的几个问题
你好,我是沐爸,欢迎点赞、收藏、评论和关注。 一、Vuex 是什么? Vuex 是一个专为 Vue.js 应用程序开发的状态管理模式。它采用集中式存储管理应用的所有组件的状态,并以相应的规则保证状态以一种可预测的方式发生变化。 二、Vu…...
vue原理分析(六)研究new Vue()
今天我们来分析使用new Vue() 之前研究时,只是说是在创建一个实例。并没有深入进行研究 在vue的源码中找下Vue的构造函数 function Vue(options) {if (!(this instanceof Vue)) {warn$2(Vue is a constructor and should be called with the new keyword);}this.…...
滑动窗口+动态规划
前言:分析这个题目的时候,就知道要这两个线段要分开,但是要保证得到最优解,那么我们在选取第二根线段的时候,要保证我们第一根线段是左边最优解 并且我们选的两根线段的右端点一定是我们的数组的点(贪心思…...
vscode配置django环境并创建django项目
1、创建文件夹 创建文件夹 并在vscode打开 终端输入命令 “ python -m venv env ” 查看目录结构 2、创建项目 在终端输入 django-admin startproject 文件名(这里以myshop为例) 3、创建应用 在myshop打开终端 在终端输入 django-admin startapp 应用名 这里以app1为例…...
WebGL系列教程四(绘制彩色三角形)
目录 1 前言2 varying变量介绍3 开始绘制3.1 声明顶点着色器3.2 声明片元着色器3.3 创建顶点和颜色的缓冲区3.4 指定变量从缓冲区获取值3.5 效果3.6 varying的内涵3.7 完整代码 4 总结 1 前言 上一篇中我们介绍了如何使用缓冲区来绘制三角形,这一篇我们来讲讲如何给…...
通过mxGraph在ARMxy边缘计算网关上实现工业物联网
在当今的工业4.0时代,工业物联网(IIoT)已经成为制造业转型升级的关键技术之一。ARMxy边缘计算网关作为工业自动化和物联网的重要组成部分,能够为工厂车间提供实时的数据处理能力和智能化服务。而mxGraph作为一种流行的JavaScript库…...
GEE案例:利用sentinel-1数据进行洪水监测分析(直方图统计)
目录 简介 数据 函数 ee.Filter.calendarRange(start, end, field) Arguments: Returns: Filter updateMask(mask) Arguments: Returns: Image 代码 结果 简介 利用sentinel-1数据进行洪水监测分析 数据 COPERNICUS/S1_GRD数据是由欧洲空间局(ESA)的Copernicus项…...
QT 联合opencv 易错点
https://blog.csdn.net/qq_51699436/article/details/135777911 网上已经有大量优秀切详尽的文章来讲述QT联合opencv了,我把容易出错的点列出来备忘 1、在进行opencv进行编译时,要确认好是32位还是64位,因为在创建QT项目的时候QT和opencv要匹…...
例如/举例的使用方法 ,e.g., 以及etc的使用方法
e.g. 例如 for example for the sake of example such as 1 e.g. 是拉丁语 exempli gratia 的缩写意思是“举个例子,比如”,等同于for example、 for the sake of example、such as,使用 e.g. 的目的是用几个例子来说明前面的观点。 2 例…...
20240902-VSCode-1.19.1-部署vcpkg-win10-22h2
20240902-VSCode-1.19.1-部署vcpkg-win10-22h2 软件环境 标签:C++ VSCode mingw gcc13 vcpkg cmake分栏:C++操作系统:Windows10 x64 22h2一、安装VScode-1.19.1 请参考另一篇文章《20240717-VSCode-1.91.1-部署gcc13-C++23-win10-22h2》。 二、安装cmake 本文流程需要安…...
MySQL学习(多表操作)
基本知识 一对多 创建部门表 – 主表 create table if not exists dept(deptno varchar(20) primary key ,name varchar(20) );创建员工表 – 创建外键约束 方式1constraint emp_fk foreign key(dept_id) references dept(deptno) create table if not exists emp(eid varc…...
鸿蒙开发(NEXT/API 12)【网络连接管理】 网络篇
简介 网络连接管理提供管理网络一些基础能力,包括WiFi/蜂窝/Ethernet等多网络连接优先级管理、网络质量评估、订阅默认/指定网络连接状态变化、查询网络连接信息、DNS解析等功能。 说明 为了保证应用的运行效率,大部分API调用都是异步的,对…...
VMware Fusion虚拟机Mac版 安装Ubuntu操作系统教程
Mac分享吧 文章目录 下载镜像地址:[www.macfxb.cn](http://www.macfxb.cn)一、CentOS安装完成,软件打开效果二、Mac中安装Ubuntu虚拟机1️⃣:下载镜像2️⃣:创建虚拟机3️⃣:虚拟机设置4️⃣:虚拟机安装5️…...
基于SpringBoot+Vue+MySQL的房屋租赁管理系统
系统展示 用户前台界面 管理员后台界面 系统背景 二十一世纪互联网的出现,改变了几千年以来人们的生活,不仅仅是生活物资的丰富,还有精神层次的丰富。在互联网诞生之前,地域位置往往是人们思想上不可跨域的鸿沟,信息的…...
虚拟机器配置固定IP地址
新安装的虚拟机,如何配置固定的ip地址,废话少说直接上干货 第一步:在VMarea中 选中你要固定IP的虚拟机器,点击上面的“编辑”按钮,然后找到“虚拟网络编辑器”,选中你要修改的ip VMnet8,然后是…...
用python实现基于形态学的方法,如开运算和闭运算,来去除pcd格式激光点云中的植被
在Python中,你可以使用open3d库来读取和处理pcd格式的点云数据。下面是一个示例代码,展示如何使用形态学操作来去除植被。 首先,确保你已经安装了open3d库,可以使用以下命令进行安装: pip install open3d接下来&…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
二维FDTD算法仿真
二维FDTD算法仿真,并带完全匹配层,输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...
何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡
何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践,很多人以为AI已经强大到不需要程序员了,其实不是,AI更加需要程序员,普通人…...
