首頁  >  文章  >  Java  >  一些常見的Java冒泡排序演算法:以升序排列

一些常見的Java冒泡排序演算法:以升序排列

WBOY
WBOY原創
2024-01-10 12:30:46602瀏覽

一些常見的Java冒泡排序演算法:以升序排列

Java冒泡排序:從小到大的幾種常見寫法,需要具體程式碼範例

冒泡排序是一種簡單的排序演算法,它重複地比較相鄰的兩個元素,並根據大小順序進行交換,直到整個序列有序。在Java中,冒泡排序有幾種常見的寫法和最佳化方式,以下將介紹其中的五種常見寫法並提供具體程式碼實例。

第一種寫法:普通的冒泡排序

普通的冒泡排序直接嵌套兩層循環,外層循環控制比較的輪數,內層循環進行具體的比較和交換。

public static void bubbleSort1(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

第二種寫法:優化外層循環

在第一種寫法的基礎上,如果一輪排序沒有進行任何交換,說明數組已經有序,可以提前結束排序。為了實現這個最佳化,我們可以新增一個標記位元來記錄是否進行了交換。

public static void bubbleSort2(int[] arr) {
    int n = arr.length;
    boolean swapped;
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;
        }
    }
}

第三種寫法:最佳化內層循環

在第二種寫法的基礎上,可以發現每輪比較都會將最大的元素「冒泡」到最後。因此,每輪比較內層循環的次數可以逐漸減少。

public static void bubbleSort3(int[] arr) {
    int n = arr.length;
    int lastSwapIndex;
    for (int i = 0; i < n - 1; i++) {
        lastSwapIndex = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        i = n - lastSwapIndex - 2;
    }
}

第四種寫法:優化內外層循環

在第三種寫法的基礎上,如果數組在某輪比較中未發生交換,表示數組後面的元素已經有序,可以提前結束排序。

public static void bubbleSort4(int[] arr) {
    int n = arr.length;
    int lastSwapIndex, rightBoundary;
    rightBoundary = n - 1;
    for (int i = 0; i < n - 1; i++) {
        lastSwapIndex = 0;
        for (int j = 0; j < rightBoundary; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        rightBoundary = lastSwapIndex;
        if (rightBoundary <= 1) {
            break;
        }
    }
}

第五種寫法:優化外層循環和內層循環

在第四種寫法的基礎上,我們可以發現每輪比較都會找到當前輪最大的元素,並將其放到了正確的位置。因此,我們可以在每輪比較中同時找到最大值和最小值,並進行排序。

public static void bubbleSort5(int[] arr) {
    int n = arr.length;
    int lastSwapIndex, leftBoundary, rightBoundary;
    leftBoundary = 0;
    rightBoundary = n - 1;
    while (leftBoundary < rightBoundary) {
        lastSwapIndex = 0;
        for (int j = leftBoundary; j < rightBoundary; j++) {
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                lastSwapIndex = j + 1;
            }
        }
        rightBoundary = lastSwapIndex;
        for (int j = rightBoundary; j > leftBoundary; j--) {
            if (arr[j] < arr[j-1]) {
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                lastSwapIndex = j - 1;
            }
        }
        leftBoundary = lastSwapIndex;
    }
}

以上就是五種​​常見的冒泡排序寫法,每種寫法都有不同的最佳化方式,在實際使用時可以根據具體情況選擇合適的寫法。透過這些最佳化,可以提高冒泡排序的效率,減少排序時間。

冒泡排序雖然簡單,但是對於大規模的資料排序時效能較差。因此,在實際應用中,更常使用更有效率的排序演算法,如快速排序、歸併排序等。

以上是一些常見的Java冒泡排序演算法:以升序排列的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn