C 语言插入排序

插入排序是一种简单的排序算法，它以迭代方式一次一个地构建数组的已排序部分。它是一种基于比较的原地方法，平均时间复杂度为 O(n²)。

该方法将数组分为两半：已排序和未排序。数组的第一个元素首先被认为是已排序部分，而其余项最初被认为是未排序部分。

算法随后将每个未排序元素与已排序部分中的元素进行比较，从末尾开始，并向右移动较大的元素一个位置，直到在正确位置找到未排序元素。

确定正确位置后，未排序元素将被插入到已排序部分的该位置。

重复此过程，直到未排序部分的所有成员都已插入到已排序部分，从而形成一个完全排序的数组。

以下是插入排序的伪代码

在此伪代码中，n 表示数组中的元素数量，arr 表示要排序的数组，i 和 j 是循环变量，key 是要插入到数组已排序部分中的元素。

用途

插入排序对于对小型数组进行排序非常有用，并且当输入数组已部分排序时，其速度表现良好。它经常用作更高级排序算法（如归并排序和快速排序）的构建块。

以下是 C 语言中插入排序的示例

输出

5 6 11 12 13

此代码定义了 insertionSort 函数，该函数将整数数组 arr 及其大小 n 作为输入。该函数使用 for 循环遍历数组的每个元素，从第二个元素开始（因为第一个元素已排序）。

该函数将每个元素的值存储在一个名为 key 的变量中，并将一个名为 j 的变量设置为前一个元素的索引。然后，代码使用 while 循环将 key 与每个前一个元素进行比较，直到找到 key 的正确位置。

每个大于 key 的元素都向右移动一个位置，并且 j 递减，直到达到正确位置。随后，通过将其赋值给 arr[j + 1] 将 key 插入到正确位置。

最后，main 函数使用示例数组及其大小来运行 insertionSort，然后输出排序后的数组。

优点

• 易于实现：由于该方法易于构建和理解，因此是教授基本排序概念的绝佳选择。
• 因为它对数组进行原地排序，所以插入排序不需要任何额外的内存空间。
• 插入排序是一种自适应排序算法，对于部分排序的输入数组效果最佳。
• 稳定排序意味着该方法在输入数组中保持相等元素的相对顺序不变。

缺点

• 对于大型数组速度慢：由于平均时间复杂度为 O(n2)，该算法对于大型数组速度慢。
• 插入排序对于随机输入数组效率低下，因为它涉及大量的比较和移动。
• 该算法不适用于并行化，因为每次迭代都依赖于前一次迭代的结果。

结论

插入排序为小型或部分排序的数组提供了一种直接而有效的方法。它不适用于大型数组或随机输入，但可用于构建更复杂的排序算法。总的来说，插入排序是高效排序小型或部分排序数组且内存使用量小的可靠解决方案。