c - C.Heapsort .计数交换和比较的次数
问题描述
排序似乎工作正常。至少它排序正确:) 它仍然只计算比较和交换的数量。如何计算和输出它?不知何故在这一点上停滞不前。我将非常感谢您的帮助。如果您用更新的代码进行演示,我将倍加感激。
#include <stdio.h>
#include <stdlib.h>
void keyDown(int* arr, int n, int head)
{
int j;
if(2*head + 2 < n && arr[2*head + 1] < arr[2*head + 2])
{
j = 2*head + 2;
}
else j = 2*head + 1;
while(arr[head] < arr[j] && head < n / 2)
{
int tmp = arr[head];
arr[head] = arr[j];
arr[j] = tmp;
head = j;
if(2*head + 2 < n && arr[2*head + 1] < arr[2*head + 2])
{
j = 2*head + 2;
}
else j = 2*head + 1;
}
}
void heapSort(int* arr, int n)
{
int i;
for(i = n/2 - 1; i >= 0; i--)
{
keyDown(arr,n,i);
}
int l = n;
while(l > 1)
{
l--;
int tmp = arr[l];
arr[l] = arr[0];
arr[0] = tmp;
keyDown(arr,l,0);
}
}
int main(int argc, char *argv[]) {
int n=10;
int start, end,i;
int *arr;
arr=(int *)malloc(n*sizeof(int));
time_t invocation_time = time(NULL);
srand(invocation_time);
int s;
for (s=0;s<n;s++)
{
arr[s] = rand() % 50;
printf ("%d \n", arr[s]);
}
printf ("\n");
heapSort(arr, n);
for (i=0;i<n;i++){
printf ("%d \n", arr[i]);
}
return 0;
}
解决方案
计算比较和交换的次数
制作函数
//global counters
unsigned comparisons = 0, swaps = 0;
int lessthan(int a, int b) {
comparisons++;
return (a < b);
}
void swap(int *a, int *b) {
swaps++;
int tmp = *a; *a = *b; *b = tmp;
}
然后用您需要的特定功能替换现有代码中的比较和交换。
int main(int argc, char **argc) {
//...
if (lessthan(a[i], a[j])) swap(a+i, a+j);
//...
printf("comparisons: %u; swaps: %u\n", comparisons, swaps);
}
推荐阅读
- angular - 在 pdf 和图像上绘图
- r - OpenCPU 公共服务器是否仍然可用?API 规范似乎已更改
- python - 如何将扩展父类的属性获取到其嵌套的子类?
- javascript - 使用 AJAX 通过 Id 获取数据 | JSON ASP.NET
- apache-flink - 如何使用 java 在 Apache flink 中读取 json 文件格式
- python - Django,用户注册后创建新的配置文件模式时出错
- javascript - 如何使用 JavaScript 或任何方式在移动设备中停止引导 4 轮播自动滑动
- python - Python语音识别卡住了(Mac)
- java - 测试/演示 Java RCE 反序列化
- arrays - 如何在vala中创建对象实例数组