冒泡排序（Java）-CSDN博客

基本思想

1. 比较前后相邻的二个数据如果前面数据大于后面的数据就将这二个数据交换。
2. 这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后最大的一个数据就“沉”到数组第N-1 个位置。
3. 如此循环 (N-1)次每次循环需要比较的个数 N 都减 1。当 N = 0 时结束。

代码实现

public static void bubbleSort(int[] arr) {
    for (int times = arr.length - 2; times > 0; times--) {
        for (int pivot = 0; pivot <= times; pivot++) {
            if (arr[pivot] > arr[pivot + 1]) {
                int temp = arr[pivot];
                arr[pivot] = arr[pivot + 1];
                arr[pivot + 1] = temp;
            }
        }
    }
}

算法复杂度

假设排序的元素个数为 n则需要循环 n-1 次每次比较次数都减1也就是说一次循环中最多比较n-1次 最少比较1次。所以 T(n) = n(n+1)/2O(n) = n²。