Java数组全套深入探究——进阶知识阶段2、冒泡排序
目录
数组学习的重要意义
冒泡排序的具体排序过程
选择排序与冒泡排序对比
实现方式：
时间复杂度：
空间复杂度：
稳定性：
对比数据（以数组64, 34, 25, 12, 22, 11, 90为例）：
总篇链接：https://laoshifu.blog.csdn.net/article/details/134906408
数组学习的重要意义
数组是我们必须要掌握的数据结构之一，在以后会对我们有非常大的帮助。
- 提高程序效率：数组是一种高效的数据结构，可以快速地访问和修改数据。在实际的生产生活中，数组被广泛应用于各种需要高效数据处理的场景，如图像处理、科学计算、金融分析等。通过学习数组，学生们可以更加高效地处理数据，提高程序的执行效率。
- 增强编程能力：数组是编程中常用的数据结构之一，掌握数组的使用方法对于学生的编程能力提升非常重要。在实际编程过程中，数组的使用非常普遍，掌握数组的使用可以帮助学生更加熟练地进行编程，提高编程效率和代码质量。
- 培养逻辑思维：数组是一种抽象的数据结构，通过学习数组，学生们可以培养自己的逻辑思维能力。在实际的问题解决中，很多问题都可以转化为数组的处理问题，通过学习数组，学生们可以更加清晰地思考问题，并给出有效的解决方案。
对于学生们来说，学习数组可能是一项有些困难的任务，但只要坚持学习，就一定能够掌握它。以下是一些鼓励学生们学习数组的话：
- 数组是编程的基础，掌握数组的使用对于成为一名优秀的程序员非常重要。
- 学习数组可能有些困难，但只要坚持下去，就一定能够掌握它。
- 通过学习数组，你可以更加高效地处理数据，提高程序的执行效率，展现出你的编程能力。
- 数组的应用非常广泛，掌握数组的使用可以让你在未来的学习和工作中更加出色。
- 相信自己，你一定能够掌握数组的使用，成为一名优秀的程序员！
冒泡排序的具体排序过程
冒泡排序（Bubble Sort）是一种简单的排序算法。它的基本思想是通过不断交换相邻的未排序元素，使得每一轮排序过程中最大（或最小）的元素"冒泡"到数组的一端。具体的排序过程如下：
- 从数组的第一个元素开始，比较相邻的两个元素。
- 如果第一个元素比第二个元素大（或根据排序顺序需要交换），则交换它们的位置。
- 继续比较下一对相邻元素，执行相同的操作，直到数组的末尾。
- 经过第一轮比较和交换，最大的元素会被移动到数组的末尾（或根据排序顺序的最后一个位置）。
- 重复上述步骤，但每次排除已经排序好的最后一个元素，直到整个数组排序完成。
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)，但是在实现方式、稳定性以及具体比较和交换次数上有所不同。选择排序通过每轮找到最小（或最大）元素进行交换，实现简单但不稳定；而冒泡排序通过相邻元素的比较和交换，"冒泡"出最大（或最小）元素，实现稍复杂但稳定。在实际应用中，选择适合的排序算法取决于具体的需求和数据集特点。
