【排序算法】之冒泡排序

一、算法介绍

冒泡排序（Bubble Sort）是一种基础的排序算法，它的主要思想是通过重复遍历待排序的列表，比较每对相邻的元素并根据需要交换它们，使得每一遍遍历都能将未排序的最大（或最小）元素“冒泡”到正确的位置。以下是冒泡排序的详细步骤和特点：
1. 基本步骤：

对于给定的未排序数组，从第一个元素开始，比较相邻的元素。
如果前一个元素大于后一个元素，则交换它们的位置。
对每一对相邻元素做同样的比较，从开始第一对到结尾的最后一对。这步做完后，最后的元素将会是最大的数。
重复步骤1和2，但不包括最后一对，因为上一轮中它们已经排好序了。
重复以上步骤，直到没有需要交换的元素，即数组完全排序。

2. 算法流程：

一次完整的遍历称为一轮。
每轮遍历中，最大的元素会“冒”到数组的末尾。
继续进行下一轮遍历，直到所有元素都在正确的位置上。

3. 示例：

对于数组 [5, 3, 8, 1, 2]，第一轮遍历后，最大的数字8会移动到最后，数组变为 [5, 3, 1, 2, 8]。
接下来的每一轮都会将剩余元素中的最大值移动到已排序部分的末尾，直到数组完全排序为 [1, 2, 3, 5, 8]。

4. 时间复杂度：

平均和最坏情况下的时间复杂度都是 O( $n^{2}$ )，其中 n 是数组的长度。这是因为每个元素都要与其他所有元素比较一次。
在最好情况下，如果数组已经排序，只需要进行 n-1 次比较即可完成排序，时间复杂度为 O(n)。

5. 空间复杂度：

冒泡排序是原地排序算法，它不需要额外的存储空间，因此空间复杂度为 O(1)。

6. 稳定性：

冒泡排序是稳定的排序算法，即相等的元素在排序后保持原有的相对顺序。

由于其效率较低，冒泡排序在实际应用中并不常见，但在我们自己学习和理解排序算法原理时很有用。在处理大量数据时，其他更高效的方法如快速排序、归并排序和堆排序更受欢迎。我们先通过简单的java代码来实现这种算法。

二、代码示例

以下代码是冒泡排序从小到大排序的示例

package com.datastructures;

import java.util.Arrays;

/**
 * 冒泡排序算法实现
 * @author hulei
 * @date 2024/5/7 11:41
 */


public class BubbleSort {
    public static void main(String[] args) {
        Integer[] array = {7,3,5,4,8,1,11,15,2};
        System.out.println("冒泡排序前数组："+Arrays.toString(array));
        bubbleSort(array);
        System.out.println("冒泡排序后数组："+Arrays.toString(array));
    }


    /**
     * 实现冒泡排序算法，对一个可比较元素数组进行排序。
     *
     * @param array 一个类型为E的数组，其中E必须实现Comparable接口，以便于元素之间的比较。
     *              该数组是待排序的数组。
     * @see java.lang.Comparable
     */
    public static <E extends Comparable<? super E>> void bubbleSort(E[] array){
        int length = array.length;
        // 外层循环控制排序的轮数，每轮确保最重（或最轻）的元素位置正确
        for (int i = 0; i < length -1; i++) {
            // 内层循环控制每轮排序中元素的比较，每次比较相邻的两个元素
            for (int j = 0; j < length -1-i; j++) {
                // 如果当前元素大于下一个元素，则交换它们的位置，使得较大的元素逐渐向数组尾部移动
                if(array[j].compareTo(array[j+1])>0){
                    swap(array,j+1,j);
                }
            }
            
        }

    }

    /**
     * 交换数组中两个元素的位置。
     * @param array 要进行交换的数组。
     * @param index1 要交换的第一个元素的索引。
     * @param index2 要交换的第二个元素的索引。
     * @param <E> 数组元素的类型。
     */
    private static <E> void swap(E[] array, int index1, int index2) {
        // 临时变量用于存储第一个元素，以便后续交换
        E temp = array[index1];
        array[index1] = array[index2]; // 将第二个元素的值赋给第一个元素
        array[index2] = temp; // 将之前存储的第一个元素的值赋给第二个元素
    }
}

在这里插入图片描述
代码逻辑比较简单，使用了两层for循环，外层控制循环的论数，n个元素就需要循环排序n轮。
第一轮外循环：
内层循环是相邻元素比较：

第一层内循环从第一个元素A开始比较，相邻比较，如果大于第二个元素，就把第一个元素和第二个元素交换位置。
第二层内循环再把这个A元素(这个元素索引位置已经移动到了第二的位置)和第三个元素比较，如果大于第三个，就把第二个元素A和第三个元素交换位置，交换后元素A移动到了第三的位置。
第三层内循环再把这个元素A(这个元素索引位置已经移动到了第三的位置)和第四个元素比较，如果A小于第四个元素B，则A和B不交换，元素A遇到第一个比自己大的元素B
第四层内循环把元素B和第五个元素C比较，如果B小于C，则B遇到第一个比自己大的元素C，B和C不交换。
第五层内循环把元素C和第六个元素D比较，如果C大于D，则把第五个元素C和第六个元素D交换。
第六层内循环从元素C（元素C在第六的位置）开始和第七个元素E比较
。
。
。
以此类推直到第一轮内存循环全部结束，最大的元素K被排在最后一位

接着开始第二轮外层循环，内部还是从第一个元素开始与相邻元素比较，比较过并交换的过程同上类似，但是内层循环最终的边界是右边倒数第二个元素，此轮结束后会把第二大的元素M排在右边倒数第二位，即K的前一位
。
。
。
。
一直到外层循环都结束，通过n轮循环把n个元素按照从小到大的顺序排好了。

三、代码优化

注意以上代码代码其实不是最优代码，因为无论数组是否排序，内存和外层都要进行全部的循环才能完成排序，时间复杂度总是为O( $n^{2}$ )，但有一种情况，比如数组已经从小到大排序好了，再进行那么多次循环岂不是浪费？
如果数组已经从小到大排序好了，在第一轮外层循环时就已经能判断出来，判断时会发现下一个元素总是大于前一个，即没有发生过元素交换。
这里提供一个交换标识来判断跳出循环，保证在已排序的情况下不做无谓的循环，优化后代码如下：
在bubbleSort方法里加了一个交换标识swapped，第一轮内部循环结束后，swapped为false则说明已排序好，跳出外层循环，其实只进行了第一轮内部循环的n-1次遍历，时间复杂度为O(n-1)

    public static <E extends Comparable<? super E>> void bubbleSort(E[] array){
        int length = array.length;
        boolean swapped; // 标记在某一轮内是否进行了交换
        // 外层循环控制排序的轮数，每轮确保最重（或最轻）的元素位置正确
        for (int i = 0; i < length -1; i++) {
            swapped = false;
            // 内层循环控制每轮排序中元素的比较，每次比较相邻的两个元素
            for (int j = 0; j < length -1-i; j++) {
                // 如果当前元素大于下一个元素，则交换它们的位置，使得较大的元素逐渐向数组尾部移动
                if(array[j].compareTo(array[j+1])>0){
                    swap(array,j+1,j);
                    swapped = true; // 标记已进行交换
                }
            }
            // 如果一轮比较下来没有进行过交换，说明数组已经有序，可以提前结束
            if (!swapped) break;

        }
    }