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

数据结构-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实现常用的数据结构和简单的算法&#xff1b;有C基础即可跟着学习&#xff0c;代码均可运行&#xff1b;准备考研的也可跟着写&#xff0c;个人感觉&#xff0c;如果时间充裕&#xff0c;手写一遍比看书、刷题管用很多&#xff0c;这也是本人采用纯C语言…...

python基本数据类型 -- 元组tuple

在 Python 中&#xff0c;元组&#xff08;Tuple&#xff09;是一种轻量级的、不可变的数据结构。与列表类似&#xff0c;元组用于存储有序的数据集合&#xff0c;但它一旦创建&#xff0c;其内容就无法更改。这种特性让元组在某些场景下更加安全和高效。本文将从定义、操作、应…...

tcpdump交叉编译

TCPDUMP在Libpcap上开发。 首先需要编译libcap。 网上那么多教程&#xff0c;下载地址都只给了一个英文的官网首页&#xff0c; 你尽可以试试&#xff0c;从里面找到下载地址都要费半天时间。 \color{red}网上那么多教程&#xff0c;下载地址都只给了一个英文的官网首页&#…...

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 是微信小程序中的一个重要函数&#xff0c;用于自定义转发内容。当用户点击右上角的菜单按钮&#xff0c;并选择“转发”时&#xff0c;会触发这个函数。开发者可以在这个函数中返回一个对象&#xff0c;用于定义分享卡片的标题、图片、路径等信息。 使用场…...

利用uniapp开发鸿蒙:运行到鸿蒙模拟器—踩坑合集

从uniapp运行到鸿蒙模拟器上这一步&#xff0c;就有非常多的坑&#xff0c;一些常见的坑&#xff0c;官网都有介绍&#xff0c;就不再拿出来了&#xff0c;这里记录一下官网未记录的大坑 1.运行路径从hbuilderx启动鸿蒙模拟器 解决方法&#xff1a; Windows系统&#xff0c;官…...

【Vue】Vue3.0(二十五)Vue3.0中的具名插槽 的概念和使用场景

上篇文章 【Vue】Vue3.0&#xff08;二十四&#xff09;Vue3.0中 r e f s 、 refs 、 refs、parent 的概念和使用场景 &#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;Vue专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;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语言允许函数的返回值是一个指针&#xff08;地址&#xff09;我们将这样的函数称为指针函数&#xff0c;下面的例子定义一了一个函数strlong&#xff08;&#xff09;&#xff0c;用来返回两个字符串中较长的一个&#xff1a; 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

由于我只有用户权限&#xff0c;没有sudo权限&#xff0c;将zsh作为用户默认shell需要密码&#xff0c;所以没法在系统层面进行操作&#xff0c;下面另寻他法。 安装zsh 可以根据网上教程去安装zsh&#xff0c;一般电脑上会带有zsh&#xff0c;可以使用下述命令查看是否安装z…...

【React 进阶】掌握 React18 全部 Hooks

一、数据更新驱动 1. useState 1. 基础介绍 useState主要用于声明和操作状态变量&#xff0c;可以使函数组件像类组件一样拥有state const [state, setState] useState(initialState);state&#xff1a;状态&#xff0c;作为渲染视图的数据源 setState&#xff1a;改变st…...

【卡尔曼滤波】数据预测Prediction观测器的理论推导及应用 C语言、Python实现(Kalman Filter)

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

【SQL50】day 2

目录 1.每位经理的下属员工数量 2.员工的直属部门 3.判断三角形 4.上级经理已离职的公司员工 5.换座位 6.电影评分 7.修复表中的名字 8.患某种疾病的患者 9.删除重复的电子邮箱 1.每位经理的下属员工数量 # Write your MySQL query statement below #e1是经理&#xff0c;…...

【内存管理】理解 `WeakReference` 以更好地管理 Android 应用中的内存

在 Android 应用开发中&#xff0c;内存管理至关重要。糟糕的内存管理可能导致“内存泄漏”&#xff0c;即一些不再需要的对象仍然留在内存中&#xff0c;最终导致性能下降&#xff0c;甚至应用崩溃。WeakReference 就是帮助解决这个问题的一种工具。在本文中&#xff0c;我们将…...

解决IDEA中Maven管理界面不是层级结构的问题

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

Linux运维篇-iscsi存储搭建

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

深度学习基础练习:代码复现transformer重难点

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

141. Sprite标签(Canvas作为贴图)

上节课案例创建标签的方式&#xff0c;是把一张图片作为Sprite精灵模型的颜色贴图,本节给大家演示把Canvas画布作为Sprite精灵模型的颜色贴图&#xff0c;实现一个标签。 注意&#xff1a;本节课主要是技术方案讲解&#xff0c;默认你有Canvas基础&#xff0c;如果没有Canvas基…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

【磁盘】每天掌握一个Linux命令 - iostat

目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat&#xff08;I/O Statistics&#xff09;是Linux系统下用于监视系统输入输出设备和CPU使…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...