Some common Java bubble sort algorithms: sort in ascending order

Java bubble sorting: several common writing methods from small to large, specific code examples are required

Bubble sorting is a simple sorting algorithm that repeatedly Compare two adjacent elements and swap them according to size order until the entire sequence is ordered. In Java, there are several common writing methods and optimization methods for bubble sorting. The following will introduce five common writing methods and provide specific code examples.

The first way to write: ordinary bubble sort

Ordinary bubble sort directly nests two levels of loops. The outer loop controls the number of rounds of comparison, and the inner loop performs specific comparisons. and exchange.

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;
            }
        }
    }
}

The second way of writing: Optimizing the outer loop

Based on the first way of writing, if no exchange is performed in one round of sorting, it means that the array is already in order and the sorting can be ended early. . To achieve this optimization, we can add a flag bit to record whether a swap occurred.

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;
        }
    }
}

The third way of writing: Optimizing the inner loop

Based on the second way of writing, you can find that each round of comparison will "bubble" the largest element to the end. Therefore, the number of inner loop comparisons per round can be gradually reduced.

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;
    }
}

The fourth way of writing: Optimizing the inner and outer loops

Based on the third way of writing, if the array does not exchange in a certain round of comparison, it means that the elements behind the array are already in order , you can end the sorting early.

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;
        }
    }
}

The fifth way of writing: optimizing the outer loop and the inner loop

Based on the fourth way of writing, we can find that each round of comparison will find the largest element of the current round, and Put it in the right place. Therefore, we can find both the maximum and minimum values ​​in each round of comparison and sort them.

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;
    }
}

The above are five common writing methods of bubble sort. Each writing method has different optimization methods. In actual use, you can choose the appropriate writing method according to the specific situation. Through these optimizations, the efficiency of bubble sorting can be improved and the sorting time can be reduced.

Although bubble sorting is simple, its performance is poor when sorting large-scale data. Therefore, in practical applications, more efficient sorting algorithms, such as quick sort, merge sort, etc., are more commonly used.

The above is the detailed content of Some common Java bubble sort algorithms: sort in ascending order. For more information, please follow other related articles on the PHP Chinese website!