排序：一. 冒泡排序 （前往后所有未排序的元素相邻比较）

系列文章共实现了六种排序算法：

1. 冒泡排序
2. 直接选择排序
3. 插入排序
4. 归并排序
5. 快速排序
6. 堆排序

定义了 Sortable 接口，每种排序方法实现该接口，在 sort 方法中实现排序。

public interface Sortable<T> {

    /**
     * 将数组进行排序
     *
     * @param sour       待排序的数组
     * @param comparator 排序规则
     * @return 数组中元素交换次数
     */
    int sort(T[] sour, Comparator<T> comparator);

}

测试示例如下：

public class Test {

    public static void main(String[] args) {

        Integer[] s = {1, 8, 9, 4, 3, 4, 3, 2, 1};
        Integer[] s1 = {1, 2, 4, 3, 5, 7};
        Integer[] s2 = {1, -2, 22223, 489, 335, 23437, 3, 4, 56, 76, 98, 12, 3421, 654};
        Integer[] s3 = P.getRandomArrays(1000, 10000);
        test2(s2);
    }

    // 测试堆排序
    private static void test2(Integer[] sour) {
        HeapSort heapSort = new HeapSort();
        P.out(sour);
        heapSort.sort(new MiniArrayHeap<>(), sour);
        P.out(sour);
    }

    private static void test1(Integer[] sour) {
        test(new SelectionSort<>(), sour); // 升序 交换 1 次
        test(new SelectionSort<>(), sour); // 升序 交换 5 次
    }

    private static <T extends Comparable> void test(Sortable<T> sortable, T... ts) {
        P.out(sortable.sort(ts, T::compareTo));
        P.out(Arrays.toString(ts));
    }

}

排序算法的稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

稳定性的好处。排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。

正文

参考文章

时间复杂度O(n2)，最好情况O(n)，最坏情况O(n2)，稳定。

适合数据规模很小的时候，而且它的效率也比较低。

通过重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

算法描述如下

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

BubbleSort sort 方法实现如下：

image.png

代码已上传 GitHub ，可以在 这里 找到