算法入門教程-冒泡排序

上節(jié)我們分別通過案例迷宮和八皇后親自體驗了遞歸回溯算法的思想,本節(jié)我們學習常見八大算法之一的冒泡排序算法,親自感受下冒泡算法的思想.

冒泡排序算法介紹

冒泡排序算法的思想來源于生活中的啟迪,冬天的時候我們在燒開水的時候,可以清晰的在壺底看到氣泡依次從底部上升,在上升的過程中氣泡是由小變大徐徐上升直至破滅,這就是冒泡的生活來源

知道了冒泡的來源,我們大概明白了它的思想:我們可以假設(shè)有一組待排序的數(shù)字,從前往后,依次比較相鄰元素的值,如果發(fā)現(xiàn)逆序的現(xiàn)象,則進行位置的交換,讓數(shù)字大的元素往后移動即可,重復該步驟即可,這就是冒泡排序算法的思想,我們用圖解的方式來看下冒泡的過程

冒泡圖解過程

假設(shè)我們有一組如下圖的數(shù)字需要排序

冒泡排序原始數(shù)據(jù).png

具體的步驟如下圖:

第一趟的過程:

冒泡排序第一趟過程.png

代碼實現(xiàn):

//待排序的數(shù)字的數(shù)組
    int [] array = {3,9,-1,10,-2};
//定義一個臨時的變量來臨時保存我們交換的數(shù)
    int temp = 0;
    for(int i = 0; i < array.length -1 ; i++) {
        //如果前面的數(shù)大于后面的,則進行交換
        if (array[i] > array[i+1]){
            temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
        }
    }
    System.out.println("第一趟排序的結(jié)果為:");
    System.out.println(Arrays.toString(array));

測試結(jié)果如下圖:

第一趟排序的最終結(jié)果圖.png

結(jié)合圖以及代碼實現(xiàn),更加生動形象的理解冒泡第一趟排序的過程,說白了就是相鄰數(shù)之間的比較然后進行位置的交換,通過這樣的比較找出最大的一個數(shù),有圖和測試結(jié)果圖發(fā)現(xiàn)第一趟的最大值為10且已經(jīng)放置在最后的位置處,接著看:

第二趟:

冒泡排序第二趟排序圖.png
代碼實現(xiàn):

 // 第二趟排序,我們找出第二個大的數(shù),并放置在倒數(shù)第二個位置上
    for (int i = 0; i < array.length -1-1 ; i++) {
        //如果前面的數(shù)大于后面的,則進行交換
        if (array[i] > array[i+1]){
            temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
        }
    }
    System.out.println("第二趟排序的結(jié)果為:");
    System.out.println(Arrays.toString(array));

測試結(jié)果圖:

第二趟測試結(jié)果圖.png

通過第二趟的排序我們找到了9是最大的數(shù)字并放置在倒數(shù)第二的位置上,我們接著看:

第三趟排序的結(jié)果:

第三趟的排序圖.png

代碼實現(xiàn):

    // 第三趟排序,我們找出第三個大的數(shù),并放置在倒數(shù)第三個位置上
    for (int i = 0; i < array.length -1-1-1 ; i++) {
        //如果前面的數(shù)大于后面的,則進行交換
        if (array[i] > array[i+1]){
            temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
        }
    }
    System.out.println("第三趟排序的結(jié)果為:");
    System.out.println(Arrays.toString(array));

-測試結(jié)果圖如下:

第三趟測試結(jié)果圖.png

通過第三趟的排序我們將3放置在了它應有的位置處,我們接著看:

第四趟排序過程圖:

第四趟排序過程圖.png

代碼實現(xiàn):

// 第四趟排序,我們找出第四個大的數(shù),并放置在倒數(shù)第四個位置上
    for (int i = 0; i < array.length -1-1-1-1 ; i++) {
        //如果前面的數(shù)大于后面的,則進行交換
        if (array[i] > array[i+1]){
            temp = array[i];
            array[i] = array[i + 1];
            array[i + 1] = temp;
        }
    }
    System.out.println("第四趟排序的結(jié)果為:");
    System.out.println(Arrays.toString(array));

