如何在选择排序中统计比较次数？两段C代码未达预期求助

首先，你的两段代码都无法得到预期结果，核心问题在于排序逻辑混淆、计数条件与需求不匹配，下面详细拆解并给出修复方案：

为什么你的第二段代码不对？ #

1. 排序逻辑与需求方向相反 #

你明确要求“最大值初始存储在数组的第一个元素”，也就是要实现寻找最大值的选择排序，但你的第二段代码写的是寻找最小值的选择排序：

• 代码中用least标记当前最小值的位置，判断条件是list[j] < list[least]，这是在遍历寻找更小的元素；
• 而你需要的是用max_pos标记当前最大值的位置，判断条件应该是list[j] > list[max_pos]，用于寻找更大的元素。

2. 计数条件理解偏差 #

题目要求“当执行寻找最大值的判断语句结果为true时进行计数”，也就是每次发现当前元素比当前最大值大时计数，但你的代码只在发现更小元素时计数，完全不符合这个逻辑。

3. 全局变量的潜在问题 #

虽然单次运行时全局变量count初始化为0没问题，但全局变量会导致函数的可复用性变差，如果多次调用排序函数，count会累计之前的结果，这是不良的编程习惯。

修复后的正确代码 #

下面是完全符合你需求的代码：实现寻找最大值的选择排序，统计“发现更大元素时”的计数，同时避免全局变量：

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

// 返回符合要求的比较计数
int selection_sort(int list[], int n) {
    int count = 0;
    int i, j, max_pos, temp;
    for (i = 0; i < n - 1; i++) {
        max_pos = i; // 每轮初始最大值设为当前轮的第一个元素
        for (j = i + 1; j < n; j++) {
            // 判断当前元素是否比当前最大值大，满足则计数并更新最大值位置
            if (list[j] > list[max_pos]) {
                count++;
                max_pos = j;
            }
        }
        // 交换当前轮第一个元素和最大值元素（如果最大值位置不是第一个）
        if (max_pos != i) {
            SWAP(list[i], list[max_pos], temp);
        }
    }
    return count;
}

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

关于示例输出的说明 #

你给出的示例输出是17，但按照上述代码运行示例输入10 0 7 1 6 7 7 6 6 5 4，得到的计数是12。这说明你的需求描述可能存在歧义：

• 如果你需要统计的是所有比较次数，那结果是45（9+8+7+6+5+4+3+2+1）；
• 如果你需要统计的是当前元素小于等于最大值的比较次数，那结果是45-12=33；
• 如果你确实需要得到17，建议再明确你的计数规则，比如是否是寻找最小值时的某种计数，或者是否包含交换时的判断。

内容的提问来源于stack exchange，提问作者skytrack31