快捷導航

Java排序算法之冒泡排序的原理及優(yōu)化

更新時間：2023年11月14日 10:26:35 作者：Cyuujie

這篇文章主要介紹了Java排序算法之冒泡排序的原理及優(yōu)化,冒泡排序的思想很簡單,遍歷數(shù)組,比較相鄰的兩個元素,順序錯誤就把它們交換,直到整個數(shù)組排序完成,因為每經(jīng)過一趟排序,越小的元素會經(jīng)交換而慢慢“浮”到數(shù)列的頂端,因此叫做冒泡排序,需要的朋友可以參考下

冒泡排序原理

冒泡排序的思想很簡單：遍歷數(shù)組，比較相鄰的兩個元素，順序錯誤就把它們交換，直到整個數(shù)組排序完成。因為每經(jīng)過一趟排序，越小的元素會經(jīng)交換而慢慢“浮”到數(shù)列的頂端，因此叫做冒泡排序。

在這里插入圖片描述

假設(shè)我們現(xiàn)在要對數(shù)組：arr= {3，9，-1，10，-2，5，21} 進行排序，結(jié)合上面的動圖，經(jīng)過第一趟排序后最大的元素會被排到最后。

第一趟排序

public int[] OneStepBubbleSort(int arr[]){
    int temp = 0;
    for (int i = 0; i < arr.length - 1; i++){
        if (arr[i] > arr[i + 1]){
            temp = arr[i];
            arr[i] =  arr[i + 1];
            arr[i + 1] = temp;
        }
    }
    System.out.print("第1趟排序完成:");
    System.out.println(Arrays.toString(arr));
    return arr;
}

測試：

public static void main(String[] args) {
    int[] arr = {3, 9, -1, 10, -2, 5, 21};
    SortTest sortTest = new SortTest();
    sortTest.OneStepBubbleSort(arr);
}

結(jié)果：

在這里插入圖片描述

那么第二趟排序后第二大的元素10會被排到倒數(shù)第二的位置。

第二趟排序

public int[] TwoStepBubbleSort(int arr[]){
    int temp = 0;
    for (int i = 0; i < arr.length - 1 - 1; i++){
        if (arr[i] > arr[i + 1]){
            temp = arr[i];
            arr[i] =  arr[i + 1];
            arr[i + 1] = temp;
        }
    }
    System.out.print("第2趟排序完成:");
    System.out.println(Arrays.toString(arr));
    return arr;
}

測試：

public static void main(String[] args) {
    int[] arr = {3, 9, -1, 10, -2, 5, 21};
    SortTest sortTest = new SortTest();
    sortTest.OneStepBubbleSort(arr);
    sortTest.TwoStepBubbleSort(arr);
}

結(jié)果：

在這里插入圖片描述

第三趟排序

public int[] ThreeStepBubbleSort(int arr[]){
    int temp = 0;
    for (int i = 0; i < arr.length - 1 - 2; i++){
        if (arr[i] > arr[i + 1]){
            temp = arr[i];
            arr[i] =  arr[i + 1];
            arr[i + 1] = temp;
        }
    }
    System.out.print("第3趟排序完成:");
    System.out.println(Arrays.toString(arr));
    return arr;
}

測試：

public static void main(String[] args) {
    int[] arr = {3, 9, -1, 10, -2, 5, 21};
    SortTest sortTest = new SortTest();
    sortTest.OneStepBubbleSort(arr);
    sortTest.TwoStepBubbleSort(arr);
		sortTest.ThreeStepBubbleSort(arr);
}

結(jié)果：

在這里插入圖片描述

如此類推，每一趟排序中不同的地方在于循環(huán)的終止條件：arr.length - 1 和 arr.length - 1 - 1 和 arr.length - 1 - 2 等等，那么只需要在此循環(huán)外面再包一層循環(huán)即可。最終代碼為：

冒泡排序算法代碼

public int[] BubbleSort(int arr[]){
    int temp = 0;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1 ; j++) {
            if (arr[j] > arr[j + 1]){
                temp = arr[j];
                arr[j] =  arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        System.out.print("第" + (i + 1) + "趟排序完成:");
        System.out.println(Arrays.toString(arr));
    }
    return arr;
}

測試：

public static void main(String[] args) {
        int[] arr = {3, 9, -1, 10, -2, 5, 21};
        SortTest sortTest = new SortTest();
        System.out.println();
        sortTest.BubbleSort(arr);
    }

結(jié)果：

在這里插入圖片描述

改進冒泡排序

從上面冒泡排序的結(jié)果可以看出，總共進行了6趟排序，但從第4躺開始數(shù)組就已經(jīng)排序完畢了，后面的兩趟排序相當于在做無用的比較。

為了解決此問題，我們可以進行優(yōu)化，思想是：如果發(fā)現(xiàn)在某一趟排序中沒有發(fā)生過一次交換，那么可以提前結(jié)束冒泡排序。實現(xiàn)方法是設(shè)置一個flag變量來記錄是否發(fā)生過交換：

public int[] BubbleSort(int arr[]){
    int temp = 0;
    boolean flag = false;
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - i - 1 ; j++) {
            if (arr[j] > arr[j + 1]){
                flag = true;
                temp = arr[j];
                arr[j] =  arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        // 判斷flag
        if (!flag){
        // 如果flag是false，則退出
            break;
        }else {
        // flag為true，說明發(fā)生過交換，那么在進行下一趟前需要把flag重新置為false
            flag = false;
        }
        System.out.print("第" + (i + 1) + "趟排序完成:");
        System.out.println(Arrays.toString(arr));
    }
    return arr;
}

測試：

public static void main(String[] args) {
        int[] arr = {3, 9, -1, 10, -2, 5, 21};
        SortTest sortTest = new SortTest();
        System.out.println();
        sortTest.BubbleSort(arr);
    }

結(jié)果：

在這里插入圖片描述