数据结构与算法-冒泡排序

什么是冒泡排序
冒泡排序是一种计算机领域较为简单的一种排序算法，因为排序的元素由小到大慢慢比较而浮现出来就如同气泡上升浮出一样，故称之为冒泡排序。

算法原理
1、相邻元素两两比较，符合预期则进行数据交换；
2、每次排序后的数据都会倾向一边，则下次排序会减少循环次数；
3、比较的次数为数组长度 N-1 次,换言之就是长度为N的数组我们只需要交换N-1次即可获得最终结果。

时间复杂度
1、如果数据本身有序，则最理想的复杂度为 O(N)
2、如果数据本身全部乱序，我们需要双层循环全部数据，则最坏的复杂度为O(N2)
综合以上原因冒泡排序的时间复杂度为 O(N2)

算法稳定性
由于在算法过程中两两比较如果数据相等不会交换数据，故在比较过程中没有相同元素次序改变的情况则该算法稳定。

小试牛刀
1、创建算法类并提供升序、降序两种排序算法

/**
 * 冒泡排序算法
 * @author senfel
 * @version 1.0
 * @date 2022/11/16 10:59
 */
@Slf4j
public class BubbleSort {
    /**
     * 升序
     * @param array
     * @author senfel
     * @date 2022/11/16 11:01
     * @return void
     */
    public static void sort(int[] array){
        if(array == null || array.length <= 1){
            return;
        }
        log.error("升序==数组大小为：{}，预计排序次数为：{}",array.length,array.length-1);
        log.error("原始数组为：{}", Arrays.toString(array));
        //排序次数为N-1次
        for(int i =1;i<array.length;i++){
            //内部两两交互将最大的数据放在数组最后
            //由于最后的数据总是排好了的，我们只需要对未排序的进行排序 array.length-i
            for(int j = 0;j<array.length-i;j++){
                int temp = array[j+1];
                //由于是升序排序只要前一个元素大于后一个元素则进行数据交换
                if(array[j] > temp){
                    array[j+1] = array[j];
                    array[j] = temp;
                }
            }
            log.error("第{}次排序，当前数组为：{}",i,Arrays.toString(array));
        }
        log.error("数据最终元素位置为：{}", Arrays.toString(array));
    }
    /**
     * 倒序
     * @param array
     * @author senfel
     * @date 2022/11/16 11:14
     * @return void
     */
    public static void invertedSort(int[] array){
        if(array == null || array.length <= 1){
            return;
        }
        log.error("降序==数组大小为：{}，预计排序次数为：{}",array.length,array.length-1);
        log.error("原始数组为：{}", Arrays.toString(array));
        //排序次数为N-1次
        for(int i =1;i<array.length;i++){
            //倒序排序也是两两比较交换位置
            //由于最大的元素都排在数组前面，则我们只需要对后面的元素与排好序的末尾元素比较即可
            //为保证第0号元素被比较 j>=i
            for(int j = array.length-1;j>=i;j--){
                int temp =  array[j-1];
                if(temp < array[j]){
                    array[j-1] = array[j];
                    array[j] = temp;
                }
            }
            log.error("第{}次排序，当前数组为：{}",i,Arrays.toString(array));
        }
        log.error("数据最终元素位置为：{}", Arrays.toString(array));
    }
}

2、测试冒泡排序

public static void main(String[] args) {
    int[] array = {23,2,2,45,1,55,78,9,89};
    //升序
    sort(array);
    int[] array2 = {23,2,2,45,1,55,78,9,89};
    invertedSort(array2);
}

11:23:48.715 – 升序==数组大小为：9，预计排序次数为：8
11:23:48.718 – 原始数组为：[23, 2, 2, 45, 1, 55, 78, 9, 89]
11:23:48.718 – 第1次排序，当前数组为：[2, 2, 23, 1, 45, 55, 9, 78, 89]
11:23:48.718 – 第2次排序，当前数组为：[2, 2, 1, 23, 45, 9, 55, 78, 89]
11:23:48.718 – 第3次排序，当前数组为：[2, 1, 2, 23, 9, 45, 55, 78, 89]
11:23:48.718 – 第4次排序，当前数组为：[1, 2, 2, 9, 23, 45, 55, 78, 89]
11:23:48.719 – 第5次排序，当前数组为：[1, 2, 2, 9, 23, 45, 55, 78, 89]
11:23:48.719 – 第6次排序，当前数组为：[1, 2, 2, 9, 23, 45, 55, 78, 89]
11:23:48.719 – 第7次排序，当前数组为：[1, 2, 2, 9, 23, 45, 55, 78, 89]
11:23:48.719 – 第8次排序，当前数组为：[1, 2, 2, 9, 23, 45, 55, 78, 89]
11:23:48.719 – 数据最终元素位置为：[1, 2, 2, 9, 23, 45, 55, 78, 89]

11:23:48.719 – 降序==数组大小为：9，预计排序次数为：8
11:23:48.719 – 原始数组为：[23, 2, 2, 45, 1, 55, 78, 9, 89]
11:23:48.719 – 第1次排序，当前数组为：[89, 23, 2, 2, 45, 1, 55, 78, 9]
11:23:48.719 – 第2次排序，当前数组为：[89, 78, 23, 2, 2, 45, 1, 55, 9]
11:23:48.719 – 第3次排序，当前数组为：[89, 78, 55, 23, 2, 2, 45, 1, 9]
11:23:48.719 – 第4次排序，当前数组为：[89, 78, 55, 45, 23, 2, 2, 9, 1]
11:23:48.719 – 第5次排序，当前数组为：[89, 78, 55, 45, 23, 9, 2, 2, 1]
11:23:48.719 – 第6次排序，当前数组为：[89, 78, 55, 45, 23, 9, 2, 2, 1]
11:23:48.719 – 第7次排序，当前数组为：[89, 78, 55, 45, 23, 9, 2, 2, 1]
11:23:48.719 – 第8次排序，当前数组为：[89, 78, 55, 45, 23, 9, 2, 2, 1]
11:23:48.719 – 数据最终元素位置为：[89, 78, 55, 45, 23, 9, 2, 2, 1]