如何用C语言按元素重复次数对数组排序（禁用vector等容器）

问题描述 #

给定数组{1,2,2,2,3,3,3,3,4,4,4,4,4}，需要将其转换为{4,4,4,4,4,3,3,3,3,2,2,2,1}，即按元素的重复次数从多到少排序。要求用纯C语言实现，不能使用C++的vector等容器，仅可使用缓冲区数组或原地排序完成。

现有思路与问题 #

原计划通过三步实现：

• 统计每个元素的重复次数并写入第二个数组
• 对第二个数组进行排序
• 根据排序结果对原数组排序

但尝试的代码无法正常运行，核心问题在于统计重复次数的逻辑错误：比如j-1在i=j=0时会触发数组越界，且仅通过A[j] == A[j+1]统计次数的逻辑不完整，无法正确计算每个元素的总重复次数。

修正后的实现方案 #

步骤说明 #

1. 绑定元素与次数：用结构体存储每个唯一元素及其出现次数，避免单独数组存储时的对应关系混乱
2. 按次数降序排序：自定义排序规则，优先按次数从大到小排序，次数相同时可按需按元素值排序
3. 重构目标数组：根据排序后的结构体数组，将元素按次数依次填充回原数组或缓冲区数组

完整代码 #

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

// 存储元素值与对应出现次数的结构体
typedef struct {
    int value;
    int count;
} ElementCount;

// qsort自定义比较函数：按次数降序，次数相同则按元素值降序（可按需修改）
int compare(const void *a, const void *b) {
    ElementCount *elemA = (ElementCount *)a;
    ElementCount *elemB = (ElementCount *)b;
    if (elemB->count != elemA->count) {
        return elemB->count - elemA->count;
    } else {
        return elemB->value - elemA->value;
    }
}

int main() {
    int arr[] = {1,2,2,2,3,3,3,3,4,4,4,4,4};
    int size = sizeof(arr) / sizeof(arr[0]);
    ElementCount elemCounts[size]; // 缓冲区数组，最坏情况每个元素都唯一
    int uniqueCount = 0;

    // 第一步：统计每个元素的出现次数
    for (int i = 0; i < size; i++) {
        int found = 0;
        // 检查当前元素是否已被统计
        for (int j = 0; j < uniqueCount; j++) {
            if (elemCounts[j].value == arr[i]) {
                elemCounts[j].count++;
                found = 1;
                break;
            }
        }
        // 未统计过则新增记录
        if (!found) {
            elemCounts[uniqueCount].value = arr[i];
            elemCounts[uniqueCount].count = 1;
            uniqueCount++;
        }
    }

    // 第二步：按次数降序排序结构体数组
    qsort(elemCounts, uniqueCount, sizeof(ElementCount), compare);

    // 第三步：原地重构原数组
    int index = 0;
    for (int i = 0; i < uniqueCount; i++) {
        for (int j = 0; j < elemCounts[i].count; j++) {
            arr[index++] = elemCounts[i].value;
        }
    }

    // 输出结果
    printf("排序后的数组：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

代码说明 #

• 结构体ElementCount绑定元素值和次数，避免单独数组存储时的对应关系错位
• 嵌套循环统计次数适合小数据量；若处理大数据集，可先对原数组排序再统计，效率更高
• 利用标准库qsort实现排序，自定义比较函数满足需求
• 最后通过遍历结构体数组，将元素按次数填充回原数组，完成原地修改（也可使用新的缓冲区数组）

原代码问题分析 #

1. 数组越界：当i=0、j=0时，A[j-1]访问A[-1]，属于非法越界，会触发未定义行为
2. 统计逻辑缺失：仅通过A[j] == A[j+1]计数，无法统计最后一个元素的次数，且重复元素的计数会被多次初始化
3. 存储对应关系混乱：counter2的递增逻辑不合理，导致B数组中存储的次数与元素无法正确对应

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