冒泡排序算法

简介

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

原理

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
   怎么比较，比较什么？那要看你关心的是什么，比如数组元素是数字，你希望升序排列，遇到2和1比较，那就需要交换，让1排在2前面。再比如你希望已某个key排序，这个key可以是学生的学号、名字、年龄等任何你关心的信息。

2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。如果从头到尾都没有发生交换，即表示排序完成，可直接退出。

3. 重复[步骤2]，你会发现随着[步骤2]不断进行，数组从后往前依次排好序的元素越来越多。（因为[步骤2]每次会把当前最大的数往后挪）

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

举例

例子1：数组array = [5,4,3,2,1]升序排列

//开始
第一阶段（5逐步向后移动，因为当前5是数组中最大的）
[4,5,3,2,1]//5和4比较，交换，继续
[4,3,5,2,1]//5和3比较，交换，继续
[4,3,2,5,1]//5和2比较，交换，继续
[4,3,2,1,5]//5和1比较，交换，继续
第二阶段（4逐步向后移动）
[3,4,2,1,5]
[3,2,4,1,5]
[3,2,1,4,5]
第三阶段（3逐步向后移动）
[2,3,1,4,5]
[2,1,3,4,5]
第四阶段（2逐步向后移动）
[1,2,3,4,5]
//结束

例子2：数组array = [1,2,3,4,5]升序排列（很明显，这个数组本来就是升序的，当是需要让程序知道。。。其实排序过程也算是验证过程）

//开始
第一阶段
[1,2,3,4,5]//1和2比较，不用交换，继续
[1,2,3,4,5]//2和3比较，不用交换，继续
[1,2,3,4,5]//3和4比较，不用交换，继续
[1,2,3,4,5]//4和5比较，不用交换，整个阶段一次交换也没有，说明什么？直接愤怒的结束就好了！！！
//结束

冒泡排序的Java实现

核心方法

//冒泡排序核心方法，isAscending表示是否升序
public void sort(boolean isAscending) {
        int[] data = super.getData();
        if (data == null || data.length < 2) {
            return;
        }
        int changeSize;
        //阶段
        for (int i = 0; i < data.length; i++) {
            changeSize = 0;
            //阶段中的具体交换过程
            for (int j = 0; j < data.length - 1 - i; j++) {
                int a = data[j];
                int b = data[j + 1];
                if (a == b) {
                    continue;
                }
                boolean largeThan = a > b;
                if (largeThan && isAscending || !largeThan && !isAscending) {
                    super.swap(data, j, j + 1);
                    changeSize++;
                }
            }
            if (changeSize == 0) {
                break;
            }
        }
    }

全部代码:（包导入信息自己设置）
AbstractSort.java

public abstract class AbstractSort {
    private int[] data;

    public AbstractSort(int[] data) {
        this.data = data;
    }

    public abstract void sort(boolean isAscending);

    public void sort() {
        this.sort(true);
    }

    public int[] getData() {
        return data;
    }

    public void print() {
        for (int i : this.data) {
            System.out.println(i);
        }
    }

    protected void swap(int[] data, int indexA, int indexB) {
        int temp = data[indexA];
        data[indexA] = data[indexB];
        data[indexB] = temp;
    }
}

BubbleSort.java

public class BubbleSort extends AbstractSort {

    public BubbleSort(int[] data) {
        super(data);
    }

    @Override
    public void sort(boolean isAscending) {
        int[] data = super.getData();
        if (data == null || data.length < 2) {
            return;
        }
        int changeSize;
        for (int i = 0; i < data.length; i++) {
            changeSize = 0;
            for (int j = 0; j < data.length - 1 - i; j++) {
                int a = data[j];
                int b = data[j + 1];
                if (a == b) {
                    continue;
                }
                boolean largeThan = a > b;
                if (largeThan && isAscending || !largeThan && !isAscending) {
                    super.swap(data, j, j + 1);
                    changeSize++;
                }
            }
            if (changeSize == 0) {
                break;
            }
        }
    }
}