1. An overview of the

Old rules, they do not write a summary and overview, you can see the introduction of the encyclopedia, write very good: baike.baidu.com/item/%E5%86…

The basic process is as follows:

1. The first round:
   • Arr [0] is compared with ARR [1]. If ARR [1] is large, they exchange with each other.
   • .
   • Arr [I] is compared with ARR [I +1], if ARR [I] is large, they interchange;
   • .
   • Arr [n-2] is compared with ARR [n-1]. If ARR [n-2] is large, they exchange with each other.
   • After the first round, the largest number from 0 to n-1 goes to ARr [n-1]
2. The second round:
   • Arr [0] is compared with ARR [1]. If ARR [1] is large, they exchange with each other.
   • .
   • Arr [I] is compared with ARR [I +1], if ARR [I] is large, they interchange;
   • .
   • Arr [n-3] is compared with ARR [n-2], if ARR [n-2] is large, they interchange
   • After the second round, the largest number of 0-n-2 is arR [n-2].
3. Round 3 ~ Round N-1
   • .
4. The first n round
   • Arr [0] is compared with ARR [0],

2. Code implementation

package com.omg.sort;

import java.util.Arrays;

/ * * *@description: bubble sort * First round: * ARR [0] is compared with ARR [1], if ARR [1] is large, they swap each other; *... * ArR [I] is compared with ARR [I +1], if ARR [I] is large, they interchange; *... * ArR [n-2] is compared with ARR [n-1], if ARR [n-2] is large, they exchange with each other; * After the first round, the largest number from 0 to n-1 reaches ARr [n-1] * * In the second round: * ARr [0] is compared with ARr [1], if ARr [1] is large, they swap each other; *... * ArR [I] is compared with ARR [I +1], if ARR [I] is large, they interchange; *... * arr[n-3] is compared with ARr [n-2], if ARr [n-2] is large, swap with each other * down the second round, the largest number of 0-n-2 is arr[n-2] *... * * Comparison of round n * ARR [0] with ARR [0], */
public class Code02_BubbleSort {
    public static void bubbleSort(int[] arr){
        if (null == arr || arr.length <= 1) {return;
        }

        for (int i = arr.length - 1; i > 0; i--){
            for (int j=0; j < i; j++){
                if (arr[j] > arr[j+1]){
                    swap(arr, j, j+1); }}}}public static void swap(int[] arr, int i, int j){
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    public static void comparator(int[] arr){
        Arrays.sort(arr);
    }

    / * * *@description: Generates a random set of numbers that are used to test sorting and compare the results with the logarithm *@paramMaxSize The maximum length of the array *@paramMaxValue Specifies the value range of the elements in the array [-maxValu, maxValu] */
    public static int[] generateRandomArray(int maxSize, int maxValue){
        int size = (int)(Math.random()*(maxSize+1));
        int[] arr = new int[size];
        for (int i=0; i<arr.length; i++){
            [-maxValue, maxValue]
            arr[i] = (int)(Math.random()*(maxValue+1)) - (int)(Math.random()*(maxValue+1));
        }
        return arr;
    }

    / * * *@description: array copy, create an identical array for log-sort comparison */
    public static int[] copyArray(int[] arr){
        if (arr == null) {
            return null;
        }

        int[] res = new int[arr.length];
        for (int i=0; i<arr.length; i++){
            res[i] = arr[i];
        }

        return res;
    }

    / * * *@description: checks whether two arrays are the same */
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if (arr1 == arr2){
            return true;
        }

        if(arr1.length ! = arr2.length){return false;
        }

        if(arr1 ! =null&& arr2 ! =null) {for (int i=0; i<arr1.length; i++){
                if(arr1[i] ! = arr2[i]){return false; }}}return true;
    }

    / * * *@description: Prints the array. If the sorting result is inconsistent with the logarithm result, it can be printed to facilitate analysis of the problem
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "");
        }
        System.out.println();
    }


    public static void main(String[] args) {
        // Number of tests
        int testTime = 50000;
        // Maximum length of array
        int maxSize = 100;
        // Range of elements in array [-100, 100]
        int maxValue = 100;
        boolean succeed = true;
        for (int i=0; i<testTime; i++){
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            bubbleSort(arr1);
            comparator(arr2);
            // Compare the result of selectable sorting with the result of logarithm, break out of the loop if inconsistent
            if(! isEqual(arr1, arr2)){ succeed =false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }

        System.out.println(succeed ? "Nice!" : "Fucking fucked!"); }}Copy the code

3. Time complexity and space complexity

Time complexity derivation is O(n^2) space complexity is O(1), just like selection sort.