Learn the common writing methods and analysis of Java bubble sorting

Quickly master Java bubble sort: analysis of several common writing methods

In computer science, bubble sort is a simple but inefficient sorting algorithm . The basic idea is to gradually "bubble" larger elements to the end of the array by comparing and exchanging adjacent elements multiple times.

In this article, we will introduce several common Java bubble sorting methods and give specific code examples to help readers quickly master this sorting algorithm.

1. The basic way of writing bubble sort

The basic way of writing bubble sort is very simple. It uses nested loops to exchange adjacent elements and compare them one by one. elements in the array, and "bubbles" larger elements to the end.

The following is a Java code example of basic writing:

public void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (array[j] > array[j+1]) {
                // 交换相邻的元素
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

2. Optimized writing of bubble sort

Although bubble sorting is simple, it is difficult to deal with large When scaling data, the efficiency will be very low. In order to improve the efficiency of sorting, we can add some optimization measures.

A common optimization method is to set a flag bit. If no exchange occurs in a certain loop, that is, the array is already in order, exit the loop early.

The following is a Java code example of optimized writing:

public void optimizedBubbleSort(int[] array) {
    int n = array.length;
    boolean swapped;
    for (int i = 0; i < n-1; i++) {
        swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (array[j] > array[j+1]) {
                // 交换相邻的元素
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                swapped = true;
            }
        }
        if (swapped == false)
            break;
    }
}

3. Optimized writing of bubble sort (further reducing the number of comparisons)

In the optimized writing , we can further reduce the number of comparisons. Because each round of bubbling operation will "bubble" the largest element in the unordered area to the end of the unordered area, the length of the unordered area in the next round is reduced by 1.

Based on this observation, we can record the last swap position lastSwapIndex in the inner loop. Because the elements after this position are already in order, no comparison is needed.

The following is a further optimized Java code example:

public void furtherOptimizedBubbleSort(int[] array) {
    int n = array.length;
    int lastSwapIndex;

    for (int i = 0; i < n-1; i++) {
        lastSwapIndex = 0;

        for (int j = 0; j < n-1-i; j++) {
            if (array[j] > array[j+1]) {
                // 交换相邻的元素
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
                lastSwapIndex = j+1;
            }
        }

        if (lastSwapIndex == 0)
            break;

        n = lastSwapIndex;
    }
}

Summary:

This article introduces common writing methods to quickly master Java bubble sorting, and gives specific code Example. Through the understanding and practice of these writing methods, everyone can better control and use this classic sorting algorithm. Of course, the efficiency of bubble sort is relatively low. For sorting large-scale data, it is recommended to choose a more efficient sorting algorithm, such as quick sort or merge sort.

The above is the detailed content of Learn the common writing methods and analysis of Java bubble sorting. For more information, please follow other related articles on the PHP Chinese website!