一.原理
1.从第一个元素起，比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
2.对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。
- 总结：
两两比较，
从头开始找最大
大的放后面，
比较的个数越来越少）
因为原理较为简单，直接贴代码。
二.java代码实现
public class Bubble {
public static void sort(int[] a){
for(int i=a.length-1;i>0;i--){
for(int j=0;j<i;j++){
if(a[j]>(a[j+1])){
swap(a,j,j+1);
}
}
}
}
private static void swap(int[] a,int i,int j){ //传的是索引！
int t;
t=a[i];
a[i]=a[j];
a[j]=t;}
public static void main(String[] args) {
int[] a={4,7,6,9,2,1};
Bubble.sort(a);
for (Integer k : a) {
System.out.println(k.intValue());
}
}
}
注意：
- 外层循环可视为每一轮最后一个数的索引范围，i=n-1是第一轮最后一个数，而 i最小为1不为0
- 内层循环从第一个数开始，依次向后比较，由于比较的是a[j]和a[j+1]，j+1最大是n-1,即索引最大值
复杂度分析：
元素比较的次数为：
(N-1)+(N-2)+(N-3)+…+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2; （二分之项数首项+末项）
元素交换的次数为：
3*[(N-1)+(N-2)+(N-3)+…+2+1]=((N-1)+1)*(N-1)/2=(N^2/2-N/2)*3;
总执行次数为：
(N^2 /2-N/2)+3(N^2/2-N/2)=…
按照大O推导法则，保留函数中的最高阶项那么最终冒泡排序的时间复杂度为O(N^2).
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89397.html
