排序算法之冒泡排序代码模板（C/C++/Java/Python多版本）

冒泡算法是一种基础的排序算法，其核心思想是反复交换相邻元素，如同水中的气泡逐渐上浮。它通过多轮遍历，在每一轮中依次比较相邻的两个元素，如果它们的顺序错误（例如前一个比后一个大），就交换它们的位置，这样每一轮遍历都会将当前未排序部分中的最大（或最小）元素“浮”到正确的一端（末端）。这个过程不断重复，直到某一轮遍历中没有发生任何交换，表明序列已经完全有序，其时间复杂度为 O(n²)，效率较低。

1. C/C++版代码：

void bubbleSort(int arr[], int n) {
    int i, j, temp;
    int swapped; // 优化标志
    
    for (i = 0; i < n - 1; i++) {      // 外层循环：n-1轮
        swapped = 0;
        
        // 内层循环：相邻元素比较交换
        for (j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {  // 逆序则交换
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        
        if (!swapped) break;           // 提前终止：本轮无交换说明已有序
    }
}

2. Java版代码：

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped; // 优化标志：记录本轮是否发生交换
        
        // 外层循环：最多需要n-1轮排序
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            // 内层循环：比较相邻元素，将较大元素"冒泡"到右侧
            // 每轮结束后，右侧i个元素已处于最终位置
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {  // 如果逆序，则交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;        // 标记发生交换
                }
            }
            
            // 提前终止优化：若本轮无交换，说明数组已完全有序
            if (!swapped) {
                break;
            }
        }
    }
}

3. Python版代码：

def bubble_sort(arr):
    # 冒泡排序：通过相邻元素比较交换，将最大元素逐步"冒泡"到右侧
    
    n = len(arr)
    
    # 外层循环：最多需要n-1轮排序
    for i in range(n - 1):
        swapped = False  # 优化标志：记录本轮是否发生交换
        
        # 内层循环：比较相邻元素，将较大元素向右移动
        # 每轮结束后，右侧i个元素已处于最终有序位置
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:   # 发现逆序对，交换位置
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True        # 标记本轮发生交换
        
        # 提前终止优化：若本轮无交换，说明数组已完全有序
        if not swapped:
            break