Java 中的选择排序

选择排序是一种易于理解和直观的算法，它可以将列表或数组中的元素按升序或降序排序。选择排序的核心思想是重复地从未排序部分获取最小（或最大）元素，并将其与未排序部分的第一个元素进行交换。这个排序过程将一直持续到整个列表排序完成。

以下是选择排序算法的简要概述：

选择： 算法遍历未处理的数组，寻找最小（或最大）元素。

交换： 找到最小（或最大）元素后，将其与剩余未排序部分的第一个元素进行交换。此操作随后将元素放置到其正确的排序位置。

收缩： 每一轮迭代后，已排序的部分都会增加，而未排序的部分则缩小。排序过程将持续到整个集合都排序完成。

选择排序并不是最高效的排序方法；然而，即使对于大型数据集，其时间复杂度在所有情况下都是 O(n^2)。尽管如此，由于其简单性和易于实现的特性，它通常用于教学目的。此外，这种原地排序方法使其成为内存使用是关键考虑因素的理想选择。

选择排序如何工作？

选择排序算法的工作方式非常简单。它维护给定数组的两个子数组。

• 第一个子数组是已排序的。
• 第二个子数组是未排序的。

在选择排序的每一轮迭代中，都会从未排序的子数组中选择一个元素并将其移到已排序的子数组中。

让我们以示例数组 [5, 1, 12, -5, 16, 2, 12, 14] 来逐步演示选择排序过程。

初始数组 [5, 1, 12, -5, 16, 2, 12, 14]

第一次迭代

• 找出整个数组中的最小元素。在此情况下，-5 是最小的元素，位于索引 3。
• 将 -5 与第一个元素 5 交换。
• 更新后的数组：[-5, 1, 12, 5, 16, 2, 12, 14]

第二次迭代

• 找出子数组 [1, 12, 5, 16, 2, 12, 14] 中的最小元素。最小元素是 1，位于索引 1。
• 将 1 与第二个元素 5 交换。
• 更新后的数组：[-5, 1, 12, 5, 16, 2, 12, 14]

第三次迭代

• 找出子数组 [12, 5, 16, 2, 12, 14] 中的最小元素。最小元素是 2，位于索引 5。
• 将 2 与第三个元素 12 交换。
• 更新后的数组：[-5, 1, 2, 5, 16, 12, 12, 14]

第 4 次迭代

• 找出子数组 [5, 16, 12, 12, 14] 中的最小元素。最小元素是 5，位于索引 3。
• 将 5 与第四个元素 16 交换。
• 更新后的数组：[-5, 1, 2, 5, 16, 12, 12, 14]

迭代 5

• 找出子数组 [16, 12, 12, 14] 中的最小元素。最小元素是 12，位于索引 5。
• 将 12 与第五个元素 16 交换。
• 更新后的数组：[-5, 1, 2, 5, 12, 16, 12, 14]

第 6 轮迭代

• 找出子数组 [16, 12, 14] 中的最小元素。最小元素是 12，位于索引 6。
• 将 12 与第六个元素 16 交换。
• 更新后的数组：[-5, 1, 2, 5, 12, 12, 16, 14]

第 7 轮迭代

• 找出子数组 [16, 14] 中的最小元素。最小元素是 14，位于索引 7。
• 将 14 与第七个元素 16 交换。
• 更新后的数组：[-5, 1, 2, 5, 12, 12, 14, 16]

最终排序后的数组 [-5, 1, 2, 5, 12, 12, 14, 16]

经过七轮迭代，数组已完全按升序排序。

让我们用图示来表示选择排序算法的每一轮迭代。

选择排序实现

SelectionSort.java

输出

Before Selection sort:
5 1 12 -5 16 2 12 14 
After Selection sort:
-5 1 2 5 12 12 14 16

时间复杂度

选择排序的时间复杂度始终为 O(n^2)，其中 'n' 是数组中的元素数量。这是因为选择排序中嵌套了两个循环。外层循环每次运行 'n' 次，内层循环分别运行 (n-1)、(n-2)、(n-3)、...、1 次。这导致总共进行 n*(n-1)/2 次交换和比较。

空间复杂度

选择排序是一种原地排序算法，它在排序数组时不需要额外的空间，只需要几个用于迭代的变量。选择排序的空间复杂度为 O(n)，这意味着算法占用的空间不随输入数组的大小而变化。

选择排序算法的优点

实现简单： 选择排序以其简单性和易于理解性而著称。它通过多次遍历数组，找到最小（或最大）的元素，然后将其与第一个未排序的项进行交换来实现。这种简单性不仅使其适用于教学目的，也为学习排序算法打下了基础。

原地排序： 选择排序采用原地排序策略，除了几个迭代变量外，不需要与数组大小成比例的额外内存。这一点使其在内存效率方面表现出色，这在排序大型数组时尤其重要，因为内存使用量是一个关键问题。

稳定排序： 在所有排序算法中，选择排序是一种稳定的算法，它保留了已排序数组中相等元素的初始顺序。如果存在多个具有相同值的元素，在排序时会保留原始顺序。

自适应性： 尽管选择排序在所有情况下的时间复杂度都是 n^2，但如果数组大小很小或者没有太多的逆序对，它也可以足够快。在这些情况下，比较和交换的次数会减少，从而与其他 O(n^2) 算法相比效率更高。

适用于小型列表或近乎有序的列表： 选择排序在排序短列表或几乎已排序的列表时非常有效。虽然它对每个元素执行相同次数的交换，但对于非常小的输入或大部分元素已接近排序位置的输入，它的运行速度可能比更复杂的算法快。

选择排序算法的缺点

二次时间复杂度： 对于具有 'n' 个元素的数组，选择排序的时间复杂度为 O(n^2)。因此，随着数组大小的增加，排序时间与数组的平方成正比。选择排序不适用于大型数据集，而像归并排序或快速排序（分别具有更好的平均和最坏情况时间复杂度）会更实用。

缺乏自适应性： 选择排序无法适应数据。无论输入数组是部分排序还是未排序，它执行的比较和交换次数都相同。这就是为什么它不适用于输入数据可能已经部分排序的情况，因为它不会消除不必要的运算。

不适用于大型数据集： 然而，具有二次时间复杂度的选择排序不适用于对大型数据集进行排序。随着输入数组大小的增长，选择排序的效率开始显著恶化，使其在解决实际问题时不如快速排序或堆排序等更高效的算法。

大量的交换： 即使数组已经部分排列好，选择排序也会进行大量的交换。这会导致内存访问模式变慢，尤其是在处理存储在慢速内存设备上的数组时。

不适用于链表： 虽然选择排序可以应用于数组，但它不适用于链表。这是因为在链表的情况下，元素的顺序访问效果不佳，因此数组是更好的选择。