c++ - 如何计算选择排序中的比较次数？

Question

如何计算selectionsort中的比较次数？

条款: 当您执行查找最大值的语句为“true”时 然后进行计数比较。

获取最大值的值保存在数组的第一个元素中，而不是随机的。

我尝试用C 可变计数位置变化 - 不起作用 新变量 'first' ，first=sort[MAX] 插入第一个 for 循环，- 不起作用

#include <stdio.h>

int main() {
    int sort[10000], i, n, MAX, temp, count;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
       scanf("%d", &sort[i]);
    }
    for (MAX = 0; MAX < n; MAX++)
        for (i = MAX + 1; i < n; i++) {
            if (sort[MAX] > sort[i]) {
                count++;
                temp = sort[MAX];
                sort[MAX] = sort[i]; 
                sort[i] = temp;
            }
        }

    printf("%d  ", count);
    return 0;
}

示例输入

10
0 7 1 6 7 7 6 6 5 4 

示例输出

17

编辑:新代码:

#include <stdio.h>
#define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )

int count = 0;

void selection_sort(int list[], int n) {
    int i, j, least, temp;

    for (i = 0; i < n - 1; i++) {
        least = i;

        for (j = i + 1; j < n; j++) {
            if (list[j] < list[least]) {
                least = j;
                count++;
            }
        }
        SWAP(list[i], list[least], temp);
    }
}

int main() {
    int list[10000], i, n;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &list[i]);
    };
    selection_sort(list, n);

    printf("%d", count);
}

这个怎么样？为什么这段代码也没有动？

Answer 1

这段代码你算错了

     if(sort[MAX]>sort[i])  
     {
        count++;
         temp=sort[MAX];
         sort[MAX]=sort[i]; 
         sort[i]=temp;
     }

计算两个数字交换的次数。但你想计算比较，所以应该是这样的

     count++;
     if(sort[MAX]>sort[i])  // this is what we are counting
     {
         temp=sort[MAX];
         sort[MAX]=sort[i]; 
         sort[i]=temp;
     }

另一个问题是你没有给 count 初始值为零

int sort[10000],i,n,MAX,temp,count;

应该是

int sort[10000],i,n,MAX,temp,count = 0;