当前位置:网站首页>冒泡排序及冒泡排序的优化

冒泡排序及冒泡排序的优化

2022-01-15 02:32:07 朝上

思想

一个for循环遍历数组,让arr[ i ]和arr[ i+1 ]比较,如果arr[ i ] > arr[ i+1 ]就产生交换,
每一轮比较下来就是将该数组中最大的数冒出来,第几轮就是找第几大

在这里插入图片描述

时间复杂度 O(n)2

public class BubbleDemo {
    

    public static void main(String[] args) {
    

        int[] arr = {
    8,4,2,1,23,344,12};

        //i 比较轮数
        for (int i = 0; i < arr.length-1; i++) {
    
            //j 次数
            for (int j = 0; j < arr.length-i-1 ; j++) {
    
                //比较
                if(arr[j]>arr[j+1]){
    
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
        
        //输出
        for (int a : arr) {
    
            System.out.println(a);
        }
    }

}

优化:

针对轮进行优化

  • 思想:因为如果到了某一轮完全不产生交换(即全数组不满足 arr[ i ] > arr[ i+1 ] ),则表明该数组已经有序,我们可以直接再次处停下比较,拿一个boolean标记处理就好

针对每轮里面的比较次数进行优化

  • 思想:如果该数组比较特殊,即数组后部分已经有序,那程序会产生很多次无效比较,为了针对这种特殊情况的优化,基于冒泡排序第几轮找第几大的前提下,我们可以记录上一轮最后一次产生交换的位置,即已经找到了第x大(该数据下标记录为index),这一轮找第x-1大的数,我们可以只在前部分找(0-index)
public class BubbleSort {
    
    public static void main(String[] args) {
    
        //int[] arr={16,49,23,56,4,11,12};
        int[] arr={
    2,19,18,16,20,21,62};
        int index=arr.length-1;
        for (int i = 0; i < arr.length-1; i++) {
    //控制轮数
            boolean flag=true;//用来记录是否产生交换,没产生交换则表明元素已经有序
            int n=index; //用来减少每一轮比较 后面有有序序列 的重复比较次数,因为冒泡排序每次找最大
            for (int j = 0; j < n ; j++) {
    //控制每轮次数
                if(arr[j]>arr[j+1]){
    
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag=false;
                    index=j;
                }
                System.out.println(Arrays.toString(arr));
                System.out.println(index);
            }
            System.out.println();
            if(flag) break;
        }

    }
}

版权声明
本文为[朝上]所创,转载请带上原文链接,感谢
https://blog.csdn.net/m0_51051154/article/details/120100099

随机推荐