Java函数实现基本的排序算法：冒泡排序

1. 冒泡排序介绍

冒泡排序（Bubble Sort）是一种简单的排序算法，它的基本思想是：重复走访要排序的数列，一次比较两个元素，如果它们的顺序错误就交换它们的位置，直到没有元素需要交换，排序完成。冒泡排序是稳定的排序算法，时间复杂度为O(n2)，空间复杂度为O(1)，正如它的名字一样，就像气泡从水中升起。

2. 冒泡排序实现

我们用Java语言来实现冒泡排序算法，首先我们需要定义一个交换函数来交换数组中两个元素的位置：

public static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

接下来，我们就可以实现冒泡排序算法了：

public static void bubbleSort(int[] nums) {
    int len = nums.length;
    //外层循环控制排序轮数
    for (int i = 0; i < len - 1; i++) {
        //内层循环控制比较次数
        for (int j = 0; j < len - 1 - i; j++) {
            //比较相邻两个元素
            if (nums[j] > nums[j + 1]) {
                //如果前一个元素大于后一个元素，交换它们的位置
                swap(nums, j, j + 1);
            }
        }
    }
}

我们可以在main函数中调用bubbleSort函数进行测试：

public static void main(String[] args) {
    int[] nums = new int[]{3, 4, 2, 1, 5};
    bubbleSort(nums);
    System.out.println(Arrays.toString(nums));
}

运行结果为：

[1, 2, 3, 4, 5]

3. 冒泡排序优化

冒泡排序算法的时间复杂度为O(n2)，在数据量较大时效率较低，因此需要针对冒泡排序进行优化，可以减少比较次数和交换次数。

3.1 比较次数优化

传统的冒泡排序是每次比较相邻两个元素，如果前一个元素大于后一个元素，就交换它们的位置。但如果待排序序列中后面一部分已经排好序了，这时再进行比较和交换就是没有必要的，因为不会改变前面已经排好序的元素位置。因此，我们可以加入一个标志位判断当前轮次是否进行了交换，如果没有进行交换，说明已经排好序了，可以提前结束循环。

优化之后的代码如下：

public static void bubbleSort(int[] nums) {
    int len = nums.length;
    //外层循环控制排序轮数
    for (int i = 0; i < len - 1; i++) {
        boolean flag = false;
        //内层循环控制比较次数
        for (int j = 0; j < len - 1 - i; j++) {
            //比较相邻两个元素
            if (nums[j] > nums[j + 1]) {
                //如果前一个元素大于后一个元素，交换它们的位置
                swap(nums, j, j + 1);
                flag = true;
            }
        }
        if (!flag) {
            //如果当前轮次没有进行交换，说明已经排好序了，提前结束循环
            break;
        }
    }
}

3.2 交换次数优化

传统的冒泡排序每次进行交换时，只要两个元素顺序相反就进行交换，但每一轮排序会把最大（小）的元素交换到队尾，交换的位置可能很远，这样就增加了排序的时间复杂度。我们可以将交换操作改成记录最后一次交换的位置，后面没有交换就说明已经有序了，这样只需要一次排序就可以确定有序区域的长度，后面的排序就不必再次比较（和“冒泡”的思想相似）。

优化之后的代码如下：

public static void bubbleSort(int[] nums) {
    int len = nums.length;
    //外层循环控制排序轮数和有序区的长度
    int lastExchangeIndex = 0;
    for (int i = 0; i < len - 1; i++) {
        boolean flag = false;
        //内层循环控制比较次数
        for (int j = 0; j < len - 1 - i; j++) {
            //比较相邻两个元素
            if (nums[j] > nums[j + 1]) {
                //记录最后一次交换位置
                lastExchangeIndex = j;
                //如果前一个元素大于后一个元素，交换它们的位置
                swap(nums, j, j + 1);
                flag = true;
            }
        }
        if (!flag) {
            //如果当前轮次没有进行交换，说明已经排好序了，提前结束循环
            break;
        }
        len = lastExchangeIndex + 1;
    }
}

4. 总结

本文通过Java函数的实现介绍了基本的排序算法——冒泡排序，通过对比较次数和交换次数的优化，提高了冒泡排序算法的效率。冒泡排序虽然简单，但是可以帮助我们深入理解排序算法的基本原理，是学习算法的重要步骤。