冒泡排序和选择排序的区别

在这里，我们将探讨选择排序和冒泡排序之间的区别。在理解这些区别之前，我们应该先分别了解选择排序和冒泡排序。

什么是冒泡排序？

冒泡排序也是用于对数组元素进行排序的技术之一。冒泡排序的基本原理是比较两个相邻元素；如果这些元素顺序正确，则继续下一次迭代。否则，交换这两个元素。我们通过一个例子来理解冒泡排序。

考虑以下数组

上面的数组是一个未排序的数组。该数组包含 5 个整数，即 15, 16, 6, 8, 5。

以下是排序数组所需的步骤

第一趟

步骤 1： a[0] 元素与 a[1] 元素进行比较。a[0] 小于 a[1]，即 15<16，因此不会进行交换，如下图所示。

步骤 2： 现在，a[1] 将与 a[2] 元素进行比较。由于 a[1] 大于 a[0] 元素，即 16>6，因此交换 16 和 6，如下图所示。

步骤 3： a[2] 将与 a[3] 元素进行比较。由于 a[2] 大于 a[3] 元素，即 16>8，因此交换 16 和 8 元素，如下图所示。

步骤 4： a[3] 将与 a[4] 元素进行比较。由于 a[3] 大于 a[4]，即 16 > 5，因此交换 16 和 5 元素，如下图所示。

正如我们在上面的数组中观察到的，最大的元素已经“冒泡”到其正确位置。换句话说，我们可以说最大的元素已经放置在数组的最后一个位置。以上步骤包含在第一趟中，其中最大的元素处于其正确位置。

我们将在第二趟中再次从第一个位置开始比较元素。

第二趟

步骤 1： 首先，我们比较 a[0] 与 a[1] 元素。由于 a[0] 元素大于 a[1] 元素，即 15 > 6，交换 a[0] 元素与 a[1]，如下图所示。

步骤 2： a[1] 元素将与 a[2] 元素进行比较。a[1] 大于 a[2]，即 15 > 8，因此交换 a[1] 与元素 a[2]，如下图所示。

步骤 3： a[2] 元素将与 a[3] 元素进行比较。由于 a[2] 大于 a[3] 元素，即 15 > 5，交换元素 15 与元素 5，如下图所示。

步骤 4： 现在，a[3] 与 a[4] 进行比较。由于 a[3] 小于 a[4]，因此不会进行交换，如下图所示。

正如我们上面观察到的，两个元素（最大元素 16 和第二大元素 15）已处于正确位置。数组中仍有三个元素未排序，因此我们将在第三趟中再次执行相同的步骤。

第三趟

步骤 1： 首先，我们比较 a[0] 与 a[1]。由于 a[0] 小于 a[1]，即 6 < 8，因此不会进行交换，如下图所示。

步骤 2： 现在，a[1] 将与 a[2] 进行比较。由于 a[1] 大于 a[2]，因此交换元素 8 与元素 5，如下图所示。

步骤 3： a[2] 将与 a[3] 进行比较。由于 a[2] 小于 a[3]，即 8 < 15，因此不会进行交换，如下图所示。

步骤 4： a[3] 元素将与 a[4] 进行比较。由于 a[3] 小于 a[4]，即 15 < 16，因此不会进行交换，如下图所示。

在第三趟中，有三个元素处于正确位置：最大元素、第二大元素和第三大元素。数组中仍有两个元素未排序，因此我们将在第四趟中再次执行相同的步骤。

第四趟

步骤 1： 首先，我们将比较 a[0] 和 a[1]。由于 a[0] 大于 a[1]，交换 a[0] 与 a[1]。

上述数组是一个已排序的数组，所有元素都处于正确位置。

什么是选择排序？

排序意味着将数组元素按升序排列。选择排序是一种用于数组排序的排序技术。在选择排序中，一个数组被分成两个子数组，即一个未排序子数组和另一个已排序子数组。最初，我们假设已排序子数组是空的。首先，我们从未排序子数组中找到最小元素，并将其与数组开头位置的元素交换。这种算法被称为选择排序，因为它选择最小元素然后执行交换。

让我们通过一个例子来理解选择排序。

正如我们上面数组中观察到的，它包含 6 个元素。上面的数组是一个未排序的数组，其索引从 0 开始到 5 结束。以下是用于排序数组的步骤

步骤 1： 在上面的数组中，最小元素是 1；将元素 1 与元素 7 交换。

现在，排序数组只包含一个元素，即 1，而未排序数组包含 5

个元素，即 4, 10, 8, 3, 7。

步骤 2： 在未排序子数组中，最小元素是 3，因此将元素 3 与未排序子数组开头的元素 4 交换。

现在，排序数组包含两个元素，即 1 和 3，而未排序数组有四个元素，即 10, 8, 4, 7，如上图所示。

步骤 3： 在未排序子数组中搜索最小元素，最小元素是 4。将元素 4 与未排序子数组开头的元素 10 交换。

现在，排序数组包含三个元素，即 1, 3, 4，而未排序数组有三个元素，即 10, 8, 7。

步骤 4： 在未排序数组中搜索最小元素，最小元素是 7。将元素 7 与未排序子数组开头的元素 10 交换。

现在，排序数组包含四个元素，即 1, 3, 4, 7，而未排序数组有两个元素，即 10, 8。

步骤 5： 在未排序数组中搜索最小元素，最小元素是 8。将元素 8 与未排序子数组开头的元素 10 交换。

现在，排序数组包含的元素是 1, 3, 4, 7, 8。

步骤 6： 未排序子数组中剩下最后一个元素。将最后一个元素移动到已排序子数组中，如下图所示。

冒泡排序和选择排序的区别