准备好一组数据
private int[] data={12,5,78,33,9,33,11};
思路:依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。
步骤:
1.第一次比较:首先比较第一和第二个数,将小数放在前面,将大数放在后面。
2.比较第2和第3个数,将小数 放在前面,大数放在后面。
...........
重复上步骤,将小数放在前面,大数放在后面,直到比较到最后的两个数,全部排序完成。
3.在上面一趟比较完成后,最后一个数一定是数组中最大的一个数,所以在比较第二趟的时候,最后一个数是不参加比较。
4.在第二趟比较完成后,倒数第二个数也一定是数组中倒数第二大数,所以在第三趟的比较中,最后两个数是不参与比较。
...........
重复上步骤,每一趟比较次数依次减少。
文字千百,不如图一张
第一趟比较完成后,得到数组如下,第二趟比较时,最后一个数78将不参与比较。
第二趟比较完成后,得到数组如下,下一趟,最后两个数33、78将不参与比较。
如此循环,我们将在第五趟,得到排序完成的数组,如下
再来个代码看看吧。
private void maopao_sort(){
int data_length=data.length;
int temp;
for(int i=0;i<data_length-1;i++){//i表示第几趟
boolean IsSort=true;
for(int y=0;y<data_length-i-1;y++){ //j表示遍历比较的次数,每遍历一趟,比较次数都会少一次
if(data[y]>data[y+1]){ //如果前面的数大于后者,则交换。
temp=data[y];
data[y]=data[y+1];
data[y+1]=temp;
IsSort=false;
}
}
System.out.println("遍历第"+i+"次");
if(IsSort){
System.out.println("排序完成"+i+"次");
break;
}
}
for(int i=0;i<data_length;i++){
System.out.println(data[i]);
}
}
算法中有个变量IsSort,用来优化效率,如果已经排序好,那就不需要遍历比较了。
我们可以总结下,N个数字要排序完成,总共进行N-1趟排序,第i趟的排序次数为(N-i)次,所以可以用双重循环语句,外层控制循环多少趟,内层控制每一趟的循环次数。
对包含n个数据的数组进行冒泡排序,最坏情况下,需要进行n*(n-1)/2次交换。最好情况下,无需进行交换。取中间值n*(n-1)/4,表示初始有序的的平均情况。也就是平均情况下需要n*(n-1)/4次交换操作,比较操作肯定要比交换操作多,而这个复杂度的上限是O(n²)。
所以可粗略地认为冒泡排序平均情况下时间复杂度是O(n²)。
思路:在长度为N的无序数组中,第n次遍历N-n个数,找到最小的数值与第n个元素交换
步骤:
1.第一次遍历N个数,找出最小的数与第一个数交换。
2.第二次从第二数个开始,遍历N-1个数,找出最小的数与第二个数交换。
如此循环......
3.直到进行第N-1次遍历,比较最后2个数,判断是否要交换。排序完成。
也来个图吧
第一次遍历,找到最小值5,与第一个数12交换,得到排序数组如下。
第二次遍历,从第二个数也就是12开始遍历,找到最小值9,与数字12交换,得到排序数组如下
如此循环,得到最后排序后的数组如下
我们在配个代码来学习下。
private void select_sort(){
int data_length=data.length;
int temp;
int min_index;
for(int i=0;i<data_length-1;i++){
min_index=i;
for(int y=i+1;y<data_length;y++){
if(data[min_index]>data[y]){
min_index=y;
}
}
if(min_index!=i){
temp=data[i];
data[i]=data[min_index];
data[min_index]=temp;
}
}
for(int i=0;i<data.length;i++){
System.out.println(data[i]);
}
}
第一次排序,需要比较N-1次; 第二次排序,需要比较N-2次; ...... 第N-1次排序,需要比较1次;
比较次数=(N-1)+(N-2)+...+1=((1+ N-1)*(N-1))/2=N²/2 + N/2 所以时间复杂度为:O(N²)
一、相同点
1.都有两层循环,外层循环控制比较的轮数,和数组元素的个数有关。内层循环控制需要参与比较的元素个数,和外层循环的轮数有关,最终比较的次数是一样的。
2.两种算法进行交换的结构是相同的。
二、不同点
1.冒泡算法每轮每个数据比较需要交换数据,选择算法每轮只要交换一次数据。所里理论上,选择排序效率高一点。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。