冒泡排序实现

冒泡排序实现

冒泡排序大家都很熟悉，他是每次拿开头的元素与后面的元素进行比较，如果遇到比他大的数就交换位置，这样一趟下来就会有一个最大的数到了数组的尾部。下一次进行比较，那些已经被排入到数组末尾的数就不再参与比较

时间复杂度（o^2)

（他是稳定的：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。）

有时候看这个双重循环突然有些懵逼了，怎么也想不通，温习的时候可以将每趟排序是什么样的都写下来，再把这个单层循环的方法改进成双重循环加深理解

import java.util.Arrays;


public class SortTest1 {
    public static void main(String[] args) {
        int arr[]={3,1,6,4,2};
        for(int i=0;iarr[i+1]){
                int swap;
                swap=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=swap;
            }
        }
        System.out.println("第一次排序："+Arrays.toString(arr));
        for(int i=0;iarr[i+1]){
                int swap;
                swap=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=swap;
            }
        }
        System.out.println("第二次排序："+Arrays.toString(arr));
        for(int i=0;iarr[i+1]){
                int swap;
                swap=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=swap;
            }
        }
        System.out.println("第三次排序："+Arrays.toString(arr));
        for(int i=0;iarr[i+1]){
                int swap;
                swap=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=swap;
            }
        }
        System.out.println("第四次排序："+Arrays.toString(arr));
   
        
    }

写完上面的程序发现，他们排序内容都是一个样子的，只是 i 

代码实现：

首先将排序算法写进一个方法中：

import java.util.Arrays;

public class BubberSort {   
    public void sort(int arr[]){
        for (int i =0; iarr[j + 1])
                {
                    temp=arr[j + 1];
                    arr[j + 1]=arr[j];
                    arr[j] =temp;
                }
            }
            System.out.println("这是第"+i+"趟排序"+ Arrays.toString(arr));
        }
    }
}

Run方法，调用上面的排序方法： 

public class Run {
    public static void main(String[] args) {
        BubberSort bubberSort = new BubberSort();
        int arr[]= {1,3,2,7,8,10,16,45,23};
        bubberSort.sort(arr);
    }
}

运行结果： 

 可以看到从第2趟排序开始，后面的位置就没有再发生改动了，这个就是可以优化的地方，我们检测每次排序是不是有元素发生了位置的交换，如果没有就直接将数组输出了，这样节省了很多时间

import java.util.Arrays;


public class BubberSort {
    @Test
    public void sort(int arr[]){
        boolean flag=false;
        for (int i = 0; i < arr.length-1; i++)
        {
            for (int j = 0; j < arr.length -  i - 1; j++)
            {
                int temp;
                if (arr[j] > arr[j + 1])
                {
                    flag=true;
                    temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println("这是第"+i+"趟排序"+ Arrays.toString(arr));
            if(!flag){
                break;
            }else{
                flag=false;
            }
        }
    }
}

可以看到这比上面少做了很多无用功，仅用了2次排序就结束了 

 

我们来看一下冒泡排序的时间怎么样

先创建一个80000大小的数组，用随机数填充，打印出执行排序前后的时间

import java.text.SimpleDateFormat;
import java.util.Date;

public class Run {
    public static void main(String[] args) {
        BubberSort bubberSort = new BubberSort();
        int arr[]=new int[80000];
        for(int i=0;i<80000;i++){
            arr[i]=(int)(Math.random()*8000000);//随机数的范围是[0,1）*8000000
        }

        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String time = simpleDateFormat.format(date);
        System.out.println("排序前的时间"+time);

        bubberSort.sort(arr);

        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat1 = new SimpleDateFormat("yyyy-MM-dd :HH:mm:ss");
        String time2 = simpleDateFormat.format(date1);
        System.out.println("这是排序后的时间"+time2);
    }
}

我测试大概都是10~11秒左右不是很快。