排序算法——冒泡排序

原理

数据分为 无序 | 有序两个部分。以升序为例，在一次冒泡过程中将通过两两比较，大的右移，将最大值调整到有序部分最左。重复该过程，直到有序部分长度等于数据源长度。

优化点

如果某次冒泡过程中没有发生交换，则说明数据处于有序状态，排序停止

复杂度分析

平均时间复杂度为O(n^2)
时间复杂度最坏为O(n^2)
空间复杂度为 O(1)
稳定，两两比较的时候顺序正确不会进行交换

代码实现

/**
 * 冒泡排序
 * 两两比较，大的右移到有序部分最末
 **/
public void sort(List<V> dataList, Comparator<V> comparator){
    V lastElem, elem;
    for (int index = dataList.size() - 1; index > 0; index--) {
        lastElem = dataList.get(0);
        boolean needSort = true;//需要排序的标志位
        for (int j=1; j <= index && needSort; j++) {
            needSort = false;
            elem = dataList.get(j);
            if (comparator.compare(lastElem, elem) > 0) {//switch
                dataList.set(j-1, elem);
                dataList.set(j, lastElem);
                needSort = true;
            } else{
                lastElem = elem;    
            }
        }
    }
}