冒泡排序和选择排序的实例、区别、优缺点
冒泡排序:从左到右,数组中相邻的两个元素进行比较,将较大的放到后面。
我们从下面这个例子中去学习下冒泡排序;
例如:有一个int [] a={2,6,5,3,1};
这个就是用冒泡排序的思路进行的第一轮排序:从图中可以看出第一轮比较了4次。
第二轮排序开始时数组已经变成{2,5,3,1,6};
因为第一轮已经确定6的位置,所以,第二轮就不需要和6比较了,从图可以看出,第二轮比较,比较了3次,确定了5的位置;
第三轮排序开始时的数组已经变成了{2,3,1,5,6};
同理,第三轮就不需要去与5进行比较了,从图可以看出,第三轮比较了2次,确定了3的位置。
第四轮排序开始时的数组已经变成了{2,1,3,5,6};
第4轮比较完之后,这组数就已经完全排好了顺序,接下来就需要找规律,实现以下代码:
public class Sequence_Bubble {
public static void main(String[] args) {
int []arr={2,6,5,3,1};//举例的数组
//由图看出,总计4轮,所以arr.length-1
for (int i = 0; i <arr.length-1 ; i++) {//外层循环,控制比较轮数
//每一轮的比较次数相比上一轮要减1,所以arr.length-1-i
for (int j = 0; j <arr.length-1-i ; j++) {//内层循环,控制每轮的比较次数
if (arr[j]>arr[j+1]){//比较相邻位置的两个数
//交换位置
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
//循环遍历经过排序后的最终的数组
for (int i = 0; i <arr.length ; i++) {
System.out.println(arr[i]);
}
}
}
选择排序:从第一个位置开始比较,找出最小的,和第一个位置互换,开始下一轮。
我们同样,以上面的例子为例 int [] a= {2,6,5,3,1};
从图可以看出,第一轮比较,比较了4轮,找出了最小数1,与第一个位置的数字进行了换位;
第二轮排序开始时的数组已经变成了{1,6,5,3,2};
从图可以看出,第二轮比较,比较了3次,确定剩余数中的最小数为2,与第二个位置的数交换。
第三轮排序开始时的数组已经变成了{1,2,5,3,6};
从图可以看出,第三轮比较,比较了2次,确定了剩余数中最小的数3,与第三个位置的数互换位置。
第四轮排序开始时的数组已经变成了{1,2,3,5,6};
从图可以看出,第四轮比较,比较了1次,确定了剩余数中最小的数5,放在了第4个位置。
这样4轮比较后,这组数已经排序好了,接下来同上,去找规律,实现代码了:
public class Sequence_Choose {
public static void main(String[] args) {
int []arr={2,6,5,3,1};
for (int i = 0; i <arr.length-1 ; i++) {//外循环控制比较轮数
int min=i;//假设min为最小值对应的索引
//每一轮开始先和后一个开始比较,所以i+1
for (int j = i+1; j <arr.length ; j++) {//内循环控制每轮比较的次数
if (arr[j]<arr[min]){
min=j;
}
}
//找出最小值后,进行元素交换
if (min!=i){//如果最小值的索引不是假设的索引,需要交换位置
int temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
for (int i = 0; i <arr.length ; i++) {//遍历输出经过选择排序后的数组
System.out.print(arr[i]+"\t");
}
}
}
二者区别:
(1)冒泡排序是比较相邻位置的两个数,而选择排序是按顺序比较,找最大值或者最小值;
(2)冒泡排序每一轮比较后,位置不对都需要换位置,选择排序每一轮比较都只需要换一次位置;
(3)冒泡排序是通过数去找位置,选择排序是给定位置去找数;
**冒泡排序优缺点:**优点:比较简单,空间复杂度较低,是稳定的;
缺点:时间复杂度太高,效率慢;
**选择排序优缺点:**优点:一轮比较只需要换一次位置;
缺点:效率慢,不稳定(举个例子5,8,5,2,9 我们知道第一遍选择第一个元素5会和2交换,那么原序列中2个5的相对位置前后顺序就破坏了)。
本文地址:https://blog.csdn.net/IT_LD/article/details/107368648
上一篇: 最常用的PHP正则表达式收集整理
下一篇: 趣图鬼斧神工之作品