← 返回学习路线

SYSTEM

冒泡排序

Java基础冒泡排序system
src/content/notes/system/冒泡排序.md

排序

冒泡排序

冒泡排序(Bubble Sort):两个数比较大小,较大的数下沉,较小的数冒起来

算法描述:每次从数组的第一个位置开始两两比较,把较大的元素与较小的元素进行层层交换,最终把当前最大的一个元素存入到数组当前的末尾

实现思路:

  1. 确定总共需要冒几轮:数组的长度-1
  2. 每轮两两比较几次
// 0 1位置比较,大的放后面,然后1 2位置比较,大的继续放后面,一轮循环最后一位是最大值
public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {55, 22, 2, 5, 1, 3, 8, 5, 7, 4, 3, 99, 88};
        int flag;//标记本趟排序是否发生了交换
        //比较i和i+1,不需要再比最后一个位置
        for (int i = 0; i < arr.length - 1; i++) {
            flag = 0;
            //最后i位不需要比,已经排序好
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = 1;//发生了交换
                }
            }
            //没有发生交换,证明已经有序,不需要继续排序,节省时间
            if(flag == 0) {
                break;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

冒泡排序时间复杂度:最坏情况

  • 元素比较的次数为:(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2
  • 元素交换的次数为:(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2
  • 总执行次数为:(N^2/2-N/2)+(N^2/2-N/2)=N^2-N

按照大 O 推导法则,保留函数中的最高阶项那么最终冒泡排序的时间复杂度为 O(N^2)