冒泡排序思路

1、對(duì)元素進(jìn)行兩次遍歷

2、第一次遍歷所有元素

3、第二次判斷當(dāng)前元素是否比之后的元素大，如果大則交換位置，否則不動(dòng)

冒泡排序理解

冒泡排序是一種常用的排序算法。從思路理解上比插入排序、快排、歸并排序都要簡(jiǎn)單。就是做兩次嵌套循環(huán)，一旦發(fā)現(xiàn)前面的數(shù)比后面的數(shù)大，就交換位置。像氣泡從水里升上來(lái)一樣，越往上氣泡越大。

冒泡排序復(fù)雜度

冒泡排序是對(duì)元素做兩次嵌套的循環(huán)，顯而易見，時(shí)間復(fù)雜度是O(n^2)。

冒泡排序JAVA實(shí)現(xiàn)

public class Main {
 
    public static void main(String[] args) {
        int[] arr = new int[10000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Math.toIntExact(Math.round(Math.random() * 1000));
        }
        bubbleSortII(arr);
        System.out.println(Arrays.toString(arr));
    }
 
    /**
     * 常見冒泡排序
     *
     * @param arr
     */
    private static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
 
    /**
     * 冒泡排序優(yōu)化
     *
     * @param arr
     */
    private static void bubbleSortII(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}