高质量的冒泡排序

冒泡排序

冒泡排序是诸多渐近时间复杂度为O(n^2)的排序算法中的一种，很多人知道这个算法并认为自己可以写出一个好的冒泡排序，其实不然，就这么一个简单的算法也有很多值得玩味的地方，话不多说直接上代码，不做过多解释，大家自己玩味。

 import java.util.Comparator;

 public final class ArrayUtil {
    @FunctionalInterface
    private interface BinaryOperation<T> {
        int doCompare(T o1, T o2);
    }

    private ArrayUtil() {
        throw new AssertionError();
    }

    private static <T> void _bubbleSort(T[] array, BinaryOperation<T> op) {
        boolean swapped = true;
        for (int i = 1, len = array.length; swapped && i <= len - 1; ++i) {
            swapped = false;
            for (int j = 0; j < len - i; ++j) {
                if (op.doCompare(array[j], array[j + 1]) > 0) {
                    T temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            if (swapped) {
                swapped = false;
                for (int j = len - i - 1; j > 0; --j) {
                    if (op.doCompare(array[j], array[j - 1]) < 0) {
                        T temp = array[j];
                        array[j] = array[j - 1];
                        array[j - 1] = temp;
                        swapped = true;
                    }
                }
            }
        }
    }

    public static <T> void bubbleSort(T[] array, Comparator<T> comp) {
        _bubbleSort(array, (o1, o2) -> { return comp.compare(o1, o2); });
    }

    public static <T extends Comparable<T>> void bubbleSort(T[] array) {
        _bubbleSort(array, (o1, o2) -> { return o1.compareTo(o2); });
    }

}