冒泡排序

文章目录

• 基本原理
• 代码实现
• • 基础实现
  • 优化代码

基本原理

将序列当中的左右元素，依次比较，如果左边的元素大于右边元素则交换位置，保证右边的元素始终大于左边的元素;( 第一轮结束后，序列最后一个元素一定是当前序列的最大值;)对序列当中剩下的n-1个元素再次执行步骤1。对于长度为n的序列，一共需要执行n-1轮比较。

代码实现

基础实现

/**
 * 冒泡排序的第一种实现, 没有任何优化
 */
public class HelloWorld {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //动态创建数组
        int[] arr = new int[sc.nextInt()];
        for(int i = 0 ; i< arr.length ; i++){
            arr[i] = sc.nextInt();
        }
        /********** Begin **********/
        for(int i=0;i<arr.length-1;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;
                }

            }
        }
    
        System.out.print(Arrays.toString(arr));
        
        /********** End **********/
    }
}    

优化代码

如果对于一个本身有序的序列，或则序列后面一大部分都是有序的序列，上面的算法就会浪费很多的时间开销，这里设置一个标志flag，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。

/**
 * 设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。
 * @param a
 * @param n
 */

public class HelloWorld {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //动态创建数组
        int[] arr = new int[sc.nextInt()];
        for(int i = 0 ; i< arr.length ; i++){
            arr[i] = sc.nextInt();
        }
        /********** Begin **********/
        boolean flag=true;
        while(flag){
            flag=false;
        for(int i=0;i<arr.length-1;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=true;  //发生交换flag就为true。
                }

            }
        }

    }
    
        System.out.print(Arrays.toString(arr));

        /********** End **********/
    }
}