常用的排序算法之冒泡排序（Bubble Sort）

冒泡排序（Bubble Sort）

原理

冒泡排序（Bubble Sort）是一种简单的排序算法，其名字来源于越小的元素会经由交换慢慢“浮”到数列的顶端（或越大的元素“沉”到底端），就如同气泡从水底冒到水面一样。虽然这个算法不是最高效的，但由于其实现简单直观，常常用于教学目的。

定义

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

扩展应用

冒泡排序的思想不仅仅局限于数组的排序，也可以应用于其他可比较元素的序列，如链表等。其思想是通过不断比较相邻元素并交换位置，使得较大的元素逐渐“沉”向序列的一端，而较小的元素逐渐“浮”向另一端。

优缺点

优点：

• 代码实现简单直观。
• 在数据已经基本有序的情况下，冒泡排序的时间复杂度接近O(n)。

缺点：

• 时间复杂度较高，平均时间复杂度为O(n^2)。
• 空间复杂度为O(1)，属于原地排序算法，但需要多次交换操作。
• 在数据量大且无序的情况下效率较低。

使用场景

冒泡排序通常用于数据量较小且对时间效率要求不高的场景。

使用数据一步步举例

假设有一个数组[64, 34, 25, 12, 22, 11, 90]，我们使用冒泡排序来对其进行升序排序：

1. 第一轮比较与交换：
   • [25, 34, 12, 22, 11, 64, 90]（64与34交换）
   • [25, 12, 34, 22, 11, 64, 90]（34与12交换）
   • [25, 12, 22, 34, 11, 64, 90]（34与22交换）
   • [25, 12, 22, 11, 34, 64, 90]（22与11交换）
   • [25, 12, 22, 11, 34, 64, 90]（无需再交换）
2. 第二轮比较与交换（已排序的最后一个元素不再参与比较）：
   • [12, 22, 25, 11, 34, 64, 90]（25与12交换）
   • [12, 11, 25, 22, 34, 64, 90]（22与11交换）
   • [11, 12, 25, 22, 34, 64, 90]（无需再交换）

... 以此类推，直到整个数组有序。

Java示例代码

public class BubbleSort {  
    public static void main(String[] args) {  
        int[] array = {64, 34, 25, 12, 22, 11, 90};  
        bubbleSort(array);  
        System.out.println(Arrays.toString(array));  
    }  
  
    public static void bubbleSort(int[] array) {  
        int n = array.length;  
        for (int i = 0; i < n - 1; i++) {  
            for (int j = 0; j < n - i - 1; j++) {  
                if (array[j] > array[j + 1]) {  
                    // 交换 array[j] 和 array[j+1]  
                    int temp = array[j];  
                    array[j] = array[j + 1];  
                    array[j + 1] = temp;  
                }  
            }  
        }  
    }  
}

运行上述代码，将输出排序后的数组[11, 12, 22, 25, 34, 64, 90]。