冒泡排序
原理：
从头（左边）开始比较每一对相邻的元素，如果第1个比第2个大，就交换它们的位置，执行完一轮后，最末尾（最右边）就是最大的元素。
举例：
假设存在数组nums={6，8，2，9，4}，对nums数组进行排序
从左往右开始，拿出两个元素进行对比，出现两种情况：
1.左边元素 <= 右边元素，不变
2.左边元素 > 右边元素，交换他们的位置（这里可以写成>=吗？不行，因为会造成排序不稳定）
接下来就是新的一轮排序，逻辑跟上图的流程是一样的，不同的是会将最大的元素排除在外，不用进行比较。
手撕代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/* 没有使用过优化策略的冒泡排序 */ 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都没有比较的必要了
优化代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
/* 使用过优化策略的冒泡排序 */ 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代表当前最大元素的下标
接下来就是新的一轮排序，逻辑跟上图的流程是一样的，不同的是会将最大的元素排除在外，不用进行比较。
手撕代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
/** * 选择排序 */ 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
查看更多关于手把手教你搞懂冒泡排序和选择排序的详细内容...