数据结构(八):冒泡排序

作者: 聪明的奇瑞 | 来源:发表于2018-02-26 17:39 被阅读68次
    • 冒泡排序是一种交换排序,通过比较相邻的元素,如果反顺序则交换,直到没有反序的元素为止

    冒泡排序代码

    int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
    // API 实现
    Arrays.sort(arr);
    // 冒泡排序
    int temp;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
        if(arr[j]>arr[j+1]){
            temp = arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;
            }
        }
    }
    
    • 优化:添加一个 flag 来判断当前循环是否已经有序,如果有序则退出循环
    boolean flag = true;
    int[] arr = new int[]{1, 3, 6, 4, 7, 8, 5, 10, 9};
    // 冒泡排序
    int temp;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if(arr[j]>arr[j+1]){
                temp = arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
                flag = false;
            }
        }
        if (!flag){
            break;  // 退出循环
        }
    }
    

    冒泡排序性能

    • 最好的情况就是排序的表本身就是有序的,那么我们只要比较次数,时间复杂度为 O(n),最坏的情况是排序表是逆序的的,时间复杂度为 O(n²)

    相关文章

      网友评论

        本文标题:数据结构(八):冒泡排序

        本文链接:https://www.haomeiwen.com/subject/nfnyxftx.html