Detailed introduction to Java bubble sort (code example)

This article brings you a detailed introduction (code example) about Java bubble sorting. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you. helped.

1. Introduction

Because this is the first article in the sorting algorithm series, I will say a few more words.

Sort is one of the most common algorithms. Now many programming languages ​​have integrated some sorting algorithms, such as Java's Arrays.sort() method. This method allows us to call it directly without caring about the internal implementation details. It is also often used in actual software development. But from a developer's perspective, to know what is happening, you must know why. Practicing more sorting algorithms will not only let us know the underlying implementation details of some sorting methods, but also exercise our thinking and improve our programming abilities. Many technical interviews now also involve basic sorting algorithms, so it is beneficial to practice more. (Recommended: Java Video Tutorial)

The codes involved in the article are all implemented in Java, but they will not involve too many Java language features, and I will add detailed comments. , helps you understand the code and convert it into a programming language you are familiar with.

There are 10 common sorting algorithms:

• Bubble sort, selection sort, insertion sort, the average time complexity is O(n² )
• The average time complexity of Hill sort, merge sort, quick sort, and heap sort is O(nlogn)
• The average time complexity of counting sort, radix sort, and bucket sort is O(nlogn) It is O(n k)

Before starting to explain the specific sorting algorithm, you must first understand two concepts:

1. Sorting in place: refers to the process of sorting It does not occupy additional storage space, and the space complexity is O(1).
2. Stability of sorting algorithm: A stable sorting means that after sorting, the order of the same elements will not be changed. Otherwise, it is called unstable. For example: an array [3, 5, 1, 4, 9, 6, 6, 12] has two 6s (for distinction, I bolded one of the 6s), if after sorting it is Like this: [1, 3, 4, 5, 6, 6, 9, 12] (the bold 6 is still in front), which shows that this is a stable sorting algorithm.

2. Closer to home

The idea of ​​bubble sorting is actually very simple. Compare the size of one data with its adjacent data. If the size relationship is satisfied , exchange the positions of these two data. By repeating this operation, the data can be sorted.

For example, if there is an array a[3,5,1,4,9,6], the first bubbling operation is as shown below:

Repeat this operation. After 6 bubbles, the data sorting is completed.

According to this idea, it should be easy to write the following code to implement bubble sorting:

public class BubbleSort {

    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序
        if (n  data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                }
            }
        }
    }
}

But this sorting algorithm can also be optimized, when there is no data exchange in the bubbling operation When, it means that the sorting has been completed, and there is no need to perform the bubbling operation. For example, in the above example, after the first bubble, the data is [3,1,4,5,6,9], and after another bubble, the data becomes [1,3,4,5,6,9] , the sorting has been completed at this time, and the loop can be ended.

So for sorting this array, the above code requires 6 bubbles to complete, 4 of which are unnecessary. So the code can be optimized:

public class BubbleSort {

    //优化后的冒泡排序
    //data表示整型数组，n表示数组大小
    public static void bubbleSort(int[] data, int n){
        //数组大小小于等于1，无须排序，返回空
        if (n  data[j + 1]，交换两个数据的位置
                if (data[j] > data[j + 1]){
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;

                    flag = true;//表示有数据交换
                }
            }
            //如果没有数据交换，则直接退出循环
            if (!flag) break;
        }
    }
}

Okay, the basic ideas and code of bubble sorting have been implemented. Finally, let’s summarize:

1. Bubble sorting is based on data comparison.
2. The best case time complexity is O(n), the worst case time complexity is O(n²), and the average time complexity is O(n²)
3. Bubble sorting is an in-place sorting algorithm and is stable.

The above is the detailed content of Detailed introduction to Java bubble sort (code example). For more information, please follow other related articles on the PHP Chinese website!