Java数据结构第二十期：解构排序算法的艺术与科学(二)

专栏：Java数据结构秘籍

个人主页：手握风云

目录

一、常见排序算法的实现

1.1. 直接选择排序

1.2. 堆排序

1.3. 冒泡排序

1.4. 快速排序

一、常见排序算法的实现

1.1. 直接选择排序

        每⼀次从待排序的数据元素中选出最小的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。第一轮，先让j下标遍历出数组中最小的元素，再利用MinIndex存放最小的下标，利用最小值与i下标的元素进行交换；第二轮，依然让j下标遍历出待排序中最小的元素，再利用MinIndex存放最小的下标，利用最小值与i下标的元素进行交换……知道i走到最后一个元素，这样就能保证i之前的元素全部是有序的。

import java.util.Random;public class Sort {public void SelectSort(int[] array){for (int i = 0; i < array.length; i++) {int MinIndex = i;for (int j = i+1; j < array.length; j++) {if(array[MinIndex] > array[j]){MinIndex = j;}}swap(array,MinIndex,i);}}private void swap(int[] array,int i,int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}public void DisOrder(int[] array) {Random ran = new Random();for (int i = 0; i < array.length; i++) {array[i] = ran.nextInt(100);}}
}
import java.util.Arrays;public class Test {public static void main(String[] args) {int[] array = new int[6];Sort sort = new Sort();sort.DisOrder(array);System.out.println("排序前：" + Arrays.toString(array));sort.SelectSort(array);System.out.println("排序后："+Arrays.toString(array));}
}

        直接选择排序是不稳定的。空间上，没有使用额外的空间，空间复杂度为O(n) =1。时间上，

        直接选择排序还有另外一种思路。与上面的方法不同的是，我们需要两个值MinIndex接收最小值下标和MaxIndex来接收最大值下标，再额外定义两个指针left和right。这种选择排序的思路是从首尾找，起始两个值接收下标都为0，利用i去遍历数组，找出最大值与最小值下标，再让left下标的值与MinIndex下标的值交换，right下标的值与MaxIndex下标的值交换。接着再让left向左移动，right向右移动，直到相遇，循环结束

        完整代码实现：

import java.util.Random;public class Sort {public void DisOrder(int[] array) {Random ran = new Random();for (int i = 0; i < array.length; i++) {array[i] = ran.nextInt(100);}}public void SelectSort(int[] array) {int left = 0, right = array.length - 1;while (left < right) {int MinIndex = left, MaxIndex = left;for (int i = left + 1; i <= right; i++) {if (array[i] < array[MinIndex]) {MinIndex = i;}if (array[i] > array[MaxIndex]) {MaxIndex = i;}}swap(array, MinIndex, left);swap(array, MaxIndex, right);left++;right--;}}private void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
}
import java.util.Arrays;public class Test {public static void main(String[] args) {Sort sort = new Sort();int[] array = new int[6];sort.DisOrder(array);System.out.println("排序前：" + Arrays.toString(array));sort.SelectSort(array);System.out.println("排序后：" + Arrays.toString(array));}
}

        但我们一运行，就会发现，排序出现了问题，这是因为，如果最大值或最小值本身就在首尾，那么一交换，最大值或最小值就会跑掉，，所以我们还需要判断一下。

import java.util.Random;public class Sort {public void DisOrder(int[] array) {Random ran = new Random();for (int i = 0; i < array.length; i++) {array[i] = ran.nextInt(100);}}public void SelectSort(int[] array) {int left = 0, right = array.length - 1;while (left < right) {int MinIndex = left, MaxIndex = left;for (int i = left + 1; i <= right; i++) {if (array[i] < array[MinIndex]) {MinIndex = i;}if (array[i] > array[MaxIndex]) {MaxIndex = i;}}swap(array, MinIndex, left);/*if (left == MaxIndex) {MaxIndex = MinIndex;}*/swap(array, MaxIndex, right);left++;right--;}}private void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
}
import java.util.Arrays;public class Test {public static void main(String[] args) {Sort sort = new Sort();int[] array = new int[6];sort.DisOrder(array);System.out.println("排序前：" + Arrays.toString(array));sort.SelectSort(array);System.out.println("排序后：" + Arrays.toString(array));}
}

