计数排序导致段错误

Question

我正在尝试用 C 实现计数排序算法，但遇到了一个奇怪的问题。

基本上与

的输入

0 0 0 0 0 1 1 1 1 2 2 2 3 3 4 6 7 7 8 10 10 10 10 10 8 8 9 9 9 9

我的代码会导致云构建出现段错误，但不是在我的实际 PC 上，而是在 我无法调试云构建，但它在我的 PC 上运行完全正常并提供所需的输出。

#include <stdio.h>
#include <string.h>
#include "introprog_countsort.h"
#include "arrayio.h"
#include <stdlib.h>

void count_sort_calculate_counts(int input_array[], int len, int count_array[]) {
    for (int i = 0; i < len; i++)
        count_array[input_array[i]]++;
}

void count_sort_write_output_array(int output_array[], int count_array[], SortDirection order) {
    int output_idx = 0;
    int max = output_array[0];
    output_array[0] = 0;
    if (order == ASCENDING) {
        for (int i = 0; i < max; i++) {
            if (count_array[i] == 0) {
            } else {
                for (int j = 0; j < count_array[i]; j++) {
                    output_array[output_idx++] = i;
                }
            }
        }
    } else {
        for (int i = max - 1; i > 0; i--) {
            if (count_array[i] == 0) {
                continue;
            } else {
                for (int j = 0; j < count_array[i]; j++)
                    output_array[output_idx++] = i;
            }
        }
    }
}

void count_sort(int input_array[], int len, int output_array[], SortDirection order) {
    for (int i = 0; i < len; i++)
        output_array[i] = 0;
    int max = 0;
    for (int i = 0; i < len; i++)
        max = input_array[i] > max ? input_array[i] : max;
    output_array[0] = max + 1; // PRO GAMER MOVE
    int count_array[max + 1];
    for (int i = 0; i < max + 1; i++)
        count_array[i] = 0;
    count_sort_calculate_counts(input_array, len, count_array);
    count_sort_write_output_array(output_array, count_array, order);
}

/* Ab hier Funktion extract_order_direction implementieren */
SortDirection extract_order_direction(char *order) {
    SortDirection direction = NOTDEFINED;
    if (strcmp(order, "desc") == 0)  direction = DESCENDING;
    if (strcmp(order, "asc") == 0)  direction = ASCENDING;
    return direction;
}

int main(int argc, char *argv[]) {
    int input_array[] = {
        0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 6,
        7, 7, 8, 10, 10, 10, 10, 10, 8, 8, 9, 9, 9, 9
    };
    int len = 30;

    printf("Unsortiertes Array:");
    print_array(input_array, len);

    int output_array[MAX_LAENGE];
    count_sort(input_array, len, output_array, ASCENDING);

    printf("Sortiertes Array:");
    print_array(output_array, len);
    return 0;
}

这是我尝试过的代码 显然这个问题是由于 count_array 引起的，但我不知道如何解决这个问题

int *count_array = malloc((max + 1) * sizeof(int));

我尝试像这样分配

count_array

，但没有任何效果。

Answer 1

我认为没有任何理由认为您的

count_sort()

函数会因

main()

提供的特定输入而失败。但自动判断通常会针对该函数运行多个输入，其中一些输入会执行该函数预期适应的各种隐式和显式极值。其他输入可能触发的排序函数问题至少包括：

• 输入数组具有

  int

  类型的元素，可以取负值。当元素为负数时，直接使用输入元素作为

  count_array

  的索引将导致越界访问。

• count_array

  在

  count_sort()

  中声明为尺寸为

  max + 1

  (2) 的变长数组 (1)。并非所有 C 实现都支持 VLA，即使对于那些支持 VLA 的实现，也很容易提供需要

  count_array

  对于堆栈来说太大的输入。

• 通过在输出数组（您的“PRO GAMER MOVE”）内传递计数数组的长度来保存函数

  count_sort_calculate_counts()

  的一个参数是令人困惑的，并且几乎没有价值。我没想到会从一个“真正的”专业程序员那里看到这样的事情，而且它也不会通过我的代码审查。

表达式
• max + 1

  有整数溢出的风险。

如果
• max

  非常大，那么你的程序可能运行得比实际速度慢得多。