一个简化的插入排序的 C 语言程序.pdf

简化的插入排序c 在这个程序中，我们定义了一个名为 `insertionSort` 的函数来执行插入排序。函数接受两个参数：要排序的数组 `arr` 和数组的大小 `n`。 在主函数中，我们首先定义一个待排序的数组 `arr`，然后计算出数组的大小 `n`。 接下来，我们调用 `insertionSort` 函数来对数组进行排序。 `insertionSort` 函数中使用了一个 `for` 循环来遍历数组。在每一次循环中，我们取出当前元素 `arr[i]`，并将其与已排序的子数组比较。 如果已排序的子数组中的元素大于当前元素，则将子数组中的元素后移一位。 最后，将当前元素插入到适当的位置。完成所有的循环后，整个数组将会被排序。 程序输出的结果是经过插入排序后的有序数组。 插入排序是一种简单的排序算法，它的基本思想是将未排序的元素逐个地插入到已排序的序列中。在C语言中实现插入排序，通常通过编写一个函数来完成，如题目中所示的`insertionSort`函数。这个函数接收一个整型数组`arr`和数组的大小`n`作为参数。 在`insertionSort`函数内部，使用一个`for`循环从第二个元素（索引为1）开始遍历数组。每次循环中，`key`变量存储当前要插入的元素，即`arr[i]`。同时，`j`变量用于追踪已排序子数组的最后一个元素的索引，初始化为`i - 1`。 在`while`循环中，我们检查`arr[j]`是否大于`key`。如果条件成立，意味着`arr[j]`应该位于`key`的前面，因此将`arr[j]`向右移动一位，将`arr[j+1]`赋值给`arr[j]`，同时将`j`减1，继续检查下一个元素。这个过程一直持续到找到一个不大于`key`的元素或者`j`小于0为止。 当`while`循环结束时，我们知道`arr[j+1]`已经为`key`准备好了位置，此时将`key`插入到`arr[j+1]`，完成一次插入操作。`for`循环会继续处理数组的下一个元素，直到整个数组都被遍历并排序完成。 在`main`函数中，我们首先定义一个待排序的数组`arr`，并计算其大小`n`。然后调用`insertionSort`函数对数组进行排序。通过一个`for`循环打印出排序后的数组，以验证排序的正确性。 插入排序的时间复杂度在最坏情况下是O(n^2)，在最好情况下（输入数组已经是有序的）是O(n)。尽管插入排序对于大规模数据并不高效，但对于小规模数据或部分有序的数据，它的性能相对较好，因为交换和移动操作较少。此外，由于其简单性和易于理解，插入排序常作为教学示例使用，也是其他更复杂排序算法（如希尔排序）的基础。