基于Bubble Sort按面积排序triangle结构体数组出现顺序异常求助

我尝试对存储在triangle结构体数组中的三角形按面积排序，思路是创建一个存储面积的并行数组，用冒泡排序同时交换两个数组的元素。排序逻辑写在接收数组和元素数量的void函数sort_by_area里。现在发现面积数组排序后输出正确，但triangle结构体数组的排序结果既不是预期顺序也不是初始顺序。我选冒泡排序是为了学习基础排序实现，暂时不想用qsort函数。

完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct triangle {
    int a;
    int b;
    int c;
};

typedef struct triangle triangle;
void sort_by_area(triangle *tr, int n) {
    double s[n];
    double p, s_2;
    int u;
    triangle v;
    for (int i = 0; i < n; i++) {
        p = (tr[i].a + tr[i].b + tr[i].b);
        p = p / 2.0;
        s_2 = p * (p - tr[i].a) + (p - tr[i].b) + (p - tr[i].c);
        s[i] = sqrt(s_2);
    }

    //bubble sort
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < (n - i - 1); j++) {
            if (s[j] > s[j + 1]) {
                u = s[j];
                s[j] = s[j + 1];
                s[j + 1] = u;
                
                v = tr[j];
                tr[j]= tr[j + 1];
                tr[j + 1] = v;
                //printf("swapped");
            }
        }
    } 
    
    for (int i = 0; i < n; i++) {
        printf("%f\n", s[i]);
        if (i == (n - 1)) {
            printf("\n\n");
        }
    }    
}

int main() {
    int n;
    scanf("%d", &n);
    triangle *tr = malloc(n * sizeof(triangle));
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d", &tr[i].a, &tr[i].b, &tr[i].c);
    }
    sort_by_area(tr, n);
    for (int i = 0; i < n; i++) {
        printf("%d %d %d\n", tr[i].a, tr[i].b, tr[i].c);
    }
    return 0;
}

测试输入示例 #

10
67 67 19
3  57 55
33 33 33
61 58 59
23 43 35
48 42 45
23 12 27
41 34 22
26 49 35
63 46 45

当前输出结果 #

23 12 27
41 34 22
33 33 33
63 46 45
48 42 45
23 43 35
26 49 35
61 58 59
3 57 55
67 67 19

问题分析与修复 #

你的代码存在三个关键错误，导致面积计算错误，进而让结构体排序逻辑完全偏离预期：

1. 半周长计算错误：
   原代码中半周长写成了 p = (tr[i].a + tr[i].b + tr[i].b);，重复累加了b边，正确的半周长应该是三边之和除以2：

   p = (tr[i].a + tr[i].b + tr[i].c) / 2.0;
   

2. 海伦公式计算错误：
   海伦公式的正确形式是 面积² = p*(p-a)*(p-b)*(p-c)，你错误地把乘法写成了加法：

   s_2 = p * (p - tr[i].a) * (p - tr[i].b) * (p - tr[i].c);
   

3. 面积交换时的类型错误：
   交换面积数组元素时，变量u的类型是int，但s数组是double类型，这会导致精度丢失，需要把u改为double类型。

修正后的sort_by_area函数 #

void sort_by_area(triangle *tr, int n) {
    double s[n];
    double p, s_2;
    double u; // 修正类型为double
    triangle v;
    for (int i = 0; i < n; i++) {
        p = (tr[i].a + tr[i].b + tr[i].c) / 2.0; // 修正半周长计算
        s_2 = p * (p - tr[i].a) * (p - tr[i].b) * (p - tr[i].c); // 修正海伦公式
        s[i] = sqrt(s_2);
    }

    //bubble sort
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < (n - i - 1); j++) {
            if (s[j] > s[j + 1]) {
                u = s[j];
                s[j] = s[j + 1];
                s[j + 1] = u;
                
                v = tr[j];
                tr[j]= tr[j + 1];
                tr[j + 1] = v;
            }
        }
    } 
    
    for (int i = 0; i < n; i++) {
        printf("%f\n", s[i]);
        if (i == (n - 1)) {
            printf("\n\n");
        }
    }    
}

修正后，结构体数组会按照面积从小到大正确排序，输出的三角形顺序会和面积数组的顺序完全匹配。

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