修复qsort()算法：跨编译环境排序结果不稳定问题

问题背景 #

开发简易“3D”体素与平面渲染引擎，需实现按相机位置排序物体的逻辑：远处物体（Z轴值更大）优先绘制；Z轴相同时，绘制离屏幕中心（player_x/player_y）更远的物体。该逻辑在PC端gcc、clang编译下运行正常，但目标设备工具链编译后排序结果每次不一致，已排除稳定排序问题，调试13-15小时未解决。

核心代码问题分析 #

问题出在compareCoordinates函数的两个关键错误：

1. 曼哈顿距离计算笔误 #

原代码中计算coord1的X轴距离时错误使用了player_y，导致距离计算错误：

// 错误代码
int value = (abs(coord2[0] - player_x) + abs(coord2[1] - player_y)) - (abs(coord1[0] - player_y) + abs(coord1[1] - player_y));

此处coord1[0] - player_y应为coord1[0] - player_x，coord[0]对应X轴坐标，需与player_x计算距离。

2. 比较函数违反严格弱序要求 #

qsort的比较函数必须满足严格弱序：若compare(a,b) > 0则compare(b,a) < 0，相等元素必须返回0。原代码中当value=0时返回1，会让qsort认为a > b且b > a，逻辑矛盾。不同平台的qsort实现对这种错误的容错性不同，PC端可能侥幸得到正确结果，而目标设备的libc实现会因此产生随机排序结果。

修复后的比较函数 #

修正笔误并遵守严格弱序的版本：

int compareCoordinates(const void *a, const void *b) {
    const int8_t *coord1 = (const int8_t *)a;
    const int8_t *coord2 = (const int8_t *)b;
    
    // 按Z轴降序：Z值更大的物体（远处）优先
    int z_diff = coord2[2] - coord1[2];
    if (z_diff != 0) {
        return z_diff;
    }
    
    // 计算曼哈顿距离，按距离降序：离屏幕中心更远的优先
    int dist1 = abs(coord1[0] - player_x) + abs(coord1[1] - player_y);
    int dist2 = abs(coord2[0] - player_x) + abs(coord2[1] - player_y);
    
    // 相等时返回0，满足严格弱序
    return dist2 - dist1;
}

自定义排序实现（可选） #

若目标设备的qsort仍存在兼容性问题，可实现自定义排序函数，以下为两种方案：

方案1：自定义快速排序（适用于大数据量） #

// 交换两个元素
static void swap(int8_t *a, int8_t *b) {
    int8_t temp[3];
    memcpy(temp, a, sizeof(temp));
    memcpy(a, b, sizeof(temp));
    memcpy(b, temp, sizeof(temp));
}

static int partition(int8_t arr[][3], int low, int high) {
    int8_t *pivot = arr[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
        if (compareCoordinates(&arr[j], &pivot) <= 0) {
            i++;
            swap((int8_t*)&arr[i], (int8_t*)&arr[j]);
        }
    }
    swap((int8_t*)&arr[i+1], (int8_t*)&arr[high]);
    return i + 1;
}

static void custom_quick_sort(int8_t arr[][3], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        custom_quick_sort(arr, low, pi - 1);
        custom_quick_sort(arr, pi + 1, high);
    }
}

// 替换原sortCoordinateList
void sortCoordinateList(int8_t coordinates[][3], int numCoordinates) {
    custom_quick_sort(coordinates, 0, numCoordinates - 1);
}

方案2：冒泡排序（适用于小数据量，实现简单） #

void sortCoordinateList(int8_t coordinates[][3], int numCoordinates) {
    for (int i = 0; i < numCoordinates - 1; i++) {
        for (int j = 0; j < numCoordinates - i - 1; j++) {
            // 若前一个元素应排在后面，则交换
            if (compareCoordinates(&coordinates[j], &coordinates[j+1]) > 0) {
                int8_t temp[3];
                memcpy(temp, coordinates[j], sizeof(temp));
                memcpy(coordinates[j], coordinates[j+1], sizeof(temp));
                memcpy(coordinates[j+1], temp, sizeof(temp));
            }
        }
    }
}

验证结果 #

使用测试数据：

int8_t coordinates[][3] = { {1,2,5}, {-1,2,5}, {-3,2,5} };
player_x = 0; player_y = 0;

修正后排序结果应为：

(-3, 2, 5)
(1, 2, 5)
(-1, 2, 5)

（后两个元素距离相等，顺序固定不会随机变化）

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