Java 中的插入排序

插入排序是一种简单的排序算法，它通过一次将一个元素与已排序的数组进行比较，然后将其插入到正确的位置来构建最终的排序数组。它遍历数组，从起始位置提取一个元素，并将其插入到数组已排序部分的正确位置。插入排序背后的思想是在数组的较低位置保留一个已排序的子列表，同时通过将新元素插入到子列表中来将其移动到正确的位置。

以下是适合使用插入排序的一些情况：

小型数据集：插入排序的时间复杂度为 O(n^2)，因此对于大型数据集来说效率可能不高。相反，对于小型数据集（例如，少于 100 个项目），插入排序可能比具有更高复杂度和较低开销的复杂算法更快。

近乎排序的数据集：如果输入数据集本身几乎已排序，则插入排序将是一种有效的算法，因为它只需要进行少量的交换或比较即可将元素排列成正确的顺序。

在线排序：在元素以实时模式不断添加到列表或数组的情况下，可以使用插入排序。当添加新元素时，其增量性质非常适合维护已排序的列表。

自适应排序：插入排序是一种自适应排序算法，这意味着它在处理部分排序的数据集时比处理完全未排序的数据集表现更好。如果输入数据集部分有序或包含的元素很少不符合排序顺序，插入排序算法将很快恢复并快速对元素进行排序。

音乐应用程序中的播放列表管理：在音乐应用程序中，用户可能会经常逐个添加歌曲。当新歌曲被添加时，排序将在播放列表中保持动态，以确保基于歌曲标题、艺术家姓名或发行日期等标准对列表进行排序。

嵌入式系统中的简单排序任务：在计算资源较低的嵌入式系统中，可以由于其易于实现和占用的内存空间少而使用插入排序来对小型数组或列表进行排序。例如，在物联网设备中完成小型任务，如对传感器读数进行排序或处理小型数据集。

插入排序如何工作？

递归地，从数组的未排序部分取出一个元素，并将其插入到已排序的子列表中正确的位置。 undefined

从第二个元素开始：让我们假设数组的前一部分已经排序。从数组的第二个元素（索引 1）开始迭代。

比较和插入：对于数组未排序部分中的每个元素

• 将当前元素与已排序子列表右侧的元素进行比较，从最右边的元素开始。
• 将大于正在比较的元素向右移动一个位置。
• 将当前元素插入到其在已排序子列表中的合适位置。

重复：继续这样做，并在每次迭代中不断扩展已排序的子列表。

最终排序数组：完成这些步骤后，数组将完全排序。

让我们逐步回顾示例数组 [1, 3, 7, 9, 16, 5] 的插入排序过程。

初始数组 [1, 3, 7, 9, 16, 5]

迭代 1（从索引 1 开始）

• 取第二个元素 **3**。
• 将 **3** 与 **1**（已排序子列表中的唯一元素）进行比较。
• 由于 **3** 大于 **1**，它保留在其当前位置。
• 数组保持：[1, 3, 7, 9, 16, 5]。

迭代 2（从索引 2 开始）

• 取第三个元素 **7**。
• 将 **7** 与已排序子列表中的元素（**3** 和 **1**）进行比较。
• 由于 **7** 大于 **3** 和 **1**，它保留在其当前位置。
• 数组保持：[1, 3, 7, 9, 16, 5]。

迭代 3（从索引 3 开始）

• 取第四个元素 **9**。
• 将 **9** 与已排序子列表中的元素（7、3 和 1）进行比较。
• 由于 **9** 大于已排序子列表中的所有元素，它保留在其当前位置。
• 数组保持：[1, 3, 7, 9, 16, 5]。

迭代 4（从索引 4 开始）

• 取第五个元素 **16**。
• 将 **16** 与已排序子列表中的元素（9、7、3 和 1）进行比较。
• 由于 **16** 大于已排序子列表中的所有元素，它保留在其当前位置。
• 数组保持：[1, 3, 7, 9, 16, 5]。

迭代 5（从索引 5 开始）

• 取第六个元素 **5**。
• 将 **5** 与已排序子列表中的元素（16、9、7、3 和 1）进行比较。
• 将 **5** 插入到 **3** 和 **7** 之间。
• 数组变为：[1, 3, 5, 7, 9, 16]。

遍历完所有元素后，数组完全排序：[1, 3, 5, 7, 9, 16]。

插入排序算法实现

InsertionSortExample.java

输出

Before Insertion Sort
9 14 3 2 43 11 58 22 
After Insertion Sort
2 3 9 11 14 22 43 58 

时间复杂度

最坏情况： O(n^2)

最佳情况： O(n)

平均情况： O(n^2)

最坏的情况是数组按反向排序，插入排序需要执行 n^2/2 次比较和交换。尽管如此，在最佳情况下，当数组已排序时，插入排序仅需要 n - 1 次比较且无需交换。

空间复杂度

O(1)

插入排序会就地排序列表。因此，它不使用任何额外的、与输入列表大小成比例的空间。结果，空间复杂度是常数的，表示为 O(1)。

插入排序算法的优点

实现简单：插入排序的实现非常容易，因此可以用于教学目的或性能不是关键考虑因素的情况。

对小型数据集高效：它在小型数据集或几乎已排序的数组上表现良好。当数组已经部分排序时，插入排序的运行时与输入大小成正比，这使其比更复杂的算法更快。

自适应：插入排序是自适应的；也就是说，它能够有效地管理已经部分排序的数组。它根据元素的初始放置调整其方法，可能节省算法需要执行的比较和交换次数。

稳定排序算法：插入排序是一种稳定的排序算法，它处理相同元素的相对顺序。此属性对于处理多键排序以及保留相似元素自然顺序的情况至关重要。

就地排序：它就地排列数组，无论数组维度如何，仅占用 O(1) 的额外空间。通过使其内存高效并适用于使用有限内存资源的排序大型数据集，它实现了这一点。

插入排序算法的缺点

二次时间复杂度：插入排序的最坏情况时间复杂度为 O(n^2)，其中 n 是数组中元素的数量。这就是为什么当应用于大型数据集时，桶排序会变得效率低下，因为比较和交换的次数与输入大小的平方成正比。

不适合大型数据集：由于其二次时间复杂度，插入排序不适用于组织大量数据。随着数组大小的增长，排序数组可能需要很长时间。

不如归并排序或快速排序高效：尽管它非常适合小型数据集或几乎已排序的数组，但在数据集大小增加时，插入排序的性能会逊色于更高效的算法，包括归并排序和快速排序。这些类型的算法通常提供更好的平均和最坏情况时间复杂度。

通常不自适应：尽管插入排序通常在几乎排序的数组上表现更好，但由于元素的原始顺序，它并不总是表现更好。相反，像归并排序和快速排序这样的算法可以拥有独立的输入顺序的最佳平均情况行为。

在实际应用中的用途有限：插入排序通常用作更复杂算法的组成部分或教学工具，但在性能要求至关重要的实际应用中，它很少被采用。在这种情况下，通常首选更优化的排序算法。