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

ing 发表于 2020-3-30 00:00

本帖最后由 ing 于 2020-3-31 17:05 编辑

我不理解这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);
   }
}

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

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

   // 最大值 m ÷ exp 得到运行次数，exp:1 每次乘10
   // m:99，99/1>0，99/10>0，99/100=0
   while (m / exp > 0) {
            int bucket = { 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 / exp) % BASE]++;
            }

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

            //目的???
            //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 / exp) % BASE]] = a;
            }

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

            exp *= BASE;

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

int main() {
   int arr;
   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);
   }

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

   radixsort(&arr, n);

   return 0;
}
```

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

JuncoJet 发表于 2020-3-30 00:18

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

KamiMao 发表于 2020-3-30 01:47

dandaodaodan 发表于 2020-3-30 02:21

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

无名氏wyw 发表于 2020-3-30 07:59

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

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

页: [1]

吾爱破解 - 52pojie.cn's Archiver

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