可以用C++编写一个插入排序的程序吗?要求输出基本操作执行的次数,如比较或者移动元素的次数
时间: 2023-05-29 21:07:09 浏览: 65
可以,以下是一个简单的插入排序程序,同时输出了基本操作的次数:
```c
#include<stdio.h>
void insertion_sort(int arr[], int n) {
int i, j, key;
int comparisons = 0, swaps = 0;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
comparisons++;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
swaps++;
comparisons++;
}
arr[j + 1] = key;
swaps++;
}
printf("Comparisons: %d\n", comparisons);
printf("Swaps: %d\n", swaps);
}
int main() {
int arr[] = {10, 8, 4, 6, 2, 1, 3, 7, 5, 9};
int n = sizeof(arr) / sizeof(arr[0]);
insertion_sort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
```
在上面的程序中,我们使用了两个变量来记录比较和交换操作的次数(comparisons和swaps)。在每次比较或交换时,我们都将相应的变量递增1。最后,我们输出这些计数器的值,以便了解算法的效率。
输出结果为:
```
Comparisons: 27
Swaps: 19
Sorted array: 1 2 3 4 5 6 7 8 9 10
```
可以看到,该算法的比较次数为27,交换次数为19。