浅谈冒泡排序

一、冒泡排序

冒泡排序是我们所掌握的最基础的排序算法之一，它的排序思想如下：
假设我们的排序要求为：数组大小为N的，从小到大的一个排序过程；
1 、排序思想
第一趟排序
（1）我们需要找出当前数组状态的第一个元素作为排序的起点；
（2）将数组相邻的元素进行比较，并且将数据较大的元素交换到相对靠后的位置上，即a[j]>a[j+1],则swap(a[j],a[j+1])，使得a[j+1]中总是存放相对较大的值；
（3）一趟排序结束，数组的第n-1元素即为该组数据的最大值；
..........
依次类推，第二趟只需对前面n-1个元素进行排序即可,且该趟排序的最大值放在数组的n-2元素位置......

例如：a[5]={3,2,4,1,5};

flag标志，初值为0，作为我们数组排序是否已经排序完成的标志，每趟排序flag初值均为1，当只要有一次相邻元素进行交换时，flag=0； flag=1时，表示数组元素为排好顺序。

Paste_Image.png

我们能发现最后一趟排序中flag的值已经为1，所以我们的排序过程也就结束了，由于第三趟的排序结果，已经是我们想要的结果啦，所以排序的第四趟只是检验我们第三趟排序的结果，所以当flag=1时，排序结束。

话不多说上代码

java

public class Bubble_Sort {
    public static void swap(int[] arr,int index1,int index2){
        int t;
        t=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=t;
    }
    public static void sort(int[] arr){
        boolean flag=false;
        int times=0;
        for (int i = 0; !flag && i < arr.length-1; i++) {
            flag=true;
            System.out.println("第"+ ++times +"排序");
            for (int j = 0; j < arr.length-i-1; j++) {
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flag=false;
                }
            }
        }
    }
    
    public static void print(int[] arr){
        System.out.println("排序结果：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }
    
    public static void main(String[] args){
        int[] arr={3,2,4,1,5};
        sort(arr);
        print(arr);
    }
}

总结：冒泡排序的算法最坏的情况下需要n-1趟的排序过程，所以该算法的时间复杂度为O（n^2）;
所需的辅助空间为1。