測試結(jié)果圖如下:

第四趟排序結(jié)果圖.png

經(jīng)過四次的排序,我們終于將該組數(shù)據(jù)排序完成,同時我們也可能找到了一些規(guī)律:

冒泡排序圖解規(guī)律總結(jié)

我們會發(fā)現(xiàn)一共進行數(shù)組的大小-1的大的循環(huán)
每一趟排序的次數(shù)都在減少

我們在上述的代碼中可以發(fā)現(xiàn),每一趟的for循環(huán)是重復的,因此我們可以將代碼進行整合優(yōu)化,一般封裝成一個方法即可,具體代碼如下:

//將冒泡排序封裝成一個方法
public static void bubbleSort(int[] array) {
    int temp = 0;
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - 1 - i; j++) {
            //如果前面的數(shù)大于后面的,則進行交換
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }

}

經(jīng)過封裝的話,我們直接調(diào)用該方法即可,只需要傳入需要排序的數(shù)組即可,其實我們上述的代碼還需要優(yōu)化,假如我們需要排序的數(shù)組為:int [] array = {3,9,-1,10,20};我們來測試一把,結(jié)果如下圖:

測試結(jié)果圖.png

在上圖的測試結(jié)果中我們看到的是,同樣也進行了四次的排序,其實在第三趟的排序過后就已經(jīng)完成了排序,第四次就不應該在排序,影響我們代碼的執(zhí)行效率,所以這里是需要優(yōu)化的一個點,具體優(yōu)化代碼如下:

代碼優(yōu)化

//將冒泡排序封裝成一個方法
public static void bubbleSort(int[] array) {
    int temp = 0;
    //定義一個標識,標識是否進行交換過
    boolean flag = false;
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - 1 - i; j++) {
            //如果前面的數(shù)大于后面的,則進行交換
            if (array[j] > array[j + 1]) {
                flag = true;
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
        System.out.println("第" + (i + 1) + "趟排序的結(jié)果為:");
        System.out.println(Arrays.toString(array));

        if (!flag) { //表示在一趟排序中沒有進行過一次交換
            break;
        } else {
            flag = false; //置為false,進行下次判斷
        }
    }
}

我們通過定義一個標識flag來控制我們的代碼,這也是算法中常見的做法,直接來看測試結(jié)果:

優(yōu)化后的測試結(jié)果.png

測試結(jié)果證明我們的代碼是沒有問題的,這也是我們代碼的一個小小的優(yōu)化,對于一個算法我們一般很關(guān)心算法的執(zhí)行時間,那么涉及到了一個知識點時間頻度和時間復雜度的問題,關(guān)于這個知識點,后續(xù)有時間的話來專門寫一篇文章細說,這里就不多說了,我們最后來測一下冒泡排序的執(zhí)行時間,修改了一下要排序的數(shù)組,直接看代碼:

冒泡排序的執(zhí)行時間的測試

代碼

  //冒泡排序的時間復雜度測試
    int [] arr = new int[100000];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int)(Math.random() * 100000); //隨機生成[0,80000)的數(shù)
    }

    Date date1 = new Date();
    SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String format = dateFormat.format(date1);
    System.out.println("排序前的時間為:"+format);
    //進行排序
    bubbleSort(arr);
    Date date2 = new Date();
    SimpleDateFormat dateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    String format2 = dateFormat.format(date2);
    System.out.println("排序后的時間為:"+format2);

測試結(jié)果圖:

執(zhí)行時間測試結(jié)果圖.png

我們可以看到的是,當排序10w的數(shù)據(jù)時,需要20多秒,也不一定,多執(zhí)行幾次對比下,其實關(guān)于冒泡排序算法的時間復雜度為O(n^2),至于為啥是這個值,因為我們是兩個for循環(huán)來執(zhí)行的,那么關(guān)于冒泡排序算法的學習就到這里了.....