Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

When it comes to algorithms, a lot of people are scared. But what about a promotion and a raise?

Running away all the time doesn’t change anything, doesn’t solve anything. I don’t want to be stuck with these algorithms for the rest of my life, but AT the same time I’m not trying to master elegant implementation algorithms all at once.

Soak it up bit by bit.

Bubble sort concept:

Constantly comparing adjacent elements, swapping if not in the right order. Round and round, until all the neighboring elements are compared, is a very naive way of sorting.

Smooth out the magnification of mentality


import java.util.Arrays;

public classBubble sort{
    // This is an example of how to compare a sequence of rows. Don't swap things that are already in order
    public static void main(String[] args) {
        int[] values = {3.1.6.2.9.0.7.4.5.8};
        bubbleSort(values);
        System.out.println(Arrays.toString(values));
    }

    private static void bubbleSort(int[] values) {
        int temp;
        for (int i=0; i<values.length; i++) {
            for (int j = 0; j<values.length-1-i; j++) { 
                if (values[j] > values[j+1]) {  // This industry determines whether you grow from small to big or from big to small
                    temp = values[j];
                    values[j] = values[j+1];
                    values[j+1] = temp;
                }
                System.out.println(i + ":"+ Arrays.toString(values)); } System.out.println(); }}}Copy the code

After I typed the basic implementation, I added a lot of print to reproduce the process, and then it was easier to understand what each sentence of the program implemented and changed.

  1. Core implementation part, nested loop, compare one by one:

You can see that in this rowvalues[j] 和 values[j+1]The former element and the latter element. In my article, when the first one is bigger than the last one, you swap, which means you pile the first one back, and you cycle through it, like a bubble. One by one to the end.

The final sorting result:

  1. Here, the upper bound of j is not values.length, because every time I skip, the maximum value is already at the end.

  1. Let’s take a closer look at what happens in each loop:
  • The first loop:

In the first loop, there are 10 elements from 0 to 9, and we compare them in pairs nine times.

  • The second loop, the last two are definitely better, with one less comparison:

  • The third loop:

  • The fourth loop:

  • Fifth to ninth cycle:

That’s when you see why so many tuning articles say there’s duplication?

Here seems to have very great, we have, the number of bubbles above the number of comparisons, and each time the bubbling need are optimized, but that’s enough, don’t we can also compare the number of times to do further optimization, bubbling each round, the last time exchange index can be used as the next bubble is the number of times, if the value is 0, To prove that the entire array is ordered, just exit the outer loop. “Bad programmer juejin.cn/post/701632…”

Optimization!

The screenshot above clearly shows where the code can be optimized:

Let's not compare the cycles in order.

private static void bubbleSort(int[] values) {
    int temp;

    for (int i=0; i<values.length; i++) {
        boolean flag = true;
        for (int j = 0; j<values.length-1-i; j++) {
            if (values[j] > values[j+1]) {
                temp = values[j];
                values[j] = values[j+1];
                values[j+1] = temp;
                // The array is unordered at this time, and the comparison continues
                flag = false;
            }
            System.out.println(i + ":" + Arrays.toString(values));
        }
        // The internal loop is complete, and the flag is still true, indicating that the order is already in order
        if (flag) {
            break; } System.out.println(); }}Copy the code

We did this by adding a new Boolean variable:

After running again, we find that the previous loop is the same as before. The difference is that after sorting, there is no unnecessary comparison:

Eggs:

www.geeksforgeeks.org/bubble-sort…