插入排序是一种简单直观的排序算法，适用于小型数据集或部分已经有序的数据。在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()`函数来测量排序所需的时间。对比其他排序算法如冒泡排序和选择排序，插入排序在处理部分有序的数据时效率更高。然而，对于大规模数据，更高效的排序算法如快速排序、归并排序或堆排序更为适用。
我的内容管理
展开
