C 基数排序(实现来自维基)

ing

我不理解这2个for循环，我只知道功能但不懂它的实现思想

#include<stdio.h>
#define MAX 20
#define SHOWPASS
#define BASE 10

void print(int *a, int n) {
        int i;
        for (i = 0; i < n; i++) {
                printf("%d\t", a[i]);
        }
}

void radixsort(int *a, int n) {
        int i, b[MAX], m = a[0], exp = 1;

        //找出最大值
        for (i = 1; i < n; i++) {
                if (a[i] > m) {
                        //令 m 为最大值
                        m = a[i];
                }
        }

        // 最大值 m ÷ exp 得到运行次数，exp:1 每次乘10
        // m:99，99/1>0，99/10>0，99/100=0
        while (m / exp > 0) {
                int bucket[BASE] = { 0 };

                //执行while第一次，for 执行结束后，将标出所有相同个位的总数在buctet中
                //a{50,123,543,187,49,30,0,2,11,100}；        bucket{4,1,1,2,0,0,0,1,0,1}  
                for (i = 0; i < n; i++) {
                        bucket[(a[i] / exp) % BASE]++;
                }

                //目的???
                //bucket{4,5,6,8,8,8,8,9,9,10}  
                for (i = 1; i < BASE; i++) {
                        bucket[i] += bucket[i - 1];
                }

                //目的???
                //bucket{0,4,5,6,8,8,8,8,9,9}  
                //执行while第一次，按个位进行分配 b{50,30,0,100,11,2,123,543,187,49}
                for (i = n - 1; i >= 0; i--) {
                        b[--bucket[(a[i] / exp) % BASE]] = a[i];
                }

                //保存每次基数排序的结果
                for (i = 0; i < n; i++) {
                        a[i] = b[i];
                }

                exp *= BASE;

#ifdef SHOWPASS
                printf("\nPASS   : ");
                print(a, n);
#endif
        }
}

int main() {
        int arr[MAX];
        int i, n;

        printf("Enter total elements (n <= %d) : ", MAX);
        scanf_s("%d", &n);
        n = n < MAX ? n : MAX;

        printf("Enter %d Elements : ", n);
        for (i = 0; i < n; i++) {
                scanf_s("%d", &arr[i]);
        }

        printf("\nARRAY  : ");
        print(&arr[0], n);

        radixsort(&arr[0], n);

        return 0;
}

调试数据
50
123
543
187
49
30
0
2
11
100

JuncoJet

不懂算法，不过百度了下，看上去像二叉树
如果只是要实现排序，直接用 std::set 偷懒
如果要实现算法，我就帮不了你了，没空造轮子

dandaodaodan

腻害,, 还没看到这里来..

无名氏wyw

基数排序简单点来说就是把数字的每一位进行一次桶排序

效率奇低，建议看看就好，真要用还是快排爽