This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

One, foreword

The principle of Bubble Sort is that each time you go through a set of numbers, you constantly compare two adjacent elements, and if they are not in the right order, you swap the two elements, for example, swapping the larger one to the next.

  • The first walk determines the largest element and puts it in the last place

  • A second pass determines the second largest element, and so on

  • After doing this N times, the array becomes incrementally ordered

Ju Li, the GIF is as follows:


Two, knowledge points

Knowledge points, as follows:

  1. Time complexity

  2. The reverse of

  3. Implementation: Simple implementation

    • Improved: Sentinel mode reduces invalid comparisons
    • Improved version: Reduces invalid comparisons

PS: Intern interview, will encounter


(1) Time complexity

  • Best case: order, time complexityO(N)
  • Best case: reverse order, time complexityO(N ^ 2)
  • Stability: Stable, that is, in the original array, element B comes after element A. In the sorting process, element B does not come before element A

General sorting diagram, as shown in figure:


(2)

If arr[I] > A [j] for subscript I < j, (I, j) is an inversion pair.

For example, sequence{34, 8, 64, 51, 32, 21}How many inversions are there?

Nine: (34, 8), (34, 32), (34, 21), (64, 51), (64, 32), (64, 21), (51, 32), (51, 21), (32, 21)Copy the code

Obtained theorem:

  • Theorem: ArbitraryNA sequence of different elements has an average ofN(N-1)/4A reverse order to
  • Theorem: The average time complexity of any algorithm that sorts only by swapping two adjacent elements isO(N^2)

So what’s the use of reverse pairs?

  1. It’s the number of swaps you have to make.

  2. It provides the basis for improving the efficiency of the algorithm

In order to improve the efficiency of the algorithm, it is necessary to:

  1. It cancels out more than one inversion pair at a time

  2. Swap two elements far apart at a time


(3) implementation

Determine the position of the trailing element each time.

Simple implementation, as follows:

public class BubbleSort {

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // Time: O(n^2), Space: O(1)
    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        int n = arr.length;
        for (int end = n - 1; end > 0; --end)
            for (int i = 0; i < end; ++i)
                if (arr[i] > arr[i+1])
                    swap(arr, i, i+1); }}Copy the code


1) Improved version: Sentinel mode, reduce invalid comparison

If a traversal does not swap, it is already ordered.

Just add an identity bit and the code looks like this:

public class BubbleSort {

    // Time: O(n^2), Space: O(1)
    public void sortEarlyReturn(int[] arr) {
        if (arr == null || arr.length == 0) return;
        int n = arr.length;
        boolean swapped;
        for (int end = n-1; end > 0; --end) {
            swapped = false;
            for (int i = 0; i < end; ++i) {
                if (arr[i] > arr[i+1]) {
                    swap(arr, i, i+1);
                    swapped = true; }}// If there is no exchange, exit
            if(! swapped)return; }}private void swap(int[] arr, int i, int j) {
        inttmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }}Copy the code


2) Improved version: Reduce invalid comparisons

To use the last fixed position, the code is as follows:

public class BubbleSort {

    // Time: O(n^2), Space: O(1)
    public void sortSkip(int[] arr) {
        if (arr == null || arr.length == 0) return;
        int n = arr.length;
        // Last fixed position
        int newEnd;
        for (int end = n-1; end > 0;) {
            newEnd = 0;
            for (int i = 0; i < end; ++i) {
                if (arr[i] > arr[i+1]) {
                    swap(arr, i, i+1); newEnd = i; } } end = newEnd; }}private void swap(int[] arr, int i, int j) {
        inttmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }}Copy the code