Java算法之冒泡排序【超詳細】

冒泡排序基本思想核心思想是從頭開始讓相鄰的兩個元素進行比較，符合條件就交換位置，這樣就把最大值或者最小值放到數(shù)組的最后面了；接著再從頭開始兩兩比較交換，直到把最大值或者最小值放到數(shù)組的倒數(shù)第二位。（即不需要與最后一位數(shù)進行對比）.....以此類推，直到排序完成。

簡單理解: 每次都從第一個元素開始(索引0),向后兩兩比較,只要后面的比前面的大,就交換(從大到小) 

用最簡單的代碼實現(xiàn)冒泡排序?qū)?shù)組進行從大到小的順序排列： 

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]
                int temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
            }
        }
        System.out.println("第一趟排序后:"+Arrays.toString(array));
    }
}

運行結(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]
        int temp = array[i];
        array[i] = array[i+1];
        array[i+1] = temp;
    }
}
System.out.println("第二趟排序后:"+Arrays.toString(array));

運行結(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]
        int temp = array[i];
        array[i] = array[i+1];
        array[i+1] = temp;
    }
}
System.out.println("第三趟排序后:"+Arrays.toString(array));

運行結(jié)果

第三趟排序后:[6, 7, 5, 4, 3]

第四趟排序

比較的順序：array[0]和array[1]比較

代碼

在第三趟排序的BubbleSort類中,添加如下代碼片段:

//從索引為0開始依次向后兩兩比較,總共比較1次
for(int i = 0;i<1;i++) {
    if(array[i]
        int temp = array[i];
        array[i] = array[i+1];
        array[i+1] = temp;
    }
}
System.out.println("第四趟排序后:"+Arrays.toString(array));

運行結(jié)果

第四趟排序后:[7, 6, 5, 4, 3]

找出共性優(yōu)化冒泡排序代碼

以上代碼,我們發(fā)現(xiàn)對于5個數(shù)字的排序我們用了簡單的4個for循環(huán)就可以完成,而且每個for循環(huán)的內(nèi)容都差不多,這樣可以對以上4個for循環(huán)的內(nèi)容進行變化,很容易看出里面的共性的內(nèi)容,從而更方便的簡化代碼.每個for循環(huán)的初始化條件都是i=0,for循環(huán)中的內(nèi)容都是相同的. 只有結(jié)束條件不同: 

第一個for的結(jié)束條件是<4；第二個for循環(huán)的結(jié)束條件<3；第三個for循環(huán)的結(jié)束條件<2；第四個for循環(huán)的結(jié)束條件<1；我們發(fā)現(xiàn)4正好是數(shù)組的長度-1,這樣可以進行如下優(yōu)化: 第一個for的結(jié)束條件是

(注意:其實最后減的數(shù)字可以不寫的,寫上是為了提高效率,但是前面的array.length-1中的-1不能省略,是為了防止索引越界異常,因為我們進行比較的時候,分別用i和i+1作為索引獲取數(shù)組中的元素,所以要保證i和i+1都不能越界。

代碼

public class BubbleSort {
    public static void main(String[] args) {
        //定義數(shù)組
        int[] array = {3,4,5,6,7};
        //從索引為0開始依次向后兩兩比較
        for(int i = 0;i
            if(array[i]
                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
        if(array[i]
            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
        if(array[i]
            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
        if(array[i]
            int temp = array[i];
            array[i] = array[i+1];
            array[i+1] = temp;
        }
    }
    System.out.println("第四趟排序后:"+Arrays.toString(array));
    }
}

運行結(jié)果

第一趟排序后:[4, 5, 6, 7, 3]

第二趟排序后:[5, 6, 7, 4, 3]

第三趟排序后:[6, 7, 5, 4, 3]

第四趟排序后:[7, 6, 5, 4, 3]

冒泡排序的最終代碼

以上4個for循環(huán)代碼重復性較高,唯獨不一樣的地方就是每個for循環(huán)結(jié)束條件最后減的數(shù)字不同,第一個for循環(huán)結(jié)束條件減的數(shù)字是0,第二個for循環(huán)結(jié)束條件減的數(shù)字是1,第3個for循環(huán)結(jié)束條件減的數(shù)字是2,第4個for循環(huán)結(jié)束條件減的數(shù)字是3,這樣可以寫一個循環(huán)4次的for循環(huán),假設循環(huán)變量為j,只要j的取值>=0開始到<4結(jié)束,正好能獲取0,1,2,3的數(shù)字,然后把上面的任意一個for循環(huán)作為循環(huán)體,把該循環(huán)體中for循環(huán)的結(jié)束條件中最后減掉的數(shù)字用j替換掉即可.發(fā)現(xiàn)5個數(shù)只需要排4趟,那么n個數(shù)需要排n-1趟,如果上面的循環(huán)中的變量j的范圍固定寫成<4,對于有6,7,...個數(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

        //j:0,1,2,3

        //i = 0:表示每次都從索引為0的開始,向后兩兩比較

        for(int i = 0;i

        //內(nèi)層循環(huán),每趟執(zhí)行的次數(shù),‐1為了防止索引越界,‐j為了提高效率

            if(array[i]

                int temp = array[i];

                array[i] = array[i+1];

                array[i+1] = temp;

           }

        }

    }

    System.out.println("排序后的內(nèi)容:"+Arrays.toString(array));

    }

}

運行結(jié)果

排序前的內(nèi)容:[3, 4, 5, 6, 7]

排序后的內(nèi)容:[7, 6, 5, 4, 3]

總結(jié)

1、冒泡排序的原理：每次都從第一個元素開始(索引0),向后兩兩比較,只要后面的比前面的大,就交換(從大到小)

2、通過畫圖分析，5個數(shù)字排4趟，n數(shù)字排n-1趟，而外層的for循環(huán)代表的是循環(huán)的趟數(shù)，所以外層循環(huán)的結(jié)束條件是array.length-1，但是寫array.length代碼也沒有問題，比如5個數(shù)字在第4趟都已經(jīng)排好了，再進行第5趟排序,也不會影響程序的結(jié)果。

3、內(nèi)層循環(huán)變量的初始值寫成int i =0，是為了保證每次都從第一個元素開始(索引為0)向后兩兩比較。但是內(nèi)層循環(huán)的結(jié)束條件ijava培訓課程。

猜你喜歡：
冒泡排序算法動圖版
Java面向?qū)ο笫鞘裁匆馑?
JDK下載安裝與環(huán)境變量配置圖文教程【超詳細】
java遞歸是什么意思,怎么用
Java中switch條件語句的用法
正則化是什么意思?正則化技術(shù)解析