Java数组全套深入探究——进阶知识阶段2、冒泡排序

Java数组全套深入探究——进阶知识阶段2、冒泡排序

数组学习的重要意义

数组是我们必须要掌握的数据结构之一，在以后会对我们有非常大的帮助。

• 提高程序效率：数组是一种高效的数据结构，可以快速地访问和修改数据。在实际的生产生活中，数组被广泛应用于各种需要高效数据处理的场景，如图像处理、科学计算、金融分析等。通过学习数组，学生们可以更加高效地处理数据，提高程序的执行效率。
• 增强编程能力：数组是编程中常用的数据结构之一，掌握数组的使用方法对于学生的编程能力提升非常重要。在实际编程过程中，数组的使用非常普遍，掌握数组的使用可以帮助学生更加熟练地进行编程，提高编程效率和代码质量。
• 培养逻辑思维：数组是一种抽象的数据结构，通过学习数组，学生们可以培养自己的逻辑思维能力。在实际的问题解决中，很多问题都可以转化为数组的处理问题，通过学习数组，学生们可以更加清晰地思考问题，并给出有效的解决方案。

对于学生们来说，学习数组可能是一项有些困难的任务，但只要坚持学习，就一定能够掌握它。以下是一些鼓励学生们学习数组的话：

• 数组是编程的基础，掌握数组的使用对于成为一名优秀的程序员非常重要。
• 学习数组可能有些困难，但只要坚持下去，就一定能够掌握它。
• 通过学习数组，你可以更加高效地处理数据，提高程序的执行效率，展现出你的编程能力。
• 数组的应用非常广泛，掌握数组的使用可以让你在未来的学习和工作中更加出色。
• 相信自己，你一定能够掌握数组的使用，成为一名优秀的程序员！

冒泡排序的具体排序过程

冒泡排序（Bubble Sort）是一种简单的排序算法。它的基本思想是通过不断交换相邻的未排序元素，使得每一轮排序过程中最大（或最小）的元素"冒泡"到数组的一端。具体的排序过程如下：

1. 从数组的第一个元素开始，比较相邻的两个元素。
2. 如果第一个元素比第二个元素大（或根据排序顺序需要交换），则交换它们的位置。
3. 继续比较下一对相邻元素，执行相同的操作，直到数组的末尾。
4. 经过第一轮比较和交换，最大的元素会被移动到数组的末尾（或根据排序顺序的最后一个位置）。
5. 重复上述步骤，但每次排除已经排序好的最后一个元素，直到整个数组排序完成。

public class Demo1 {
    public static void main(String[] args) {
        // 定义待排序的数组
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        // 打印排序前的数组
        System.out.println("排序前的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
        // 执行选择排序算法
        int n = arr.length;
        // 遍历数组，进行n-1轮比较和交换
        for (int i = 0; i < n - 1; i++) {
            // 找到当前未排序部分中的最小元素索引
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 将找到的最小元素与未排序部分的第一个元素交换位置
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        // 打印排序后的数组
        System.out.println("排序后的数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

示例：

考虑以下待排序的数组 [64, 34, 25, 12, 22, 11, 90]

第1轮：

比较64和34，交换位置：[34, 64, 25, 12, 22, 11, 90]

比较64和25，交换位置：[34, 25, 64, 12, 22, 11, 90]

比较64和12，交换位置：[34, 25, 12, 64, 22, 11, 90]

比较64和22，交换位置：[34, 25, 12, 22, 64, 11, 90]

比较64和11，交换位置：[34, 25, 12, 22, 11, 64, 90]

比较64和90，不交换位置：[34, 25, 12, 22, 11, 64, 90]

第2轮：

排除已排序好的最后一个元素90，继续比较前面的元素。

比较34和25，交换位置：[25, 34, 12, 22, 11, 64, 90]

...（以此类推）

重复上述步骤，直到整个数组排序完成。最终排序后的数组为 [11, 12, 22, 25, 34, 64, 90]。

通过多轮的比较和交换操作，冒泡排序将最大的元素逐渐"冒泡"到数组的一端，从而实现整个数组的排序。

选择排序与冒泡排序对比

选择排序和冒泡排序都是简单的排序算法，它们在实现上有一些差异，并且在某些方面有不同的性能特点。以下是它们之间的对比：

时间复杂度、空间复杂度、算法的稳定性说明以及示例-CSDN博客

实现方式：

选择排序：通过每轮找到未排序部分中的最小（或最大）元素，并与未排序部分的第一个元素进行交换，直到整个数组排序完成。

冒泡排序：通过相邻元素的比较和交换，使得每一轮排序过程中最大（或最小）的元素"冒泡"到数组的一端，直到整个数组排序完成。

时间复杂度：

选择排序的时间复杂度为O(n^2)，其中n是数组的大小。因为无论数组是否已经有序，都需要进行n-1轮比较和交换操作。

冒泡排序的时间复杂度也为O(n^2)。但是在最好的情况下，即数组已经有序时，冒泡排序可以在早期终止，时间复杂度可以达到O(n)。然而，在最坏和平均情况下，冒泡排序的比较和交换次数较多。

空间复杂度：

选择排序和冒泡排序的空间复杂度都是O(1)，因为它们都只需要常数级别的额外空间来存储临时变量。

稳定性：

选择排序是不稳定的排序算法，因为交换操作可能会改变相等元素的相对顺序。

冒泡排序是稳定的排序算法，因为相等元素之间的相对顺序在排序过程中不会改变。

对比数据（以数组[64, 34, 25, 12, 22, 11, 90]为例）：

选择排序的比较次数：每轮需要比较的次数逐渐减少，总共需要(n-1) + (n-2) + ... + 1 = n*(n-1)/2次比较。在这个例子中，总共需要21次比较。

冒泡排序的比较次数：在最坏情况下，需要比较的次数和选择排序相同，即n*(n-1)/2次比较。但是，如果数组已经有序，则只需要进行n-1次比较。在这个例子中，第一轮需要6次比较，第二轮需要5次比较，以此类推，总共需要21次比较。

选择排序的交换次数：每轮最多交换一次，总共最多需要n-1次交换。在这个例子中，总共需要进行6次交换。

冒泡排序的交换次数：在最坏情况下，需要交换的次数和选择排序相同，即n-1次交换。但是，如果数组已经有序，则不需要进行任何交换。在这个例子中，第一轮需要进行5次交换，第二轮需要进行3次交换，以此类推，总共需要进行15次交换。

综上所述，选择排序和冒泡排序在时间复杂度上都是O(n^2)，但是在实现方式、稳定性以及具体比较和交换次数上有所不同。选择排序通过每轮找到最小（或最大）元素进行交换，实现简单但不稳定；而冒泡排序通过相邻元素的比较和交换，"冒泡"出最大（或最小）元素，实现稍复杂但稳定。在实际应用中，选择适合的排序算法取决于具体的需求和数据集特点。