已知数组最值，求O(n+y−x)时间复杂度的排序算法（作业求助）

嘿，我来帮你搞定这个作业题！你提到的O(n + y - x)时间复杂度的排序算法，其实就是**计数排序（Counting Sort）**的适配版本，完全符合你的需求，咱们一步步拆解清楚。

计数排序的时间复杂度是O(n + k)，其中k是待排序元素的取值范围大小。这里题目里的k就是y - x + 1（从最小整数x到最大整数y，共有y-x+1个不同的整数），忽略常数项后正好是O(n + y - x)，完美匹配题目要求。

具体步骤拆解：

• 第一步：确认数组的最小值x和最大值y（这一步可以通过一次遍历数组完成，时间O(n)）
• 第二步：创建一个长度为y - x + 1的计数数组count，初始化为0。我们可以把每个元素值减去x，得到它在计数数组中的索引（比如x对应索引0，x+1对应索引1，以此类推，y对应索引y-x）
• 第三步：遍历原数组，统计每个元素的出现次数：对每个元素A[i]，计算索引idx = A[i] - x，然后让count[idx]++（时间O(n)）
• 第四步：遍历计数数组，把元素按顺序回填到原数组中：从索引0开始，count[idx]是几，就把x + idx重复写入原数组几次（时间O(y - x + 1)）

把这些步骤加起来，总时间就是O(n + y - x)，完全满足题目要求。

你之前的代码只处理了最小和最大元素，这显然不够完成整个排序。我把你的代码补全并修正错误，写成完整的C实现：

#include <stdio.h>
#include <stdlib.h> // 用于malloc和free

// 修正参数：传入数组指针、数组长度n，以及已知的x和y
void countingSort(int *array, int n, int x, int y) {
    int range = y - x + 1;
    // 动态分配计数数组内存，避免栈溢出
    int *count = (int *)malloc(range * sizeof(int));
    if (count == NULL) {
        printf("内存分配失败\n");
        return;
    }

    // 初始化计数数组为0
    for (int i = 0; i < range; i++) {
        count[i] = 0;
    }

    // 统计每个元素的出现次数
    for (int i = 0; i < n; i++) {
        int idx = array[i] - x;
        count[idx]++;
    }

    // 将计数结果回填到原数组
    int pos = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            array[pos++] = x + i;
            count[i]--;
        }
    }

    // 释放动态分配的内存，避免泄漏
    free(count);
}

// 测试用例
int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    // 如果作业要求自己找出x和y，可以加这段代码
    int x = arr[0], y = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < x) x = arr[i];
        if (arr[i] > y) y = arr[i];
    }

    printf("排序前：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    countingSort(arr, n, x, y);

    printf("排序后：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

• 你原来的代码参数有误：int array应该改成int *array（传递数组指针），同时必须传入数组长度n才能正确遍历
• 用malloc动态分配计数数组，避免当y-x很大时出现栈溢出问题
• 记得释放动态分配的内存，这是C语言的好习惯，避免内存泄漏
• 如果作业要求程序自动找出x和y，我在main函数里加了一段遍历数组的代码，你可以直接用

你之前只处理最小和最大元素的思路是对的方向，计数排序就是把这个思路扩展到所有元素，通过统计每个元素的出现次数，再按顺序回填，就能高效完成整个数组的排序啦。

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