冒泡排序
代码
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] numbers = { 5, 1, 3, 2, 4, 6 };
System.out.println("排序前的数组为:" + Arrays.toString(numbers));
// 冒泡排序
// 外层循环控制排序循环的轮数
for (int i = 0; i < numbers.length - 1; i++) {
// 内层循环控制两两比较
for (int j = 0; j < numbers.length - i - 1; j++) {
// 不通过第三遍量交换两个数的顺序
if (numbers[j] > numbers[j + 1]) {
numbers[j] += numbers[j + 1];
numbers[j + 1] = numbers[j] - numbers[j + 1];
numbers[j] -= numbers[j + 1];
}
}
}
System.out.println("排序后的数组为:" + Arrays.toString(numbers));
}
}
输出效果为:
排序前的数组为:[5, 1, 3, 2, 4, 6]
排序后的数组为:[1, 2, 3, 4, 5, 6]
释义
冒泡算法,通过两两比较得到排好顺序的数列。以[5, 1, 3, 2, 4, 6]
升序排列为例,一步一步来理顺。
第一轮比较是这样的,将两个相邻的元素相比较,若前面的元素比后面的元素小则元素交换位置。先是第一个和第二个元素比较,下面依次是第二个和第三个元素比较直到倒数第二个和最后一个。通过第一轮比较可以将数值最大的元素放置到数组末尾。这里一共比较了五次。
[5, 1, 3, 2, 4, 6]
5和1比较
[1, 5, 3, 2, 4, 6]
5和3比较
[1, 3, 5, 2, 4, 6]
5和2比较
[1, 3, 2, 5, 4, 6]
5和4比较
[1, 3, 2, 4, 5, 6]
5和6比较
[1, 3, 2, 4, 5, 6]
接着是第二轮比较。这次比较直比较5个元素即可,因为最后一个元素已经确认。为了方便理解,最后一个元素不予显示。这里一共比较了四次。
[1, 3, 2, 4, 5]
1和3比较
[1, 3, 2, 4, 5]
3和2比较
[1, 2, 3, 4, 5]
3和4比较
[1, 2, 3, 4, 5]
4和5比较
[1, 2, 3, 4, 5]
以这个数组为例并不恰当,因为第二次比较就已经得出了排好顺序的数组,但是计算机并不知道这是排好序的数组,为了更好的理解冒泡排序,我们走完它。第三次:
[1, 2, 3, 4]
1和2比较
[1, 2, 3, 4]
2和3比较
[1, 2, 3, 4]
3和4比较
[1, 2, 3, 4]
第四次:
[1, 2, 3]
1和2比较
[1, 2, 3]
2和3比较
[1, 2, 3]
第五次:
[1, 2]
1和2比较
[1, 2]
至此,已经比较完毕。我们一次得到了五个最大的元素。如果上面的数组不省略,最后一应该写作[1, 2, 3, 4, 5, 6]
。
六个元素排序,我们一共进行了五轮比较,若是进行N个元素排序,需进行N-1次比较。
每一轮的比较中,比较的次数也是有迹可循的。前一轮的比较会得到某个极值元素,我们只需将此元素排除,进行剩余的元素个数-1次比较就会得到剩余元素中的极值元素。
在实际代码过程中外层控制比较轮数,内层控制美伦比较次数。数组下标从零开始。就可以得出循环的条件:
外层循环:int i = 0; i < numbers.length - 1; i++
内层循环:int j = 0; j < numbers.length - i - 1; j++
改进
从上面的例子我们可以看出,最后的几轮排序是毫无用处的,这给计算机造成了一定程度上的资源浪费。我们应该怎么避免这种无意义的循环呢?可以设置标记变量来实现。
int flag = 1;
for (int i = 0; i < numbers.length - 1 && flag != 0; i++) {
flag = 0;
// 内层循环控制两两比较
for (int j = 0; j < numbers.length - i - 1; j++) {
// 不通过第三遍量交换两个数的顺序
if (numbers[j] > numbers[j + 1]) {
numbers[j] += numbers[j + 1];
numbers[j + 1] = numbers[j] - numbers[j + 1];
numbers[j] -= numbers[j + 1];
// 若不交换位置,flag应为0,外层条件不成立,循环结束
flag = 1;
}
}
}
总结
时间复杂度
在设置标志变量之后:
当原始序列“正序”排列时,冒泡排序总的比较次数为n-1,移动次数为0,也就是说冒泡排序在最好情况下的时间复杂度为O(n);
当原始序列“逆序”排序时,冒泡排序总的比较次数为n(n-1)/2,移动次数为3n(n-1)/2次,所以冒泡排序在最坏情况下的时间复杂度为O(n^2);
当原始序列杂乱无序时,冒泡排序的平均时间复杂度为O(n^2)。
空间复杂度
冒泡排序排序过程中需要一个临时变量进行两两交换,所需要的额外空间为1,因此空间复杂度为O(1)。
稳定性
冒泡排序是一种稳定的排序算法。这里稳定的意思是指,若两元素数值相同,他们的位置并不会发生改变。
标签:int,元素,冒泡排序,numbers,排序,比较 From: https://www.cnblogs.com/isxh/p/16770407.html