手把手教你搞懂冒泡排序和选择排序

手把手教你搞懂冒泡排序和选择排序

目录冒泡排序原理：选择排序原理：总结

冒泡排序

原理：

从头（左边）开始比较每一对相邻的元素，如果第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代表当前最大元素的下标

接下来就是新的一轮排序，逻辑跟上图的流程是一样的，不同的是会将最大的元素排除在外，不用进行比较。

手撕代码：

/*oeOLM*

* 选择排序

*/

public class Selhttp://ectionSort {

//测试数据

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+"_");

}

}

}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多文章！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。