更新時(shí)間:2020-06-11 來源:黑馬程序員 瀏覽量:
冒泡排序基本思想核心思想是從頭開始讓相鄰的兩個(gè)元素進(jìn)行比較,符合條件就交換位置,這樣就把最大值或者最小值放到數(shù)組的最后面了;接著再從頭開始兩兩比較交換,直到把最大值或者最小值放到數(shù)組的倒數(shù)第二位。(即不需要與最后一位數(shù)進(jìn)行對(duì)比).....以此類推,直到排序完成。
簡單理解: 每次都從第一個(gè)元素開始(索引0),向后兩兩比較,只要后面的比前面的大,就交換(從大到小)
用最簡單的代碼實(shí)現(xiàn)冒泡排序?qū)?shù)組進(jìn)行從大到小的順序排列:
int[] array = {3,4,5,6,7};
第一趟排序比較的順序: array[0]和array[1]比較,array[1]和array[2]比較,array[2]和array[3]比較,array[3]和array[4]比較
代碼
public class BubbleSort {
public static void main(String[] args) {
//定義數(shù)組
int[] array = {3,4,5,6,7};
//從索引為0開始依次向后兩兩比較,總共比較4次
for(int i = 0;i<4;i++) {
if(array[i]<array[i+1]) { //只要后面的比它大就交換
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
System.out.println("第一趟排序后:"+Arrays.toString(array));
}
}
運(yùn)行結(jié)果
第一趟排序后:[4, 5, 6, 7, 3]
第二趟排序
比較的順序:array[0]和array[1]比較,array[1]和array[2]比較,array[2]和array[3]比較
代碼
在第一趟排序的BubbleSort類中,添加如下代碼片段:
//從索引為0開始依次向后兩兩比較,總共比較3次
for(int i = 0;i<3;i++) {
if(array[i]<array[i+1]) { //只要后面的比它大就交換
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
System.out.println("第二趟排序后:"+Arrays.toString(array));
運(yùn)行結(jié)果
第二趟排序后:[5, 6, 7, 4, 3]
第三趟排序
比較的順序:array[0]和array[1]比較,array[1]和array[2]比較
代碼
在第二趟排序的BubbleSort類中,添加如下代碼片段:
//從索引為0開始依次向后兩兩比較,總共比較2次
for(int i = 0;i<2;i++) {
if(array[i]<array[i+1]) { //只要后面的比它大就交換
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
System.out.println("第三趟排序后:"+Arrays.toString(array));
運(yùn)行結(jié)果
第三趟排序后:[6, 7, 5, 4, 3]
第四趟排序
比較的順序:array[0]和array[1]比較
代碼
在第三趟排序的BubbleSort類中,添加如下代碼片段:
//從索引為0開始依次向后兩兩比較,總共比較1次
for(int i = 0;i<1;i++) {
if(array[i]<array[i+1]) { //只要后面的比它大就交換
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
System.out.println("第四趟排序后:"+Arrays.toString(array));
運(yùn)行結(jié)果
第四趟排序后:[7, 6, 5, 4, 3]
找出共性優(yōu)化冒泡排序代碼
以上代碼,我們發(fā)現(xiàn)對(duì)于5個(gè)數(shù)字的排序我們用了簡單的4個(gè)for循環(huán)就可以完成,而且每個(gè)for循環(huán)的內(nèi)容都差不多,這樣可以對(duì)以上4個(gè)for循環(huán)的內(nèi)容進(jìn)行變化,很容易看出里面的共性的內(nèi)容,從而更方便的簡化代碼.每個(gè)for循環(huán)的初始化條件都是i=0,for循環(huán)中的內(nèi)容都是相同的. 只有結(jié)束條件不同:
第一個(gè)for的結(jié)束條件是<4;第二個(gè)for循環(huán)的結(jié)束條件<3;第三個(gè)for循環(huán)的結(jié)束條件<2;第四個(gè)for循環(huán)的結(jié)束條件<1;我們發(fā)現(xiàn)4正好是數(shù)組的長度-1,這樣可以進(jìn)行如下優(yōu)化: 第一個(gè)for的結(jié)束條件是<array.length-1-0 ,二個(gè)for循環(huán)的結(jié)束條件<array.length-1-1,第三個(gè)for循環(huán)的結(jié)束條件<array.length-1-2,第四個(gè)for循環(huán)的結(jié)束條件<array.length-1-3這樣四個(gè)for循環(huán)的結(jié)束條件唯一不同的就是最后減的數(shù)字不同(其實(shí)真正的含義是每一趟排序都會(huì)確定出一個(gè)數(shù)字的具體的位置,下一趟排序,就可以少排一個(gè))
(注意:其實(shí)最后減的數(shù)字可以不寫的,寫上是為了提高效率,但是前面的array.length-1中的-1不能省略,是為了防止索引越界異常,因?yàn)槲覀冞M(jìn)行比較的時(shí)候,分別用i和i+1作為索引獲取數(shù)組中的元素,所以要保證i和i+1都不能越界,所以i必須<array.length-1)
代碼
public class BubbleSort {
public static void main(String[] args) {
//定義數(shù)組
int[] array = {3,4,5,6,7};
//從索引為0開始依次向后兩兩比較
for(int i = 0;i<array.length‐1‐0;i++) {
if(array[i]<array[i+1]) { //只要后面的比它大就交換
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
System.out.println("第一趟排序后:"+Arrays.toString(array));
//從索引為0開始依次向后兩兩比較,總共比較3次
for(int i = 0;i<array.length‐1‐1;i++) {
if(array[i]<array[i+1]) { //只要后面的比它大就交換
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
System.out.println("第二趟排序后:"+Arrays.toString(array));
//從索引為0開始依次向后兩兩比較,總共比較2次
for(int i = 0;i<array.length‐1‐2;i++) {
if(array[i]<array[i+1]) { //只要后面的比它大就交換
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
System.out.println("第三趟排序后:"+Arrays.toString(array));
//從索引為0開始依次向后兩兩比較,總共比較1次
for(int i = 0;i<array.length‐1‐3;i++) {
if(array[i]<array[i+1]) { //只要后面的比它大就交換
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
System.out.println("第四趟排序后:"+Arrays.toString(array));
}
}
運(yùn)行結(jié)果
第一趟排序后:[4, 5, 6, 7, 3]
第二趟排序后:[5, 6, 7, 4, 3]
第三趟排序后:[6, 7, 5, 4, 3]
第四趟排序后:[7, 6, 5, 4, 3]
冒泡排序的最終代碼
以上4個(gè)for循環(huán)代碼重復(fù)性較高,唯獨(dú)不一樣的地方就是每個(gè)for循環(huán)結(jié)束條件最后減的數(shù)字不同,第一個(gè)for循環(huán)結(jié)束條件減的數(shù)字是0,第二個(gè)for循環(huán)結(jié)束條件減的數(shù)字是1,第3個(gè)for循環(huán)結(jié)束條件減的數(shù)字是2,第4個(gè)for循環(huán)結(jié)束條件減的數(shù)字是3,這樣可以寫一個(gè)循環(huán)4次的for循環(huán),假設(shè)循環(huán)變量為j,只要j的取值>=0開始到<4結(jié)束,正好能獲取0,1,2,3的數(shù)字,然后把上面的任意一個(gè)for循環(huán)作為循環(huán)體,把該循環(huán)體中for循環(huán)的結(jié)束條件中最后減掉的數(shù)字用j替換掉即可.發(fā)現(xiàn)5個(gè)數(shù)只需要排4趟,那么n個(gè)數(shù)需要排n-1趟,如果上面的循環(huán)中的變量j的范圍固定寫成<4,對(duì)于有6,7,...個(gè)數(shù)字的數(shù)組排序是不通用的,所以4可以使用數(shù)組的長度array.length-1 = 5-1 來表示
代碼
public class BubbleSort {
public static void main(String[] args) {
//定義數(shù)組
int[] array = {3,4,5,6,7};
System.out.println("排序前的內(nèi)容:"+Arrays.toString(array));
for(int j = 0;j<array.length‐1;j++) { //外層循環(huán),趟數(shù)
//j:0,1,2,3
//i = 0:表示每次都從索引為0的開始,向后兩兩比較
for(int i = 0;i<array.length‐1‐j;i++) {
//內(nèi)層循環(huán),每趟執(zhí)行的次數(shù),‐1為了防止索引越界,‐j為了提高效率
if(array[i]<array[i+1]) {
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
}
System.out.println("排序后的內(nèi)容:"+Arrays.toString(array));
}
}
運(yùn)行結(jié)果
排序前的內(nèi)容:[3, 4, 5, 6, 7]
排序后的內(nèi)容:[7, 6, 5, 4, 3]
總結(jié)
1、冒泡排序的原理:每次都從第一個(gè)元素開始(索引0),向后兩兩比較,只要后面的比前面的大,就交換(從大到小)
2、通過畫圖分析,5個(gè)數(shù)字排4趟,n數(shù)字排n-1趟,而外層的for循環(huán)代表的是循環(huán)的趟數(shù),所以外層循環(huán)的結(jié)束條件是array.length-1,但是寫array.length代碼也沒有問題,比如5個(gè)數(shù)字在第4趟都已經(jīng)排好了,再進(jìn)行第5趟排序,也不會(huì)影響程序的結(jié)果。
3、內(nèi)層循環(huán)變量的初始值寫成int i =0,是為了保證每次都從第一個(gè)元素開始(索引為0)向后兩兩比較。但是內(nèi)層循環(huán)的結(jié)束條件i<array.length-1-i,這里一定要-1,原因很簡單,因?yàn)樵趦?nèi)層循環(huán)中分表使用i和i+1作為索引獲取數(shù)組的元素,就要保證i和i+1都不能超出數(shù)組的索引范圍,即i<array.length && i+1<array.length 推導(dǎo)出i<array.length-1.最后的-i只是為了提高效率,因?yàn)槊刻伺判蚨紩?huì)確定一個(gè)數(shù)組元素的位置,下一趟排序的時(shí)候,已經(jīng)確定好位置的元素是不用繼續(xù)排序的。推薦了解黑馬程序員java培訓(xùn)課程。
猜你喜歡:
冒泡排序算法動(dòng)圖版