Java冒泡排序

一、Java冒泡排序概述

冒泡排序是一种基本的排序算法，它属于交换排序类，通过相邻元素之间的比较和交换来把小的数交换到前面，大的数交换到后面，从而实现排序。

Java语言中实现冒泡排序算法是比较简单的，只需要使用双重循环来实现比较和交换操作即可。

二、Java冒泡排序实现

public static void bubbleSort(int[] arr) {
    int len = arr.length;
    // 外层循环控制排序趟数
    for (int i = 0; i < len - 1; i++) {
        // 内层循环控制比较和交换过程
        for (int j = 0; j  arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

三、Java冒泡排序优化

虽然冒泡排序算法简单易懂，但它的时间复杂度为O(n^2)，效率比较低。因此，在实际应用中，对其进行优化是非常重要的。

1、优化一：已经排序好的数据不再循环

public static void bubbleSort(int[] arr) {
    int len = arr.length;
    // 外层循环控制排序趟数
    for (int i = 0; i < len - 1; i++) {
        boolean flag = true; // 标志位，表示本次循环是否进行了交换操作
        // 内层循环控制比较和交换过程
        for (int j = 0; j  arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = false;
            }
        }
        if (flag) { // 如果一趟比较下来没有发生交换操作，说明数据已经是有序的，退出循环
            break;
        }
    }
}

2、优化二：每趟循环确定了最大值和最小值

冒泡排序每趟循环都要确定一个最大值和一个最小值，而选择排序每趟循环只需要交换一个位置，因此，选择排序效率比冒泡排序要高。所以，我们可以使用类似选择排序的方法来优化冒泡排序。

public static void bubbleSort(int[] arr) {
    int len = arr.length;
    int left = 0;
    int right = len - 1;
    while (left < right) {
        boolean flag = true; // 标志位，表示本次循环是否进行了交换操作
        for (int i = left; i  arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                flag = false;
            }
        }
        right--;
        if (flag) { // 如果一趟比较下来没有发生交换操作，说明数据已经是有序的，退出循环
            break;
        }
        flag = true;
        for (int i = right; i > left; i--) {
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
                flag = false;
            }
        }
        left++;
        if (flag) { // 如果一趟比较下来没有发生交换操作，说明数据已经是有序的，退出循环
            break;
        }
    }
}

四、其他语言的冒泡排序实现

1、JavaScript冒泡排序实现

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j  arr[j + 1]) {
                var temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

2、C语言冒泡排序实现

void bubbleSort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++) {
        for (j = 0; j  arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

3、Python冒泡排序实现

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr