Several common ways to write bubble sort in java

Common writing methods: 1. Basic bubble sort; 2. Improved bubble sort: Since each outer loop will move the largest number to the correct position, the number of inner loops can be reduced , thereby improving efficiency; 3. Combination of insertion sort and bubble sort: This writing method draws on the idea of ​​insertion sort, by gradually moving the sorted elements forward, so that the unsorted elements are gradually ordered. This method is called "cocktail sequencing."

Operating system for this tutorial: Windows 10 system, Dell G3 computer.

Bubble sorting is a simple sorting algorithm that repeatedly traverses the sequence to be sorted, comparing two elements at a time, and swapping them if they are in the wrong order. The work of traversing the array is repeated until no more exchanges are needed, which means that the array has been sorted.

The following are several common Java implementations of bubble sorting:

1. Basic bubble sorting:

java

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

2. Improved bubble sort: Since each outer loop will move the largest number to the correct position, the number of inner loops can be reduced, thereby improving efficiency.

java

public static void bubbleSort(int[] arr) {  
    for (int i = 0; i < arr.length - 1; i++) {  
        boolean swapped = false;  
        for (int j = 0; j < arr.length - 1 - i; j++) {  
            if (arr[j] > arr[j + 1]) {  
                // swap arr[j+1] and arr[j]  
                int temp = arr[j];  
                arr[j] = arr[j + 1];  
                arr[j + 1] = temp;  
                swapped = true;  
            }  
        }  
        // If no two elements were swapped by inner loop, then the array is sorted  
        if (!swapped) break;  
    }  
}

3. Combination of insertion sort and bubble sort: This writing method draws on the idea of ​​insertion sort, by gradually moving the sorted elements forward. , so that unsorted elements are gradually sorted. This method is called "cocktail sequencing."

java

public static void cocktailSort(int[] arr) {  
    int n = arr.length;  
    boolean swapped; // to flag if any swap has been made in a pass  
    for (int i = 0; i < n - 1; i++) {  
        swapped = false; // assume this pass will do nothing  
        for (int j = 0; j < n - 1 - i; j++) { // start with the second last element and go to the last one  
            if (arr[j] > arr[j + 1]) { // if the current element is greater than the next one, swap them  
                int temp = arr[j]; // swap elements  
                arr[j] = arr[j + 1];  
                arr[j + 1] = temp;  
                swapped = true; // flag to indicate a swap has been made in this pass  
            }  
        }  
        // if no two elements were swapped in this pass, then the array is sorted, so we can stop the sorting process  
        if (!swapped) break; // no swaps means the array is sorted, so we can stop the sorting process. This optimization is not required for correctness, but it can help in practice. If the array is already sorted, the outer loop will keep making passes without making any swaps, so we can stop early. This optimization can be applied to any version of bubble sort

The above is the detailed content of Several common ways to write bubble sort in java. For more information, please follow other related articles on the PHP Chinese website!