Java冒泡排序（Bubble Sort）

1.冒泡排序

冒泡排序（Bubble Sort）是编程中较简单的一种排序算法。它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误，就把它们交换过来。重复地进行走访数列的工作直到没有再需要交换的元素，这也就意味着该数列已经完成排序。

冒泡排序就像气泡从水中出现一样，在气泡排序中最小或最大的数字，取决于我们是按升序还是降序排序数组，气泡朝着数组的开始或结束冒出。

2.冒泡排序的算法原理

1）比较相邻的元素，如果第一个比第二个大，就交换他们两个。

2）对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对，在这一点，最后的元素应该会是最大的数。

3）针对所有的元素重复以上的步骤，除了最后一个。

4）持续对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

3.冒泡排序的复杂度和性能

与其他排序算法，诸如快速排序、归并排序或shell排序相比，冒泡排序表现不佳。这些算法的平均情况复杂度为O(nlogn)，而冒泡排序平均情况复杂度为O(n^2)。

在最佳情况下，冒泡排序比具有O(n)性能的快速排序更好。冒泡排序比快速排序或归并排序慢三倍，即使n=100，但它更容易实现和记忆。

冒泡排序的复杂度和性能如下：

1）冒泡排序最差情况性能O(n^2)

2）冒泡排序最佳情况性能O(n)

3）冒泡排序平均情况性能O(n^2)

4.形成代码

//冒泡排序
public static void bubbleSort(int[] arr) {
    //外层循环用来控制数组循环的圈数
    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;
            }
        }
    }
    //输出结果
    for(int n:nums) {
        System.out.println(n);
    }
}

例如：

public class Main {
    public static void main(String[] args) {
        int a[] = {6,1,15,32,9};
        for(int i=1;i<a.length;i++) {
            for(int j=0;j<a.length-1;j++) {
                if(a[j] > a[j+1]) {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
        System.out.println("冒泡排序的结果是：");
        for(int temp:a) {
            System.out.print(temp+" ");
        }
    }
}

运行结果如下：

冒泡排序的结果是：
1 6 9 15 32

大家可以亲自上机实验！