C 中的计数排序

Question

我正在尝试用 C 语言实现计数排序算法，但它只对前 4 个元素进行排序，然后就变得疯狂了。

我使用维基百科页面 ( https://de.wikipedia.org/wiki/Countingsort ) 作为方向。

我使用外部 .txt 文件作为输入。

我尝试的 txt 文件包含以下数字:

90, 38, 42, 34, 8, 0, 77, 1, 84, 5, 25, 72, 44, 42, 90, 63, 23

结果是:

0, 1, 5, 8, 1836801184, 32767, 1343601744, 0, 0, 0, 0, 0, 1696599910, -721405914, 33, 0, 1343602158

我的代码:

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

int MAX_LAENGE = 1000;
int MAX_VALUE = 100;
int i,k,j;
void count_sort_calculate_counts(int input_array[], int len, int count_array[]) 
{
    for (i=0; i<=len;i++)
    {
        count_array[i] = 0;
    }
    for (j=0; j<sizeof(input_array);j++)
    {
        count_array[input_array[j]] = count_array[input_array[j]] + 1;
    }
}

void count_sort_write_output_array(int output_array[], int len, int count_array[]) 
{
    k=0;
    for (j=0;j<sizeof(count_array);j++)
    {
        for (i=0; i<count_array[j]; i++)
        {
            output_array[k] = j;
            k = k + 1;
        }
    }
}

int main(int argc, char *argv[]) 
{
    if (argc < 2)
    {
        printf("Aufruf: %s <Dateiname>\n", argv[0]);
        printf("Beispiel: %s zahlen.txt\n", argv[0]);
        exit(1);
    }

    char *filename = argv[1];

    int input_array[MAX_LAENGE];   
    int len = read_array_from_file(input_array, MAX_LAENGE, filename);

    printf("Unsortiertes Array:");
    print_array(input_array, len);
    int count_array[MAX_LAENGE];
    int output_array[MAX_LAENGE];
    count_sort_calculate_counts(input_array, len, count_array);
    count_sort_write_output_array(output_array, len, count_array);

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

    return 0;
}

Answer 1

我认为你的问题出在 count_sort_calculate_counts 函数中。

for (i=0; i<=len;i++)

你的意思是我

for (j=0; j<sizeof(input_array);j++)

sizeof 并没有像你想象的那样做。它肯定不会给你数组元素的数量，而是变量 input_array 的大小。