冒泡排序原理：
比較相鄰的元素芋忿，如果第一個(gè)比第二個(gè)大，就交換他們蒋荚， 把大的放到后面再和后面的其他元素比較戳稽。
對(duì)每一對(duì)相鄰元素做同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)期升。每次執(zhí)行完都會(huì)產(chǎn)生一個(gè)最大數(shù)惊奇。
每次比較完都會(huì)使需要比較的數(shù)少 1 互躬，一直進(jìn)行到只剩最后一個(gè),即 比較次數(shù)從n-1 一直到1。
n 個(gè)數(shù)需要進(jìn)行的循環(huán)次數(shù)從n - 1次到1次颂郎。
靜態(tài)實(shí)現(xiàn)圖：
ps:這是一個(gè)循環(huán)的實(shí)現(xiàn)情況吼渡。
動(dòng)態(tài)實(shí)現(xiàn)圖：
代碼實(shí)現(xiàn)：
importjava.util.Arrays;
?
publicclassBubbleSort{
publicstaticvoidmain(String[]args){
int[]arr={10,30,25,58,45,74};
inttemp=0;
?
for(inti=0;i<arr.length-1;i++){
//arr.length -1-i 是為了減少循環(huán)次數(shù)，已經(jīng)排好序的數(shù)據(jù)不需要再次比較乓序。
for(intj=0;j<arr.length-1-i;j++) {
if(arr[j]>arr[j+1]) {
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
? ? ? ? ? ? ?? }
? ? ? ? ?? }
? ? ?? }
System.out.println(Arrays.toString(arr));
?
?? }
}
優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：代碼簡(jiǎn)單诞吱，易于理解，空間復(fù)雜度低竭缝，屬于穩(wěn)定排序房维。
缺點(diǎn)：不管數(shù)據(jù)是否有序，都會(huì)進(jìn)行固定次數(shù)的排序操作抬纸，效率不高咙俩，時(shí)間復(fù)雜度：
交換數(shù)據(jù)的代碼執(zhí)行次數(shù) T(n) = 1+2+....+(n-1) = (1+n-1)*(n-1)/2 = (n^2 - n)/2
所以最壞情況：T(n) = O(f(n)) = O(n^2)
改進(jìn)版：
importjava.util.Arrays;
?
publicclassBubbleSort{
publicstaticvoidmain(String[]args){
int[]arr={1,3,5,8,45,74};
inttemp=0;
booleanflag=true;
?
for(inti=0;i<arr.length-1;i++){
for(intj=0;j<arr.length-1-i;j++) {
if(arr[j]>arr[j+1]) {
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
flag=false;
? ? ? ? ? ? ?? }
? ? ? ? ?? }
if(flag){
break;
}else{
flag=true;
? ? ? ? ?? }
? ? ?? }
System.out.println(Arrays.toString(arr));
?? }
}
?
加入一個(gè)flag變量作為崗哨，探測(cè)有沒有發(fā)生數(shù)據(jù)交換湿故，如果某一次循環(huán)的時(shí)候沒有發(fā)生數(shù)據(jù)交換阿趁，那么就說明數(shù)組已經(jīng)是有序的了，就不再繼續(xù)執(zhí)行循環(huán)坛猪。
