0

我正在尝试在 C 中为整数实现基数排序，但遇到了一个似乎无法修复的循环错误。这是代码和输出。我不知道错误的确切部分，所以请原谅帖子的长度。

有人可以指出我的错误吗？

#include <stdio.h>
#define BINS 16
#define GROUP 4

int main(int argc, const char *argv[])
{
    int mask = 0xf;
    int i, j;
    int list[] = {0x65c6, 0xbeb, 0x96ba, 0x9a7d};
    int buffer[GROUP];
    int *temp, *src_ptr, *dest_ptr;
    int cnt[BINS];
    int map[BINS];
    map[0] = 0;

    //init pointers to the list of unsorted numbers and temp buffer
    src_ptr = list;
    dest_ptr = buffer;

    //print unsorted list
    putchar('\n');
    printf("unsorted list: \n");
    for(i = 0; i < GROUP; i++) 
        printf("int: %d hex: 0x%x ", src_ptr[i], src_ptr[i]);
    putchar('\n');

    j = 0;
    while(j < GROUP)
    {
        //initalize the count
        for(i = 0; i < BINS; i++)
            cnt[i] = 0;
        
        //count significant digits. shifting i * group # of times
        for(i = 0; i < GROUP; i++)
            cnt[(src_ptr[i] >> i*GROUP) & mask]++;

        //initalize the map
        map[0] = 0;
        for(i = 0; i < BINS; i++)
            map[i] = 0;

        //compute the map
        for(i = 1; i < BINS; i++)
        {
            map[i] = (map[i - 1] + cnt[i - 1]);
        }

        //shift the elements in buffer[] and list[] via their pointers. 
        //shifting i * group # of times
        for(i = 0; i < GROUP; i++)
        {
            dest_ptr[map[(src_ptr[i] >> i*GROUP) & mask]++] = src_ptr[i];
        }

        //perform a swap of list[] and buffer[] via their pointers
        temp = src_ptr;
        src_ptr = dest_ptr;
        dest_ptr = src_ptr;
    
        j++;
    }

    //print list for reference
    putchar('\n');
    printf("sorted list: \n");
    for(i = 0; i < GROUP; i++) 
        printf("int: %d hex: 0x%x ", src_ptr[i], src_ptr[i]);
    putchar('\n');
    
    //print buffer for reference
    putchar('\n');
    printf("sorted buffer: \n");
    for(i = 0; i < GROUP; i++) 
        printf("int: %d hex: 0x%x ", dest_ptr[i], dest_ptr[i]);
    putchar('\n');

    return 0;
}

输出：

未排序的原始列表： 整数：26054 十六进制：0x65c6 整数：3051 十六进制：0xbeb 整数：38586 十六进制：0x96ba 整数：39549 十六进制：0x9a7d

排序列表： 整数：3051 十六进制：0xbeb 整数：3051 十六进制：0xbeb 整数：3051 十六进制：0xbeb 整数：3051 十六进制：0xbeb

排序缓冲区：int：3051 hex：0xbeb int：3051 hex：0xbeb int：3051 hex：0xbeb int：3051 hex：0xbeb

4

1 回答 1

2

代码中有两个问题：

  1. 你的交换代码：temp = src_ptr; src_ptr = dest_ptr; dest_ptr = src_ptr;应该引用temp两次（我的编译器告诉我你做错了，因为它说“ error: variable ‘temp’ set but not used [-Werror=unused-but-set-variable]”）。你需要让你的编译器产生类似的警告，然后注意它们。交换代码应该是：temp = src_ptr; src_ptr = dest_ptr; dest_ptr = temp;当然。这是必要的改变；这还不够。

    我希望我的代码能够在以下条件下干净地编译：

    gcc -g -O3 -std=c11 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes -Wold-style-definition -Wold-style-declaration -Werror  radixsort.c -o radixsort

  2. j你在换档时没有正确使用。你有：

    cnt[(src_ptr[i] >> i*GROUP) & mask]++;
dest_ptr[map[(src_ptr[i] >> i*GROUP) & mask]++] = src_ptr[i];

    你需要：

    cnt[(src_ptr[i] >> j*GROUP) & mask]++;
dest_ptr[map[(src_ptr[i] >> j*GROUP) & mask]++] = src_ptr[i];

此代码似乎正确排序：

#include <stdio.h>

enum { BINS  = 16  };
enum { GROUP = 4   };
enum { MASK  = 0xF };

static void dump_array(char const *tag, size_t n, int a[n])
{
    printf("%s:\n", tag);
    for (size_t i = 0; i < n; i++)
        printf("int: %5d hex: 0x%.4X\n", a[i], a[i]);
}