1.2. 堆排序

        堆排序是指利⽤堆积树这种数据结构所设计的⼀种排序算法，它是选择排序的⼀ 种，通过堆来进⾏选择数据。需要注意的是排升序要建大堆，排降序建小堆。

import java.util.Random;public class Sort {public void HeapSort(int[] array) {CreateHeap(array);int end = array.length - 1;while(end > 0){swap(array,0,end);ShiftDown(array,0,end);end--;}}private void CreateHeap(int[] array) {for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {ShiftDown(array, parent, array.length);}}private void ShiftDown(int[] array, int parent, int length) {int child = 2 * parent + 1;while (child < length) {if (child + 1 < length && array[child] < array[child + 1]) {child++;}if (array[child] > array[parent]) {swap(array,parent,child);parent = child;child = 2 * parent + 1;} else {break;}}}private void swap(int[] array,int i,int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}public void DisOrder(int[] array){Random ran = new Random();for (int i = 0; i < array.length; i++) {array[i] = ran.nextInt(1,100);}}
}
import java.util.Arrays;public class Solution {public static void main(String[] args) {Sort sort = new Sort();int[] array = new int[6];sort.DisOrder(array);System.out.println("排序前："+ Arrays.toString(array));sort.HeapSort(array);System.out.println("排序前："+ Arrays.toString(array));}
}

        堆排序使⽤堆来选数，效率就⾼了很多。但堆排序是不稳定的，时间复杂度为O(n)=nlogn，空间复杂度为O(n)=1。

1.3. 冒泡排序

        定义下标j，比较array[j]与array[j+1]的值，如果array[j] > array[j+1]，则交换两数的位置。我们还可以进行一个优化，如果数组本身就是有序，或者没有走完所有的趟数就已经有序，那么后面就不用再比较了。

