如需转载请评论或简信，并注明出处，未经允许不得转载

概述

冒泡排序就是依次比较相邻的两个数，将值较大的数放到后面的排序算法。每进行一趟排序都会找出一个较大值，所以每进行一趟排序，就会少比较一次

时间复杂度

O(n²)

排序过程

初始化：

第一趟排序：

第一次排序：6和3比较，6大于3，交换位置： 3 6 8 2 9 1

第二次排序：6和8比较，6小于8，不交换位置：3 6 8 2 9 1

第三次排序：8和2比较，8大于2，交换位置： 3 6 2 8 9 1

第四次排序：8和9比较，8小于9，不交换位置：3 6 2 8 9 1

第五次排序：9和1比较：9大于1，交换位置： 3 6 2 8 1 9

第二趟排序：

第一次排序：3和6比较，3小于6，不交换位置：3 6 2 8 1 9

第二次排序：6和2比较，6大于2，交换位置： 3 2 6 8 1 9

第三次排序：6和8比较，6大于8，不交换位置：3 2 6 8 1 9

第四次排序：8和1比较，8大于1，交换位置： 3 2 6 1 8 9

第三趟排序：

第一次排序：3和2比较，3大于2，交换位置： 2 3 6 1 8 9

第二次排序：3和6比较，3小于6，不交换位置：2 3 6 1 8 9

第三次排序：6和1比较，6大于1，交换位置： 2 3 1 6 8 9

第四趟排序：

第一次排序：2和3比较，2小于3，不交换位置：2 3 1 6 8 9

第二次排序：3和1比较，3大于1，交换位置： 2 1 3 6 8 9

第五趟排序：

第一次排序：2和1比较，2大于1，交换位置： 1 2 3 6 8 9

代码

public static void sort(int[] arr) {
    int n = arr.length;
    //外层循环控制排序趟数
    for (int i = 0; i < n - 1; i++) {
        //内层循环控制每一趟排序多少次
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}


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

性能测试

随机生成10,000个从0到10,000的数，分别进行五次测试，效果如下

次数	性能
1	281ms
2	325ms
3	323ms
4	263ms
5	293ms

随机生成100,000个从0到100,000的数，分别进行五次测试，效果如下

次数	性能
1	23003ms
2	22515ms
3	21579ms
4	21698ms
5	22108ms