title: 算法基础——冒泡排序
date: 2019-11-29 16:16:29
categories:

• Algorithms
  tags:
• 排序算法

排序

冒泡排序

通过重复的走访要排序的元素列，依次比较相邻的每个元素，如果顺序错误就交换。

代码

/* 冒泡排序 */
/* 1. 从当前元素起，向后依次比较每一对相邻元素，若逆序则交换 */
/* 2. 对所有元素均重复以上步骤，直至最后一个元素 */
public static void bubbleSort(int [] arr){
    for(int i=1;i<arr.length;i++){    //外循环为排序躺数，length长度，循环 length-1次
        for(int j=0;j<arr.length-i;++){ //内循环为第i趟比较的次数，第i趟比较 length-i次
            if(arr[j]>arr[j+1]){  //如果前者大于后者，则交换
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] =temp;
            }
        }
    }
}

笔记

使用了双层嵌套循环，时间复杂的是O(N²)

这里有个问题，如果说在外循环结束前已经排序好了，但是任然要执行外循环。

代码优化

• 设置一个标识，用来确定是否已经排序好了
• 排序好的标志就是，未发生交换，所以我们可以设置flag = false，如果发生交换则改为true
• 如果一趟循环下来，flag任然是false则代表已经排序好，直接退出循环

/** * 对上述代码就行优化 */
public static void bubbleSort(int [] arr){
    for(int i=1;i<arr.length;i++){    //外循环为排序躺数，length长度，循环 length-1次
        boolean flag = false; //每次循环前初始化flag= false
        for(int j=0;j<arr.length-i;++){ //内循环为第i趟比较的次数，第i趟比较 length-i次
            if(arr[j]>arr[j+1]){  //如果前者大于后者，则交换
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] =temp;
                flag = true; //发生比较 。flag =true
            }
            if(!flag){ //循环结束后，任然为false说明排序好了，跳出外循环
                break;
            }
        }
    }
}