Java版冒泡排序

分析&回答

动态演示 -> 跳转到博客查看

实现代码

/**
 * 冒泡排序算法的运作如下:
 *
 *  比较相邻的元素。如果第一个比第二个大，就交换他们两个。
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
 *  针对所有的元素重复以上的步骤，除了最后一个。
 *  持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
 *
 * @param sortArr
 */
private static void bubbleSort(int[] sortArr) {
    //开始冒泡排序
    //外层是要比较的趟数（这里注意要从1开始，否则内层循环就越界了）
    for (int i = 1; i < sortArr.length; i++) {
        boolean flag = true;
        //内层是一趟中具体的比较次数，每次要做的事情就是相邻数字比较，交换
        for (int j = 0; j < sortArr.length - i; j++) {
            if (sortArr[j] > sortArr[j + 1]) {
                int temp = sortArr[j];
                sortArr[j] = sortArr[j + 1];
                sortArr[j + 1] = temp;
                flag = false;
            }
        }
        if (flag) {  //如果一趟下来没有发生交换，说明已经有序
            break;
        }
    }
}

性能分析

• 稳定 
• 平均时间复杂度O(n²) 
• 空间复杂度O(1) 

反思&扩展

Java版常用排序算法复杂度

喵呜面试助手： 一站式解决面试问题，你可以搜索微信小程序 [喵呜面试助手] 或关注 [喵呜刷题] -> 面试助手 免费刷题。如有好的面试知识或技巧期待您的共享！