数据结构排序算法之冒泡排序详解（java实现）

骑猪看日落 2022-06-01 23:54 163阅读 0赞

### 前言： ###

说起冒泡排序应该没有几个人不知道吧，今天来总结一下冒泡排序的知识。

### 知识点一：排序思想 ###

冒泡排序：比较两个元素，如果不有序，则交换位置。每循环一次都会有某个元素放到恰到的位置。
    
    另一种说法： 
           两两比较数据列表中的相邻的两项，满足条件，交换位置。每一轮循环中都会有一个元素放到指定的位置上，直到有序为止；

### 知识点二：冒泡排序算法分类 ###

1,基础冒泡排序
    2，改进冒泡排序
    3，进一步改进的冒泡排序
    
    说明：
       这里分类没有严格的意义，只是用来说明对冒泡排序改进的的一种说明。
       建议大家写冒泡排序使用3，相对来说效率高一下。

### 知识点三：时间复杂度，辅助空间、稳定性 ###

时间复杂度：O(n^2)
    辅助空间：O(1)
    稳定性：稳定

### 知识点四：java实现 ###

#### 1.基础冒泡排序实现 ####

/** * 基础冒泡排序 （升序） */
        private void bubbleSort(int[] ints) {
            Objects.requireNonNull(ints);
            for (int i = 0; i < ints.length; i++) {
                //这里j要小于ints.length - 1，如果j < ints.length会报ArrayIndexOutOfBoundsException
                for (int j = 0; j < ints.length - 1; j++) {
                    if (ints[j] > ints[j + 1]) {
                        int temp = ints[j];
                        ints[j] = ints[j + 1];
                        ints[j + 1] = temp;
                    }
                }
            }
        }

测试类：

@Test
        public void test() {
            int[] ints = {
       12, 5, 78, 99, 31, 8};
            bubbleSort(ints);
    
            Arrays.stream(ints).forEach(System.out::println);
        }

测试结果：

5
    8
    12
    31
    78
    99

#### 2.改进的冒泡排序 ####

##### 改进说明： #####

定义一个标识变量来标志一次循环中有没有交换位置，如果在一次循环中没有交换位置，此时说明数据集合中已经有序，直接跳出循环即可。 
    这样可以避免内部循环多次判断，提高效率。

/** * 改进冒泡排序 （升序） */
        private void bubbleSort1(int[] ints) {
            Objects.requireNonNull(ints);
            for (int i = 0; i < ints.length; i++) {
                //标志是否交换
                boolean flag = false;
                //这里j要小于ints.length - 1，如果j < ints.length会报ArrayIndexOutOfBoundsException
                for (int j = 0; j < ints.length - 1; j++) {
                    if (ints[j] > ints[j + 1]) {
                        int temp = ints[j];
                        ints[j] = ints[j + 1];
                        ints[j + 1] = temp;
                        flag = true;
                    }
                }
                //没有交换,说明现在已经是有序的，直接跳出循环
                if (!flag) {
                    break;
                }
            }
        }

测试代码：

@Test
        public void test() {
            int[] ints = {
       12, 5, 78, 99, 31, 8};
            //bubbleSort(ints);
            bubbleSort1(ints);
            //bubbleSort2(ints);
            Arrays.stream(ints).forEach(System.out::println);
        }

测试结果：

5
    8
    12
    31
    78
    99

#### 3.进一步改进的冒泡排序 （建议使用这个） ####

##### 改进思想： #####

可以使用一个变量记录每次交换的最后位置，因为交换最后位置后面的元素都已经是有序的了，不需要在进行排序。默认交换的位置为数据集合的最后一个位置。
    这样可以提高内部循环的效率，从而提高冒泡排序的整体效率。

/** * 进一步改进的冒泡排序 （升序） * */
        private void bubbleSort2(int[] ints) {
            Objects.requireNonNull(ints);
            int lastSwap = ints.length - 1;
            for (int i = 0; i < ints.length; i++) {
                boolean flag = false;
                int m  = lastSwap;
                for (int j = 0; j < m; j++) {
                    if (ints[j] > ints[j + 1]) {
                        int temp = ints[j];
                        ints[j] = ints[j + 1];
                        ints[j + 1] = temp;
                        flag = true;
                        lastSwap = j;
                    }
                }
                if (!flag) {
                    break;
                }
            }
        }

测试代码：

@Test
        public void test() {
            int[] ints = {
       12, 5, 78, 99, 31, 8};
            //bubbleSort(ints);
            //bubbleSort1(ints);
            bubbleSort2(ints);
            Arrays.stream(ints).forEach(System.out::println);
        }

测试结果：

5
    8
    12
    31
    78
    99

### 总结： ###

平时我们使用冒泡排序尽量使用我们改进过的，这样可以提高效率。