How to implement bubble sort algorithm in Java

In computer science, sorting algorithms are a very important class of algorithms used to arrange a set of data in a specific order.

Bubble Sort is a simple and intuitive sorting algorithm that gradually "bubbles" larger elements to the end of the array by repeatedly traversing the array to be sorted, comparing adjacent elements and exchanging their positions.

This article will introduce in detail how to implement the bubble sort algorithm using Java, and analyze its time complexity.

Introduction to Bubble Sort Algorithm.

The basic idea of bubble sort is: for a given array, starting from the first element, compare two adjacent elements in turn, and if the previous element is larger than the next element, exchange the positions of the two elements.

In this way, each round of traversal will "bubble" the maximum value of the currently unsorted portion to the end of the array.

Repeat this process until the entire array is ordered.

Java implements bubble sort.

The following is the code for the bubble sort algorithm written in Java:

public class BubbleSort {
    // 定义一个方法来实现冒泡排序
    public static void bubbleSort(int[] array) {
        int n = array.length; // 获取数组的长度
        boolean swapped; // 标记是否进行了交换
        
        // 外层循环控制遍历的次数
        for (int i = 0; i < n - 1; i++) {
            swapped = false; // 每次开始新的一轮时，重置交换标志
            
            // 内层循环进行相邻元素的比较和交换
            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;
                    swapped = true; // 设置交换标志为true
                }
            }
            
            // 如果在某一轮遍历中没有发生任何交换，说明数组已经有序，可以提前退出
            if (!swapped) {
                break;
            }
        }
    }
    
    // 主方法用于测试冒泡排序算法
    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90}; // 初始化一个待排序的数组
        System.out.println("排序前的数组:");
        printArray(array); // 打印排序前的数组
        
        bubbleSort(array); // 调用冒泡排序方法对数组进行排序
        
        System.out.println("排序后的数组:");
        printArray(array); // 打印排序后的数组
    }
    
    // 辅助方法用于打印数组
    public static void printArray(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

Code explanation.

1. # bubbleSort method #: This is the core method for implementing bubble sort.

It accepts an array of integers as parameters and implements sorting logic through a nested for loop.

The outer loop controls the number of traversals, and the inner loop is responsible for comparing and exchanging adjacent elements.

swappedVariables are used to optimize the algorithm, and the sorting process can be terminated early when no exchange occurs in a certain round of traversal.

2. # main method #: This is the entry point of the program to test the bubble sort algorithm.

First initialize an array to be sorted, then call bubbleSortMethod to sort it, and finally print the array before and after the sort.

3. # printArray method #: This is an auxiliary method for printing the contents of the array to facilitate viewing of the sorting results.

Time complexity analysis.

The time complexity of bubble sort can be determined by analyzing its worst, best, and average: - # Worst case #: When the input array is arranged in reverse order, each round of traversal requires the largest number of comparison and exchange operations.

At this point, the time complexity of the bubble sort is O (n ^ 2), where n is the length of the array.

- # Best case #: When the input array is already ordered, due to the setting of swappedFlag, the sort process can be terminated immediately after the first traversal.

At this point, the time complexity of the bubble sort is O (n).

- # Average case #: In general, the time complexity of bubble sort is also O (n ^ 2).

This is because in most cases, multiple traversals are required to complete the sort.

Despite the high time complexity of bubble sort, its implementation is very simple and suitable for small-scale datasets or teaching presentations.

For large datasets, it is recommended to use more efficient sorting algorithms, such as quick sort, merge sort, etc.

Practical application scenarios.

Although bubble sorting is not efficient, it is suitable for beginners to understand and master the basic sorting algorithm principles due to its simple implementation.

In actual development, bubble sorting is more used for teaching and learning purposes than sorting tasks in a production environment.

In practical applications, we usually choose more efficient sorting algorithms to process large-scale data.

In summary, bubble sorting is a basic and easy-to-understand sorting algorithm. Through the introduction and code implementation of this article, I believe that readers have mastered its basic principles and implementation methods.

Hope this article can help you better understand and apply the bubble sort algorithm.