冒泡排序算法

一、冒泡排序

冒泡排序的英文Bubble Sort，是一种最基础的交换排序。

大家一定都喝过汽水，汽水中常常有许多小小的气泡，哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻，所以小气泡可以一点一点向上浮动。

二、实现思路

使用双重循环，循环比较相邻的两个数字，把较小的数字移动到右边，步骤如下：

1. 第一次循环，相邻的两个数比较，小的数下沉到右边，循环比较length次，则会出现最小的数字在最后一位
2. 第二次循环，相邻的两个数比较，小的数据下沉到右边，循环比较 length-1 次（因为第一次最小的数已在最右边，不要再比较最后一位），则会出现第二小的数字在倒数第二位
3. 第n次循环，相邻的两个数比较，小的数据下沉到右边，循环比较 length-n 次，则会出现第二小的数字在倒数第n-1位

实现思路不清楚的可点此链接，有相关的图文介绍

三、代码实现

package xzg.algorithm;
/**
 * 冒泡排序算法
 */
public class BubbleSort {
    public static void main(String[] args) {
        int score[] = {3, 8, 1, 13, 24, 14, 41, 26, 5, 2};
        int[] bubbleSort = bubbleSort(score);
        System.out.print("冒泡排序结果：");
        for (int a = 0; a < score.length; a++) {
            System.out.print(score[a] + "\t");
        }
    }

    /**
     * 双重循环实现冒泡排序<p/>
     * 实现思路：<p/>
     * 1.第一次循环，相邻的两个数比较，小的数下沉到右边，循环比较length次，则会出现最小的数字在最后一位<p/>
     * 2.第二次循环，相邻的两个数比较，小的数据下沉到右边，循环比较 length-1 次（因为第一次最小的数已在最右边，不要再比较最后一位），则会出现第二小的数字在倒数第二位<p/>
     * 3.第n次循环，相邻的两个数比较，小的数据下沉到右边，循环比较 length-n 次，则会出现第二小的数字在倒数第n-1位<p/>
     *
     * @param arr 待排序数组
     * @return 排序完成的数组
     */
    public static int[] bubbleSort(int arr[]) {
        int length = arr.length;
        for (int i = 0; i < length - 1; i++) {
            //第i+1趟循环排序
            for (int j = 0; j < length - 1 - i; j++) {//循环比较 length - 1 - i次（因为后i项数据已排序完毕）
                if (arr[j] < arr[j + 1]) {//右边数据比左边的大，则交换位置
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.print("第" + (i + 1) + "次排序结果：");
            for (int a = 0; a < arr.length; a++) {
                System.out.print(arr[a] + "\t");
            }
            System.out.println();
        }
        return arr;
    }
}

bubbleSort方法输出结果如下：

第1次排序结果：8   3   13  24  14  41  26  5   2   1   
第2次排序结果：8   13  24  14  41  26  5   3   2   1   
第3次排序结果：13  24  14  41  26  8   5   3   2   1   
第4次排序结果：24  14  41  26  13  8   5   3   2   1   
第5次排序结果：24  41  26  14  13  8   5   3   2   1   
第6次排序结果：41  26  24  14  13  8   5   3   2   1   
第7次排序结果：41  26  24  14  13  8   5   3   2   1   
第8次排序结果：41  26  24  14  13  8   5   3   2   1   
第9次排序结果：41  26  24  14  13  8   5   3   2   1   
冒泡排序结果：41   26  24  14  13  8   5   3   2   1   
Process finished with exit code 0

可以看到其实到第6次排序后，已经排序成功了，相关算法是否可以优化呢？
答案是肯定的，我们可以增加一个标示位，用于标示第n次排列时，是否有进行位置交换，如果没有进行交换(说明已排序完毕)，则终止排序即可。

优化后的代码如下：

  public static int[] bubbleSortOptimize(int arr[]) {
        int length = arr.length;
        for (int i = 0; i < length - 1; i++) {
            boolean isMove = false;//用于表示第i+1趟排序中是否有移动交换数据，如果没有则说明已排序完成，无需再次循环比较
            //第i+1趟循环排序
            for (int j = 0; j < length - 1 - i; j++) {//循环比较 length - 1 - i次（因为后i项数据已排序完毕）
                if (arr[j] < arr[j + 1]) {//右边数据比左边的大，则交换位置
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    //有移动交换数据，修改标示
                    isMove = true;
                }
            }
            if (!isMove){//如果没有移动交换数据则说明已排序完成，无需再次循环比较
                System.out.println("冒泡排序完成，无需再次比较数据");
                break;
            }
            System.out.print("第" + (i + 1) + "次排序结果：");
            for (int a = 0; a < arr.length; a++) {
                System.out.print(arr[a] + "\t");
            }
            System.out.println();
        }
        return arr;
    }

以下是优化后的排序输出结果。

bubbleSortOptimize方法输出结果如下：

第1次排序结果：8   3   13  24  14  41  26  5   2   1   
第2次排序结果：8   13  24  14  41  26  5   3   2   1   
第3次排序结果：13  24  14  41  26  8   5   3   2   1   
第4次排序结果：24  14  41  26  13  8   5   3   2   1   
第5次排序结果：24  41  26  14  13  8   5   3   2   1   
第6次排序结果：41  26  24  14  13  8   5   3   2   1   
冒泡排序完成，无需再次比较数据
冒泡排序结果：41   26  24  14  13  8   5   3   2   1   
Process finished with exit code 0

四、算法分析

冒泡排序总的平均时间复杂度为O(n^2)

参考文章如下：
https://www.cnblogs.com/lisaShare/p/9988043.html