Personal blog portal

Graphic thinking

The largest/smallest number bubbles to the very end

Let’s say the array is length N

1. Compare two adjacent bits and swap the larger ones to the right until the NTH one is swapped
2. N minus one (step 1 makes the largest numberThe bubblingTo the far right)
3. Keep going 1 or 2 until n is equal to 1

implementation

        / / n
        for (int i = length - 1; i > 0; i--) {
            boolean isSwap = false;
            // Pairwise comparison
            for (int j = 0; j < i; j++) {
                if (array[j] > array[j + 1]) {
                    doSwap(array, j, j + 1);
                    isSwap = true; }}if(! isSwap) {return; }}Copy the code

Time complexity

O(n) ~ O(n^2)

Worst: When arrays are out of order

f(n) = n (n-1) / 2 = O(n^2)

Best: When the array is basically ordered, only one alignment is needed

f(n) = n = O(n)

Spatial complexity

Order 1, I don’t have to allocate any extra space

The complete code

public class BubbleSort {

    private static void sort(int[] array) {
        if (array == null || array.length == 1) {
            return;
        }
        int length = array.length;


        for (int i = length - 1; i > 0; i--) {
            boolean isSwap = false;
            for (int j = 0; j < i; j++) {
                if (array[j] > array[j + 1]) {
                    doSwap(array, j, j + 1);
                    isSwap = true; }}if(! isSwap) {return; }}}private static void doSwap(int[] array, int x, int y) {
        int t = array[x];
        array[x] = array[y];
        array[y] = t;
    }

    public static void main(String[] args) {
        int[] array = {111.52.77.98.36.12.13.48};
        sort(array);
        System.out.println(arrayToString(array));
    }

    private static String arrayToString(int[] array) {
        StringBuilder builder = new StringBuilder();
        for (int t : array) {
            builder.append(t + "");
        }
        returnbuilder.toString(); }}Copy the code