算法-冒泡排序

冒泡排序应该是我们最先接触到的排序算法了，其思想很简单，将一个数组内的数据，从下到上依次冒泡(比较)，如果下一个值小于当前值则交换，否则不进行交换，直到最顶层，java实现代码如下

/**
 * 冒泡排序,时间复杂第O(n^2)，原地排序
 * @param data ： 需要排序的数组
 */
public static void bubbleSort(int[] data) {
    int tmp;
    // 冒泡次数，由于每次冒泡出来的都是当前未完成冒泡元素的最大值，所以只需要冒泡n-1次即可，最后一个一定为最小值
    for (int i = 0; i < data.length - 1; i++) {
        for (int j = 0; j < data.length - i - 1; j++) {
            if (data[j] > data[j+1]) {
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
}

/**
 * 冒泡排序优化版，若一次排序没有发生交换则直接返回,,时间复杂第O(n^2)原地排序
 * @param data 需要排序的数组
 */
public static void bubbleSort2(int[] data) {
    int tmp;
    // 设置一个标志位，如果某一次冒泡排序没有进行任何替换则说明已经排序完毕
    int changeFlag;
    for (int i = 0; i < data.length - 1; i++) {
        changeFlag = 0;
        for (int j = 0; j < data.length - 1 - i; j++) {
            if (data[j] > data[j+1]) {
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
                changeFlag = 1;
            }
        }
        if (changeFlag != 1) {
            return;
        }
    }
}