C++实现插入排序算法：时间复杂度与随机数列优化

插入排序是一种简单直观的排序算法，适用于小型数据集或部分已经有序的数据。在C++中，这个算法可以通过`insertionsort`函数实现。本代码提供了三个排序函数：冒泡排序（bubblesort）、选择排序（selectionsort）和插入排序（insertionsort）。这里主要关注的是插入排序。 **插入排序**： 插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。具体步骤如下： 1. **初始化**：遍历数组，从第二个元素开始（索引为1），将当前元素视为“待插入”元素。 2. **比较与插入**：对于每个“待插入”元素，与已排序部分的每个元素进行比较，如果当前元素小于前一个元素，则交换它们的位置，直到找到合适的位置或者已达到已排序部分的末尾。 3. **递归过程**：当所有元素都完成排序后，数组即为有序。 在给定的代码片段中，`insertionsort`函数实现如下： ```cpp void insertionsort(int c[], int N){ int i; // 当前已排序部分的边界 int j; // 当前待插入元素的索引 int temp; // 临时存储值 int start3 = clock(); // 记录开始时间 for (j = 1; j < N; j++) { // 遍历数组，从第二个元素开始 temp = c[j]; // 备份当前元素 i = j - 1; // 已排序部分的最后一个元素 // 将当前元素逐个向右移动，找到正确的位置 while (i >= 0 && c[i] > temp) { c[i + 1] = c[i]; // 如果前一个元素大于temp，将它向右移一位 i--; // 减小已排序部分的边界 } c[i + 1] = temp; // 将temp插入到正确的位置 } int end3 = clock(); // 记录结束时间 int time3 = end3 - start3; // 计算排序所需的时间 cout << "insertionsortingtime: " << time3 << endl; // 输出排序时间 } ``` 该函数首先初始化`i`和`j`，然后在循环中不断比较和移动元素，直到数组完全排序。这种算法的时间复杂度在最好、最坏和平均情况下都是O(n^2)，但对于近乎有序的输入，性能会相对较好。 总结来说，这段代码展示了如何用C++实现插入排序算法，并通过`clock()`函数来测量排序所需的时间。对比其他排序算法如冒泡排序和选择排序，插入排序在处理部分有序的数据时效率更高。然而，对于大规模数据，更高效的排序算法如快速排序、归并排序或堆排序更为适用。