手把手教你搞懂冒泡排序和选择排序
作者:小胖java攻城狮 时间:2022-05-08 23:08:34
冒泡排序
原理:
从头(左边)开始比较每一对相邻的元素,如果第1个比第2个大,就交换它们的位置,执行完一轮后,最末尾(最右边)就是最大的元素。
举例:
假设存在数组nums={6,8,2,9,4},对nums数组进行排序
从左往右开始,拿出两个元素进行对比,出现两种情况:
1.左边元素 <= 右边元素,不变
2.左边元素 > 右边元素,交换他们的位置(这里可以写成>=吗?不行,因为会造成排序不稳定)
接下来就是新的一轮排序,逻辑跟上图的流程是一样的,不同的是会将最大的元素排除在外,不用进行比较。
手撕代码:
/*
没有使用过优化策略的冒泡排序
*/
public class BubbleSort1 {
//测试数据
public static int[] nums = {4,1,7,11,9,55};
//main方法
public static void main(String[] args){
//这个for循环每循环完一次,end--,说明就把最大的元素给选出来了
for (int end = nums.length - 1; end > 0; end--){
for (int begin = 1; begin <= end; begin++){
if(nums[begin] < nums[begin - 1]){ //每当发现左边的元素大于右边的元素
//交换元素
int temp = nums[begin];
nums[begin] = nums[begin - 1];
nums[begin - 1] = temp;
}
}
}
//打印验证结果
for(int num : nums){
System.out.print(num+"_");
}
}
}
时间复杂度为O(n^2),
也就是n的平方,不过这是平均时间复杂度
存在最好时间复杂度O(n)
,那就是数组本来就有序,也就是说只扫描一遍就行了。
优化策略:
由于存在部分有序的情况,例如nums数组为{8,5,2,10,11,12},也就是说10,11,12都没有比较的必要了
优化代码:
/*
使用过优化策略的冒泡排序
*/
public class BubbleSort1 {
public static int[] nums = {4,1,7,11,9,55};
public static void main(String[] args){
for (int end = nums.length - 1; end > 0; end--){
int sortIndex = 1; //记录最后一次交换位置
for (int begin = 1; begin <= end; begin++){
if(nums[begin] < nums[begin - 1]){
int temp = nums[begin - 1];
nums[begin - 1] = nums[begin];
nums[begin] = temp;
sortIndex = begin;
}
end = sortIndex;
}
}
for(int num : nums){
System.out.print(num+"_");
}
}
}
选择排序
原理:
从数组中找到最大的元素,然后与末尾(最右边)的元素交换位置,执行完一轮后,末尾(最右边)的那个元素就是最大的元素。
举例:
假设存在数组nums={5,8,1,9,3},对nums数组进行排序,准备一个maxIdex代表当前最大元素的下标
接下来就是新的一轮排序,逻辑跟上图的流程是一样的,不同的是会将最大的元素排除在外,不用进行比较。
手撕代码:
/**
* 选择排序
*/
public class SelectionSort {
//测试数据
private static int[] nums = {6,3,2,8,9};
//main方法
public static void main(String[] args){
//这个for循环每循环完一次,end--,说明就把最大的元素给选出来了
for(int end = nums.length - 1; end > 0; end--){
int maxIndex = 0; //假设下标0是数组中最大元素
for(int begin = 1; begin <= end; begin++){ //从左往右开始比较
if(nums[maxIndex] < nums[begin]){ //发现存在一个元素大于假设最大元素
maxIndex = begin; //更改最大元素索引
}
}
//最右边一个元素和最大值元素交换位置
int temp = nums[maxIndex];
nums[maxIndex] = nums[end];
nums[end] = temp;
}
//打印结果
for(int num : nums){
System.out.print(num+"_");
}
}
}
来源:https://blog.csdn.net/qq_45798556/article/details/116936068
标签:冒泡排序,选择排序
0
投稿
猜你喜欢
Spring Cloud Config配置文件使用对称加密的方法
2021-08-09 08:50:02
java中transient关键字用法分析
2022-01-22 04:27:05
eclipse下配置Spring环境的方法步骤
2023-02-27 20:39:26
Java实现数据库连接池的方法
2023-11-28 08:57:30
Java抽象类与接口区别详解
2021-06-19 19:22:37
C#实现关闭其他程序窗口或进程代码分享
2022-05-26 07:38:03
浅谈Java字符串比较的三种方法
2023-05-13 12:26:51
浅谈Java中实现深拷贝的两种方式—clone() & Serialized
2022-04-05 18:36:15
一文搞懂MyBatis多数据源Starter实现
2023-07-19 03:34:22
Java中关于MouseWheelListener的鼠标滚轮事件详解
2023-10-19 02:02:54
java实现学籍管理系统
2023-04-03 00:32:19
Android开发中使用颜色矩阵改变图片颜色,透明度及亮度的方法
2023-04-28 20:42:22
利用Spring boot+LogBack+MDC实现链路追踪
2023-10-03 16:02:53
示例解析java重载Overloading与覆盖Overriding
2021-11-03 17:22:19
SpringBoot整合MybatisPlus的教程详解
2023-12-06 18:05:20
C#微信开发之微信公众号标签管理功能
2023-04-17 20:20:44
Java并发控制机制详解
2022-12-12 22:07:56
Android实现毛玻璃效果的对话框
2021-07-19 03:28:42
SpringBoot利用切面注解及反射实现事件监听功能
2022-09-25 16:55:00
c#实现16进制和字符串之间转换的代码
2023-07-22 08:28:09