int main(void)
{
    int i, j;
    int list[] = {0x65C6, 0x0BEB, 0x96BA, 0x9A7D};
    int buffer[GROUP];
    int *temp, *src_ptr, *dest_ptr;
    int cnt[BINS];
    int map[BINS];
    map[0] = 0;

    // init pointers to the list of unsorted numbers and temp buffer
    src_ptr = list;
    dest_ptr = buffer;

    // print unsorted list
    dump_array("unsorted list", GROUP, src_ptr);

    j = 0;
    while (j < GROUP)
    {
        // initalize the count
        for (i = 0; i < BINS; i++)
            cnt[i] = 0;

        // count significant digits. shifting i * group # of times
        for (i = 0; i < GROUP; i++)
            cnt[(src_ptr[i] >> j*GROUP) & MASK]++;

        // initalize the map
        map[0] = 0;
        for (i = 0; i < BINS; i++)
            map[i] = 0;

        // compute the map
        for (i = 1; i < BINS; i++)
        {
            map[i] = (map[i - 1] + cnt[i - 1]);
        }

        // shift the elements in buffer[] and list[] via their pointers.
        // shifting i * group # of times
        for (i = 0; i < GROUP; i++)
        {
            dest_ptr[map[(src_ptr[i] >> j*GROUP) & MASK]++] = src_ptr[i];
        }

        // perform a swap of list[] and buffer[] via their pointers
        temp = src_ptr;
        src_ptr = dest_ptr;
        dest_ptr = temp;
        j++;
    }

    // print list for reference
    dump_array("sorted list", GROUP, src_ptr);

    // print buffer for reference
    dump_array("sorted buffer", GROUP, dest_ptr);

    return 0;
}

样本输出：

unsorted list:
int: 26054 hex: 0x65C6
int:  3051 hex: 0x0BEB
int: 38586 hex: 0x96BA
int: 39549 hex: 0x9A7D
sorted list:
int:  3051 hex: 0x0BEB
int: 26054 hex: 0x65C6
int: 38586 hex: 0x96BA
int: 39549 hex: 0x9A7D
sorted buffer:
int: 26054 hex: 0x65C6
int: 38586 hex: 0x96BA
int: 39549 hex: 0x9A7D
int:  3051 hex: 0x0BEB

广义代码

上面的代码GROUP用于两个不同的目的。一个是要排序（和打印）的列表的长度。一个是用于进行基数排序的数字组数。下面的代码被概括为将列表大小与基数组分开。它还清理了一些未在原始代码中修复的注释等。

#include <stdio.h>

enum { BINS  = 16  };
enum { GROUP = 4   };
enum { MASK  = 0xF };

static void dump_array(char const *tag, size_t n, int a[n])
{
    printf("%s:\n", tag);
    for (size_t i = 0; i < n; i++)
        printf("int: %5d hex: 0x%.4X\n", a[i], a[i]);
}

int main(void)
{
    int list[] = {0x65C6, 0x0BEB, 0x96BA, 0x9A7D, 0x2917, 0x8A2C, 0xDEAD, 0xBEEF, 0xFACE };
    enum { LIST_SIZE = sizeof(list) / sizeof(list[0]) };
    int buffer[LIST_SIZE];
    int cnt[BINS];
    int map[BINS];

    // init pointers to the list of unsorted numbers and temp buffer
    int *src_ptr = list;
    int *dst_ptr = buffer;

    // print unsorted list
    dump_array("unsorted list", LIST_SIZE, src_ptr);

    for (int j = 0; j < GROUP; j++)
    {
        // initalize the count
        for (int i = 0; i < BINS; i++)
            cnt[i] = 0;

        // count significant digits. shifting j * group # of times
        for (int i = 0; i < LIST_SIZE; i++)
            cnt[(src_ptr[i] >> j*GROUP) & MASK]++;

        // initalize the map
        for (int i = 0; i < BINS; i++)
            map[i] = 0;

        // compute the map
        for (int i = 1; i < BINS; i++)
            map[i] = (map[i - 1] + cnt[i - 1]);

        // shift the elements in buffer[] and list[] via their pointers.
        // shifting j * group # of times
        for (int i = 0; i < LIST_SIZE; i++)
            dst_ptr[map[(src_ptr[i] >> j*GROUP) & MASK]++] = src_ptr[i];

        // perform a swap of list[] and buffer[] via their pointers
        int *tmp_ptr = src_ptr;
        src_ptr = dst_ptr;
        dst_ptr = tmp_ptr;
    }

    // print list for reference
    dump_array("sorted list", LIST_SIZE, src_ptr);

    // print buffer for reference
    dump_array("sorted buffer", LIST_SIZE, dst_ptr);

    return 0;
}

此代码现在假定整数值都在 0x0000..0xFFFF 范围内（每个 4 位的 4 个 nybbles，或 16 位数字）。

样本输出：

unsorted list:
int: 26054 hex: 0x65C6
int:  3051 hex: 0x0BEB
int: 38586 hex: 0x96BA
int: 39549 hex: 0x9A7D
int: 10519 hex: 0x2917
int: 35372 hex: 0x8A2C
int: 57005 hex: 0xDEAD
int: 48879 hex: 0xBEEF
int: 64206 hex: 0xFACE
sorted list:
int:  3051 hex: 0x0BEB
int: 10519 hex: 0x2917
int: 26054 hex: 0x65C6
int: 35372 hex: 0x8A2C
int: 38586 hex: 0x96BA
int: 39549 hex: 0x9A7D
int: 48879 hex: 0xBEEF
int: 57005 hex: 0xDEAD
int: 64206 hex: 0xFACE
sorted buffer:
int: 26054 hex: 0x65C6
int: 38586 hex: 0x96BA
int: 10519 hex: 0x2917
int: 35372 hex: 0x8A2C
int: 39549 hex: 0x9A7D
int: 64206 hex: 0xFACE
int:  3051 hex: 0x0BEB
int: 57005 hex: 0xDEAD
int: 48879 hex: 0xBEEF
于 2013-10-19T21:23:08.370 回答