数据结构经典算法之四 冒泡排序及其优化算法

冒泡排序

基本思想：减治算法。根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

• 普通冒泡的基本算法：

1. 设置数组长度为N
2. 比较相邻两个数据大小，前 > 后,交换两个数
3. 从第0个数据遍历到第(N - 1)数，最大的数就沉到第(N - 1)个位置
4. N = N - 1,如果 N != 0 , 重复 2 - 3 两步，否则排序完成

void bubbleSort1(int[] array, int N){
    int i,j;
    //共(N - 1)次循环
    for(i = 0; i < N; i++){
        //一层循环
        for(j = 1; j < N - i; j++){
            if(array[j - 1] > array[j]){
                swap(array, array[j - 1] , array[j]);
            }
        }
    }
}

• 冒泡优化1.0的基本算法：

1. 对普通冒泡进行优化，设置一个标志flag
2. 如果这一趟排序发生了交换 flag == true,否则 flag == false
3. 如果flag == false 就代表这组数已经有序了

void bubbleSort2(int[] array, int N){
    int i;
    int j = N;
    boolean flag = true;

    while(flag){
        flag = false;
        for(i = 1; i < j; i++){
            if(array[i - 1] > array[i]){
                swap(array, array[i -1], array[i]);
                flag = true;
            }
            j--;
        }
    }
}

• 冒泡优化2.0的基本算法：

1. 假设一组数有50个元素，仅前10个元素无序，后40个数都已经排好序
2. 第一趟遍历完毕，发生交换的最后一个位置必定 < 10，并且这个位置之后的数据都已经有序
3. 定义一个标志flag记录下最后这个位置，下一次只要从数组头遍历到这个位置就可以了

void bubbleSort3(int[] array, int N){
    int i,j;
    int flag = N;
    while(flag > 0){
        j = flag;
        flag = 0;
        for(i = 1; i < j; i++){
            if(array[i - 1] > array[i]){
                swap(array, array[i - 1], array[i]);
                flag = i;
            }
        }
    }
}

• 把最小的数冒泡到最前面

void bubbleSort4(int[] array){

    for(int i = 0; i < array.length; i++){
        boolean flag = true;
        //有序[0,i)   无序[i,array.length - 1)
        //要把最小的数冒泡的最前面，需要从后往前冒泡
        for(int j = array.length - 1; j > i; j--){
            if(array[j - 1] > array[j]){
                swap(array, array[j - 1], array[j]);
                flag = false;
            }
        }
        if(flag){
            break;
        }
    }
}

• 把最大的数冒泡到最后面

void bubbleSort5(int[] array) {
    // 外部的循环表示的是，冒泡的次数
    // 一次冒泡可以解决一个数的问题
    // 一共需要 array.length
    // 更优化的方式是 array.length - 1
    for (int i = 0; i < array.length; i++) {
        
        // 每次冒泡之前，假设数组已经有序
        boolean sorted = true;

        // 一次冒泡的过程，保证最大的数被推到最后去
        for (int j = 0; j <= array.length - 2 - i; j++) {
            // 保证相邻的两个数，最大的在后面
            if (array[j] > array[j + 1]) {
        
                swap(array, array[j], array[j + 1]);
                sorted = false;
            }
        }

        // 如果过程一次交换都没发生过，假设有序成立
        if (sorted == true) {
            break;
        }
    }
}

冒泡排序特性总结：

1. 冒泡排序采用减治算法
2. 冒泡排序的效率较低，在数据规模很小时，可以采用
3. 时间复杂度：最好O(n),最坏O(n^ 2),平均O(n^2)
4. 空间复杂度：O(1)
5. 稳定性：稳定