数据结构-8.Java. 七大排序算法(中篇)
本篇博客给大家带来的是排序的知识点, 由于时间有限, 分两天来写, 中篇主要实现后三种排序算法: 冒泡排序,快速排序,下一篇讲 归并排序.
文章专栏: Java-数据结构
若有问题 评论区见
欢迎大家点赞 评论 收藏 分享
如果你不知道分享给谁,那就分享给薯条.
你们的支持是我不断创作的动力 .
1. 冒泡排序
1.1 算法思路
1. 将数组中相邻元素从前往后依次进行比较,如果前一个元素比后一个元素大,则交换,一趟下来后最大元素就在数组的末尾
2. 依次进行上述过程,直到数组中所有的元素都排列好
如下模拟动图:
1.2 具体步骤:
1. 定义i = 0, j = 0, i 表示冒泡的趟数, j为起始位置的下标值.
2. 每一趟中遍历未排序数组, 比较[ j ] 与 [ j + 1 ] 的大小, 若[ j ] 较大, 则值交换, 否则 j++.
1.3 代码实现:
// 交换下标分别为 i 和 j 的两个元素
public static void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}//冒泡排序public static void bubbleSort(int[] array) {for (int i = 0; i < array.length-1; i++) {for (int j = 0; j < array.length-1-i; j++) {if(array[j] > array[j+1]) {swap(array,j,j+1);}}}}
1.4 优化冒泡排序:
如上图, 进行完第i = 2 趟之后,发现数组已经有序了,没有必要再进行下去了.
于是我们可以定义一个标记变量flag = false,如果发生交换就将flag = true.
优化代码如下:
/*** 冒泡排序:* 时间复杂度:* 最坏情况: 没有优化的 O(N^2)* 最好情况: 优化过的O(N)* 空间复杂度: O(1)* 稳定性: 稳定* @param array*/public static void bubbleSort(int[] array) {for (int i = 0; i < array.length-1; i++) {boolean flag = false;for (int j = 0; j < array.length-1-i; j++) {if(array[j] > array[j+1]) {swap(array,j,j+1);flag = true;}}if(!flag) {//没交换,说明已经有序return;}}}public static void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
1.5 冒泡排序的特性总结:
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度:O(N^2)
3. 空间复杂度:O(1)
4. 稳定性:稳定
2. 快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法.
2.1 基本思想:
任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
[start,end]为待排序区间.
private static void quick(int[] array,int start,int end) {if(start >= end) return;//start下标 与 end相遇说明基准值已经排好序了.//拿到基准值下标,将原数组划分为两个子序列.int pivot = partition(array,start,end);//递归排左序列quick(array,start,pivot-1);//递归排右序列quick(array,pivot+1,end);}
上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,在写快速排序递归框架时可想想二叉树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式有:
2.2 具体实现:
2.2.1 Hoare版:
1. 将首元素作为关键字key, 先从数组最右边right开始,向左找到比key小的数 i .再从左left开始向右找比key大的数 j . i 和 j 交换.
2. 重复第一步直到left >= right.
3. 当left = right 时 交换 [left] 和 key. 此时left 和 right所在的位置即为基准值下标.
具体过程如下图:
代码如下:
public static void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
private static int partition(int[] array,int left,int right) {int key = array[left];int i = left;while(left < right) {//1. 为什么要先走右边而不是先走左边?//如果先走右边,最终pivot下标处的值一定比key(头元素)小,自己画图便知.//如果先走左边,最终pivot下标处的值一定比key(头元素)大,自己画图便知.//2. 为什么要 >= 和 <= 而不能是>和< 等号必须取,因为left一开始就在key下标,// 判断的时候,a[left]<key为false,a[right]>key为也为false,所以等号必取,否则left和right一开始就不动.while(left < right && array[right] >= key) {//如果所有元素确实都小于key,那么会越界,所以加上left<right条件right--;}while(left < right && array[left] <= key) {left++;}//走到这里说明right的元素值小于key,left的元素大于key,那么交换即可swap(array,left,right);}//走到这里,left=right,key与pivot交换,但是原先的key位置left已经改变了,//所以再left变之前先将其保存下来.swap(array,i,left);//返回基准值的下标.return left;}
2.2.2 挖坑法:
1. 定义变量key=[left], 从右边right开始往左,找到比key小的第一个数 tmpR,tmpR的下标为 i , [left] = tmpR, 将 left位置覆盖, 此时 i 位置可看作一个空出来的坑位.
2. 再从左边left开始往右, 找到一个比key大的元素 tmpL, tmpL的位置为 j , [right] = tmpL, 此时 j 也空出来了.
3. 重复以上两步, 直到left >= right.
具体过程如下图:
代码如下:
public static void quickSort(int[] array) {quick2(array,0,array.length-1);}private static void quick2(int[] array,int start,int end) {if(start >= end) return;int pivot = partition2(array,start,end);quick2(array,start,pivot-1);quick2(array,pivot+1,end);}
private static int partition2(int[] array,int left,int right) {int key = array[left];while(left < right) {while(left < right && array[right] >= key) {right--;}//从右边开始第一个比key小的元素覆盖[left]array[left] = array[right];while(left < right && array[left] <= key) {left++;}//从左边开始第一个比key大的元素覆盖空位.array[right] = array[left];}//key填补最终的空位,此时left=rightarray[left] = key;return left;}
2.2.3 前后指针法(了解):
自行画图即可:
代码如下:
public static void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
private static int partition(int[] array, int left, int right) {
int prev = left ;
int cur = left+1;
while (cur <= right) {
if(array[cur] < array[left] && array[++prev] != array[cur]) {
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,left);
return prev;
}
递归快排模拟动图
2.2.4 快速排序的递归优化:
1. 当数据量很大的待排序数组本身是有序的时候, 递归快排会出现单分支的情况, 此时递归的次数最多, 所需的空间也最多, 怎么减小空间消耗呢?
在递归快排之前, 先对待排序数组进行三数取中操作
三数取中: 拿出数组首尾中三个元素值, 取这三个数的中间值与0下标的值进行交换.
三数取中代码实现:
//三数取中.private static int midOfThree(int[] array, int left, int right) {int mid = (left+right)/2;if(array[right] > array[left]) {if(array[mid] < array[left]) {return left;}else if(array[mid] > array[right]) {return right;}else {return mid;}}else {if(array[mid] > array[left]) {return left;}else if(array[mid] < array[right]) {return right;}else {return mid;}}}public static void quickSort(int[] array) {quick2(array,0,array.length-1);}private static void quick2(int[] array,int start,int end) {if(start >= end) return;//三数取中,优化空间复杂度int index = midOfThree(array,start,end);//三数取中,swap(array,index,start);//start下标数与中间数交换,确保start下标 是中间大的数.int pivot = partition2(array,start,end);quick2(array,start,pivot-1);quick2(array,pivot+1,end);}private static int partition2(int[] array,int left,int right) {int key = array[left];while(left < right) {while(left < right && array[right] >= key) {right--;}//从右边开始第一个比key小的元素覆盖[left]array[left] = array[right];while(left < right && array[left] <= key) {left++;}//从左边开始第一个比key大的元素覆盖空位.array[right] = array[left];}//key填补最终的空位,此时left=rightarray[left] = key;return left;}
2.递归快排的第二次优化:
//第二次优化快速排序.//递归得差不多了之后,使用直接插入排序效率可能会更高.public static void insertSortRange(int[] array,int begin,int end) {for (int i = begin+1; i <= end; i++) {int tmp = array[i];int j = i-1;for (; j >= begin; j--) {if(array[j] > tmp) { // >= 会变成不稳定的array[j+1] = array[j];}else {//array[j+1] = tmp; 执行了一次break;}}//当j=-1时,a[j+1]=tmp这条语句没被执行,所以再写一次array[j+1] = tmp; //执行了两次, 故把第一次屏蔽.}}public static void quickSort(int[] array) {quick2(array,0,array.length-1);}private static void quick2(int[] array,int start,int end) {if(start >= end) return;//第二次优化快速排序法.减少递归的次数,但是不一定是优化,可能反而会变慢.if(end - start+1 <= 15) {//直接插入排序insertSortRange(array,start,end);return;}//三数取中,优化空间复杂度int index = midOfThree(array,start,end);//三数取中,swap(array,index,start);//start下标数与中间数交换,确保start下标 是中间大的数.int pivot = partition2(array,start,end);quick2(array,start,pivot-1);quick2(array,pivot+1,end);}
以递归快排的整体代码如下(以Hoare版为例):
public static void quickSort(int[] array) {quick2(array,0,array.length-1);}private static void quick2(int[] array,int start,int end) {if(start >= end) return;//第二次优化快速排序法.减少递归的次数,但是不一定是优化,可能反而会变慢.if(end - start+1 <= 15) {//直接插入排序insertSortRange(array,start,end);return;}//三数取中,优化空间复杂度int index = midOfThree(array,start,end);//三数取中,swap(array,index,start);//start下标数与中间数交换,确保start下标 是中间大的数.int pivot = partition2(array,start,end);quick2(array,start,pivot-1);quick2(array,pivot+1,end);}private static int partition2(int[] array,int left,int right) {int key = array[left];while(left < right) {while(left < right && array[right] >= key) {right--;}//从右边开始第一个比key小的元素覆盖[left]array[left] = array[right];while(left < right && array[left] <= key) {left++;}//从左边开始第一个比key大的元素覆盖空位.array[right] = array[left];}//key填补最终的空位,此时left=rightarray[left] = key;return left;}//递归快排的第一次优化: 三数取中.private static int midOfThree(int[] array, int left, int right) {int mid = (left+right)/2;if(array[right] > array[left]) {if(array[mid] < array[left]) {return left;}else if(array[mid] > array[right]) {return right;}else {return mid;}}else {if(array[mid] > array[left]) {return left;}else if(array[mid] < array[right]) {return right;}else {return mid;}}}//第二次优化快速排序.//递归得差不多了之后,使用直接插入排序效率更高.public static void insertSortRange(int[] array,int begin,int end) {for (int i = begin+1; i <= end; i++) {int tmp = array[i];int j = i-1;for (; j >= begin; j--) {if(array[j] > tmp) { // >= 会变成不稳定的array[j+1] = array[j];}else {//array[j+1] = tmp; 执行了一次break;}}//当j=-1时,a[j+1]=tmp这条语句没被执行,所以再写一次array[j+1] = tmp; //执行了两次, 故把第一次屏蔽.}}
快速排序的非递归实现在下篇 ↓
以上就是本篇文章的全部内容啦! 七大排序的难点在于理解, 只要理解了并且自己画图,写代码, 那么相信这一块就没什么太大的问题啦,
感谢观看, 希望我们都能在排序的学习之路上 秒杀"OJ排序题" .
相关文章:

数据结构-8.Java. 七大排序算法(中篇)
本篇博客给大家带来的是排序的知识点, 由于时间有限, 分两天来写, 中篇主要实现后三种排序算法: 冒泡排序,快速排序,下一篇讲 归并排序. 文章专栏: Java-数据结构 若有问题 评论区见 欢迎大家点赞 评论 收藏 分享 如果你不知道分享给谁,那就分享给薯条. 你们的支持是我不断创作…...

数据结构C语言描述4(图文结合)--栈的实现,中序转后序表达式的实现
前言 这个专栏将会用纯C实现常用的数据结构和简单的算法;有C基础即可跟着学习,代码均可运行;准备考研的也可跟着写,个人感觉,如果时间充裕,手写一遍比看书、刷题管用很多,这也是本人采用纯C语言…...
python基本数据类型 -- 元组tuple
在 Python 中,元组(Tuple)是一种轻量级的、不可变的数据结构。与列表类似,元组用于存储有序的数据集合,但它一旦创建,其内容就无法更改。这种特性让元组在某些场景下更加安全和高效。本文将从定义、操作、应…...

tcpdump交叉编译
TCPDUMP在Libpcap上开发。 首先需要编译libcap。 网上那么多教程,下载地址都只给了一个英文的官网首页, 你尽可以试试,从里面找到下载地址都要费半天时间。 \color{red}网上那么多教程,下载地址都只给了一个英文的官网首页&#…...
Spring IOC注入方式、Bean作用域
Spring IOC注入 手动注入 set方法注入 需要提供set方法 public class UserService {private UserDao userDao; public void setUserDao(UserDao userDao) {this.userDao userDao;} } 设置属性字段的值 <bean id"userService" class"com.shsxt.servi…...

uniapp微信小程序转发跳转指定页面
onShareAppMessage 是微信小程序中的一个重要函数,用于自定义转发内容。当用户点击右上角的菜单按钮,并选择“转发”时,会触发这个函数。开发者可以在这个函数中返回一个对象,用于定义分享卡片的标题、图片、路径等信息。 使用场…...

利用uniapp开发鸿蒙:运行到鸿蒙模拟器—踩坑合集
从uniapp运行到鸿蒙模拟器上这一步,就有非常多的坑,一些常见的坑,官网都有介绍,就不再拿出来了,这里记录一下官网未记录的大坑 1.运行路径从hbuilderx启动鸿蒙模拟器 解决方法: Windows系统,官…...

【Vue】Vue3.0(二十五)Vue3.0中的具名插槽 的概念和使用场景
上篇文章 【Vue】Vue3.0(二十四)Vue3.0中 r e f s 、 refs 、 refs、parent 的概念和使用场景 🏡作者主页:点击! 🤖Vue专栏:点击! ⏰️创作时间:2024年11月20日16点30分 …...
【pytorch-02】:张量的索引、形状操作和常见运算函数
文章目录 1 张量索引1.1 简单行列索引和列表索引1.2 布尔索引和多维索引 2 张量的形状操作2.1 reshape函数2.2 transpose和permute函数的使用2.3 view和contiguous函数2.4 squeeze和unsqueeze函数用法2.5 张量更改形状小结 3 常见运算函数 1 张量索引 1.1 简单行列索引和列表索…...

C语言-指针作为函数返回值及二级指针
1、指针作为函数返回值 c语言允许函数的返回值是一个指针(地址)我们将这样的函数称为指针函数,下面的例子定义一了一个函数strlong(),用来返回两个字符串中较长的一个: 1. #include <stdio…...

css 使用图片作为元素边框
先看原始图片 再看效果 边框的四个角灭有拉伸变形,但是图片的中部是拉伸的 代码 border-style: solid;/* 设置边框图像的来源 */border-image-source: url(/static/images/mmwz/index/bk_hd3x.png);/* 设置如何切割图像 */border-image-slice: 66;/* 设置边框的宽度 */border…...
Linux无sudo权限将zsh作为默认shell
由于我只有用户权限,没有sudo权限,将zsh作为用户默认shell需要密码,所以没法在系统层面进行操作,下面另寻他法。 安装zsh 可以根据网上教程去安装zsh,一般电脑上会带有zsh,可以使用下述命令查看是否安装z…...
【React 进阶】掌握 React18 全部 Hooks
一、数据更新驱动 1. useState 1. 基础介绍 useState主要用于声明和操作状态变量,可以使函数组件像类组件一样拥有state const [state, setState] useState(initialState);state:状态,作为渲染视图的数据源 setState:改变st…...

【卡尔曼滤波】数据预测Prediction观测器的理论推导及应用 C语言、Python实现(Kalman Filter)
【卡尔曼滤波】数据预测Prediction观测器的理论推导及应用 C语言、Python实现(Kalman Filter) 更新以gitee为准: 文章目录 数据预测概念和适用方式线性系统的适用性 数据预测算法和卡尔曼滤波公式推导状态空间方程和观测器先验估计后验估计…...

【SQL50】day 2
目录 1.每位经理的下属员工数量 2.员工的直属部门 3.判断三角形 4.上级经理已离职的公司员工 5.换座位 6.电影评分 7.修复表中的名字 8.患某种疾病的患者 9.删除重复的电子邮箱 1.每位经理的下属员工数量 # Write your MySQL query statement below #e1是经理,…...
【内存管理】理解 `WeakReference` 以更好地管理 Android 应用中的内存
在 Android 应用开发中,内存管理至关重要。糟糕的内存管理可能导致“内存泄漏”,即一些不再需要的对象仍然留在内存中,最终导致性能下降,甚至应用崩溃。WeakReference 就是帮助解决这个问题的一种工具。在本文中,我们将…...

解决IDEA中Maven管理界面不是层级结构的问题
文章目录 0. 前言1. 点击Maven管理界面右上角的三个点2. 勾选将模块分组3. 分组后的层级结构 更多 IDEA 的使用技巧可查看 IDEA 专栏中的文章:IDEA 0. 前言 在 IDEA 中,如果项目中有很多子模块,每个子模块中又有一个或多个子模块时…...

Linux运维篇-iscsi存储搭建
目录 概念实验介绍环境准备存储端软件安装使用targetcli来管理iSCSI共享存储 客户端软件安装连接存储 概念 iSCSI是一种在Internet协议上,特别是以太网上进行数据块传输的标准,它是一种基于IP Storage理论的存储技术,该技术是将存储行业广泛…...

深度学习基础练习:代码复现transformer重难点
2024/11/10-2024/11/18: 主要对transformer一些比较难理解的点做了一些整理,希望对读者有所帮助。 前置知识: 深度学习基础练习:从pytorch API出发复现LSTM与LSTMP-CSDN博客 【神经网络】学习笔记十四——Seq2Seq模型-CSDN博客 【官方双语】一…...

141. Sprite标签(Canvas作为贴图)
上节课案例创建标签的方式,是把一张图片作为Sprite精灵模型的颜色贴图,本节给大家演示把Canvas画布作为Sprite精灵模型的颜色贴图,实现一个标签。 注意:本节课主要是技术方案讲解,默认你有Canvas基础,如果没有Canvas基…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...

自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...