import java.util.Random;public class Sort {public void DisOrder(int[] array) {Random ran = new Random();for (int i = 0; i < array.length; i++) {array[i] = ran.nextInt(1, 100);}}public void BubbleSort(int[] array) {//表示交换的趟数for (int i = 0; i < array.length-1; i++) {boolean flg = false;for (int j = 0; j < array.length-1-i; j++) {if(array[j] > array[j+1]){swap(array,j,j+1);flg = true;}}if(!flg){break;}}}private void swap(int[] array,int i,int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}
}
import java.util.Arrays;public class Test {public static void main(String[] args) {Sort sort = new Sort();int[] array = new int[6];sort.DisOrder(array);System.out.println("排序前："+Arrays.toString(array));sort.BubbleSort(array);System.out.println("排序后："+Arrays.toString(array));}
}

        冒泡排序是稳定的。时间复杂度：O(n)=n^{2}，空间复杂度：O(n)=1。

1.4. 快速排序

        快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素 序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列。

        我们需要定义两个指针left和right，假设以6作为基准值，left向左移动，遇到比6大的数停下；right向右移动，遇到比6小的数停下，然后交换两个元素。当两个指针相遇时，再与基准值进行交换。这样就能保证6左边都是比6小的数，6右边都是比6大的数。按照这个过程再次进行，，构成递归的条件，直到分离出只含一个值的子序列。这样就构成了如下图所示的二叉树结构。

public class Sort {public void QuickSort(int[] array){}public void Quick(int[] array,int start,int end){if(start >= end){//如果结点的右子树为空，就不用遍历右边return;}int par = partition(array,start,end);Quick(array,start,par-1);Quick(array,par+1,end);//当start==end时，递归条件结束}private int partition(int[] array, int left, int right) {return -1;}
}

        我们接下来要思考的问题是如何写partition这个方法。无论是递归左边还是右边，与上面的过程都是一样的。只要left下标的值比基准值小，left右移；只要right下标的值比基准值大，right右移。这里我们还需要注意里层的while循环，指针不能越界。

    private int partition(int[] array, int left, int right) {int i = left;int tmp = array[left];while(left < right){while(left < right && array[right] >= tmp){right--;}while(left < right && array[left] <= tmp){left++;}swap(array,left,right);}swap(array,left,i);return left;}

        完整代码实现：

import java.util.Random;public class Sort {public void DisOrder(int[] array){Random ran = new Random();for (int i = 0; i < array.length; i++) {array[i] = ran.nextInt(1,40);}}public void QuickSort(int[] array){Quick(array,0,array.length-1);}public void Quick(int[] array,int start,int end){if(start >= end){//如果结点的右子树为空，就不用遍历右边return;}int par = partition(array,start,end);Quick(array,start,par-1);Quick(array,par+1,end);//当start==end时，递归条件结束}private int partition(int[] array, int left, int right) {int i = left;int tmp = array[left];while(left < right){while(left < right && array[right] >= tmp){right--;}while(left < right && array[left] <= tmp){left++;}swap(array,left,right);}swap(array,left,i);return left;}private void swap(int[] array,int i,int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}
}
import java.util.Arrays;public class Test {public static void main(String[] args) {Sort sort = new Sort();int[] array = new int[6];sort.DisOrder(array);System.out.println("排序前："+Arrays.toString(array));sort.QuickSort(array);System.out.println("排序后："+Arrays.toString(array));}
}

        这里解释一下为什么先让right移动，防止越过某些值。这里我们还需要注意，>=或<=的等号不能省略，如果left和right的值与基准值相等，那么就不会进入内层的while循环，导致外层的while循环陷入死循环。

        快速排序是不稳定的。快速排序的时间复杂度通常是指最好情况下，因为我们经常对快速排序进行优化。

        快速排序还有一种做法——挖坑法。与上面的方法类似，我们依然是以6为基准值，把6存进tmp中，right向左移动，遇到比6小的数，把6之前的位置填上；left向右移动，遇到比6大的数，把5之前的位置填上……我们只需要对上面的代码进行修改就可以。

import java.util.Random;public class Sort {public void DisOrder(int[] array){Random ran = new Random();for (int i = 0; i < array.length; i++) {array[i] = ran.nextInt(1,40);}}public void QuickSort(int[] array){Quick(array,0,array.length-1);}public void Quick(int[] array,int start,int end){if(start >= end){//如果结点的右子树为空，就不用遍历右边return;}int par = partition(array,start,end);Quick(array,start,par-1);Quick(array,par+1,end);//当start==end时，递归条件结束}private int partition(int[] array, int left, int right) {int i = left;int tmp = array[left];while(left < right){while(left < right && array[right] >= tmp){right--;}array[left] = array[right];while(left < right && array[left] <= tmp){left++;}array[right] = array[left];}array[left] = tmp;return left;}}

import java.util.Arrays;public class Test {public static void main(String[] args) {Sort sort = new Sort();int[] array = new int[6];sort.DisOrder(array);System.out.println("排序前："+ Arrays.toString(array));sort.QuickSort(array);System.out.println("排序后："+ Arrays.toString(array));}
}

        我们接下来思考一下快排的优化。我们先来看第一种三数取中法。我们找出start和end的中位数，让二叉树的形状尽量不要出现单分支的情况。那我们怎么再这段区间里面去找中位数呢？我们可以通过下标来找

    private static int midNum(int[] array, int left, int right) {int mid = (left+right)/2;if(array[left] < array[right]) {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;}}}

        第二种，递归到⼩的⼦区间时，可以考虑使⽤插⼊排序。

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

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

相关文章

【MapSet】哈希表

【MapSet】哈希表

目录 1. 搜索树 1.1 概念 1.2 操作-查找 1.3 操作-插入 1.4 操作-删除&#xff08;难点&#xff09; 1.5 性能分析 1.6 和java类集的关系 2. 搜索 2.1 概念及场景 2.2 模型 3. Map的使用 3.1 关于Map的说明 3.2 关于Map.Entry的说明 3.3 Map的常用方法说明 3.4 …
阅读更多...
手写一个Tomcat

手写一个Tomcat

Tomcat 是一个广泛使用的开源 Java Servlet 容器&#xff0c;用于运行 Java Web 应用程序。虽然 Tomcat 本身功能强大且复杂&#xff0c;但通过手写一个简易版的 Tomcat&#xff0c;我们可以更好地理解其核心工作原理。本文将带你一步步实现一个简易版的 Tomcat&#xff0c;并深…
阅读更多...
git commit messege 模板设置 (规范化管理git)

git commit messege 模板设置 (规范化管理git)

配置方法 git config --global core.editor vim &#xff08;设置 Git 的默认编辑器为 Vim&#xff09;在用户根目录下&#xff08;~&#xff09;&#xff0c;创建一个.git_commit_msg文件&#xff0c;然后把下面的内容拷贝到文件中并保存。 [version][模块][类型]{解决xxx问题…
阅读更多...
亚信安全发布第七期《勒索家族和勒索事件监控报告》

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

本周态势快速感知 本周全球共监测到勒索事件121起&#xff0c;与上周相比&#xff0c;勒索事件数量大幅下降&#xff0c;仍需注意防范。从整体上看Clop是影响最严重的勒索家族&#xff1b;本周Ransomhub和Akira也是活动频繁的两个恶意家族&#xff0c;需要注意防范。本周&…
阅读更多...
React基础之项目实战

React基础之项目实战

规范的项目结构 安装scss npm install sass -D 安装Ant Design组件库 内置了一些常用的组件 npm install antd --save 路由基础配置 npm i react-router-dom 路由基本入口 import Layout from "../page/Layout"; import Login from "../page/Login"; impor…
阅读更多...
第44天：WEB攻防-PHP应用SQL盲注布尔回显延时判断报错处理增删改查方式

第44天：WEB攻防-PHP应用SQL盲注布尔回显延时判断报错处理增删改查方式

时间轴&#xff1a; 44天知识点总结&#xff1a; 1.mysql的增删改查功能 2.根据源码sql语句的三种sql注入&#xff1a;布尔盲注&#xff08;必须要有回显&#xff09; 延时判断&#xff08;都可以&#xff09; 报错回显&#xff08;必须要有报错处理机制&#xff09; 3.两个cms…
阅读更多...
【51单片机】程序实验15.DS18B20温度传感器

【51单片机】程序实验15.DS18B20温度传感器

主要参考学习资料&#xff1a;B站【普中官方】51单片机手把手教学视频 开发资料下载链接&#xff1a;http://www.prechin.cn/gongsixinwen/208.html 单片机套装&#xff1a;普中STC51单片机开发板A4标准版套餐7 目录 DS18B20介绍主要特性内部结构控制时序初始化时序写时序读时序…
阅读更多...
Vue3 深度解析：构建现代Web应用的全新范式

Vue3 深度解析：构建现代Web应用的全新范式

Vue3 深度解析&#xff1a;构建现代Web应用的全新范式 mindmaproot(Vue3核心革新)性能优化Proxy响应式编译优化体积缩减Composition APIsetup语法逻辑复用TypeScript支持新特性TeleportSuspense片段支持工程化Vite集成自定义渲染器服务端渲染一、Vue3 架构革新&#xff1a;从O…
阅读更多...
推理模型对SQL理解能力的评测：DeepSeek r1、GPT-4o、Kimi k1.5和Claude 3.7 Sonnet

推理模型对SQL理解能力的评测：DeepSeek r1、GPT-4o、Kimi k1.5和Claude 3.7 Sonnet

引言 随着大型语言模型&#xff08;LLMs&#xff09;在技术领域的应用日益广泛&#xff0c;评估这些模型在特定技术任务上的能力变得越来越重要。本研究聚焦于四款领先的推理模型——DeepSeek r1、GPT-4o、Kimi k1.5和Claude 3.7 Sonnet在SQL理解与分析方面的能力&#xff0c;…
阅读更多...
cesium安装与配置（visual studio版）

cesium安装与配置（visual studio版）

文章目录 一、下载Cesium二、解压Cesium三、VS打开网站四、参考文献 如有错误&#xff0c;请指正&#xff01;&#xff01;&#xff01; 一、下载Cesium 登录官网&#xff0c;下载Cesium。 点击箭头所指&#xff0c;下载Cesium 二、解压Cesium 解压Cesium压缩包得到以下文件…
阅读更多...
Netty基础—3.基础网络协议二

Netty基础—3.基础网络协议二

大纲 1.网络基础的相关问题总结 2.七层模型和四层模型 3.物理层(网线 光缆 01电信号) 4.数据链路层(以太网协议 网卡mac地址) 5.网络层(IP协议 子网划分 路由器) 6.传输层(TCP和UDP协议 Socket 端口) 7.应用层(HTTP协议 SMTP协议) 8.浏览器请求一个域名会发生什…
阅读更多...
Linux：Ubuntu server 24.02 上搭建 ollama + dify

Linux：Ubuntu server 24.02 上搭建 ollama + dify

一、安装Ubuntu 具体的安装过程可以参见此链接&#xff1a;链接&#xff1a;Ubuntu Server 20.04详细安装教程&#xff0c;这里主要记录一下过程中遇到的问题。 安装时subnet如何填写 在Ubuntu中subnet填写255.255.255.0是错误的&#xff0c;其格式为 xx.xx.xx.xx/yy &#…
阅读更多...
算法练习——双指针算法(更新中)

算法练习——双指针算法(更新中)

一、介绍双指针算法 双指针&#xff08;或称为双索引&#xff09;算法是一种高效的算法技巧&#xff0c;常用于处理数组或链表等线性数据结构。它通过使用两个指针来遍历数据&#xff0c;从而减少时间复杂度&#xff0c;避免使用嵌套循环。双指针算法在解决诸如查找、排序、去重…
阅读更多...
stm32week6

stm32week6

stm32学习 三.通信 5.硬件读取I2C 硬件读取I2C的代码(main.c与软件读取相同)&#xff1a; #include "stm32f10x.h" // Device header #include "MPU6050_Reg.h"#define MPU6050_ADDRESS 0xD0 //MPU6050的I2C从机地址/*** 函 数&…
阅读更多...
qt+opengl 播放yuv视频

qt+opengl 播放yuv视频

一、实现效果 二、pro文件 Qt widgets opengl 三、主要代码 #include "glwidget.h"GLWidget::GLWidget(QWidget *parent) : QOpenGLWidget(parent) {connect(&m_timer, &QTimer::timeout, this,[&](){this->update();});m_timer.start(1000/33); }v…
阅读更多...
文本对抗样本系列的论文阅读笔记（整理合订）

文本对抗样本系列的论文阅读笔记（整理合订）

文本对抗样本系列的论文阅读笔记 以前调研文本对抗样本时的论文笔记梳理&#xff0c;论文都很经典&#xff0c;有现成的框架&#xff08;TextAttack&#xff09;可以直接用&#xff0c;论文中部分内容直接是截取自论文&#xff0c;所以存在中英混合笔记的情况。 BERT-Attack …
阅读更多...
相对与绝对路径的关系

相对与绝对路径的关系

首先&#xff0c;我们一起来了解相对路径和绝对路径的概念&#xff1a; 相对路径&#xff1a;相对于当前工作目录的路径&#xff0c;不以 / 开头&#xff0c;以一个 ""、./、../、。例如&#xff1a;nginx、./nginx 或 ../nginx绝对路径&#xff1a;从根目录 / 开始…
阅读更多...
java项目之基于ssm的在线学习系统（源码+文档）

java项目之基于ssm的在线学习系统（源码+文档）

项目简介 在线学习系统实现了以下功能&#xff1a; 该系统可以实现论坛管理&#xff0c;通知信息管理&#xff0c;学生管理&#xff0c;回答管理&#xff0c;教师管理&#xff0c;教案管理&#xff0c;公告信息管理&#xff0c;作业管理等功能。 &#x1f495;&#x1f495;作…
阅读更多...
位运算刷题+总结

位运算刷题+总结

文章目录 判定字符是否唯一题解代码 丢失的数字题解代码 两整数之和题解代码 只出现一次的数字 II题解代码 消失的两个数字题解代码 总结 判定字符是否唯一 题目链接 题解 1. 哈希表&#xff0c;创建26个空间大小的哈希表 2. 位图&#xff0c;小写字符只有26个&#xff0c;…
阅读更多...
Qt表格美化笔记

Qt表格美化笔记

介绍 表格是一种常见的数据管理界面形式&#xff0c;在大批量的数据交互情形下使用的比较多 表格 可以通过样式表设置线条以及边框的颜色 QTableWidget { gridline-color : rgb(55, 60, 62); border: 1px solid rgb(62,112,181);}表头 如果表头和第一行的分割线显示&#…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023