0
0

排序算法之非比较排序（基数排序和计数排序）

**个人主页：欢迎大家光临——>**沙漠下的胡杨

** 各位大帅哥，大漂亮**

如果觉得文章对自己有帮助

可以一键三连支持博主

** 你的每一分关心都是我坚持的动力**

** **

☄：本期重点：

** 希望大家每天都心情愉悦的学习工作。**

在我们之前的讲解中，我们学到了大多数的比较排序，今天我们主要学一下非比较排序。

计数排序：

  1.     计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 当然这是一种牺牲空间换取时间的做法，而且O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）

排序思想：

1. 确定开辟的空间大小（一般为数据中的最大值 - 最小值的差值）。、

2. 确定对应关系。

3. 把数据对应关系的数组下标自增。

4. 根据队形关系拷贝数据。

计数排序图示分析：

首先我们有原数组，还要开辟一个辅助数组。并且辅助数组的大小是根据原数组中的数据的最大值—最小值决定的。下面数组中的值都在 1 到 8之间，所以我们辅助数组开辟 8 个大小的空间，其中 原数组中 1 对应辅助数组中下标 0 的位置，原数组中 8 数据，对应辅助数组下标为 7 的位置，刚开始时我们把辅助数据都为内存设置为0。

下面我们把数据根据对应关系写入辅助数组中去，1对应位置就是数组下标为0的位置，然后把辅助数组内的数据自增。8 对应下标为 7 的位置，然后把辅助数组内的数组自增。

写入完成后，我们根据辅助数组和原数组的对应关系，一个个的在写入原数组，其中辅助数组 0 下标对应的是 1 ，然后 0 下标的数据 2 表示写入两次 。同理，下标为辅助数组 7 下标对相应的是 8 ，辅助数组下标为 7 的数据为 2 ，表示写入 2 次 8。

代码实现：

  1. void CountSort(int* a, int n)//计数排序
  2. {
  3.     //获取最大值和最小值
  4.     int max = a[0];
  5.     int min = a[0];
  7.     for (int i = 0; i < n; i++)
  8.     {
  9.         if (max < a[i])
  10.         {
  11.             max = a[i];
  12.         }
  14.         if (min > a[i])
  15.         {
  16.             min = a[i];
  17.         }
  18.     }
  20.     //获取开辟的区间大小
  21.     int rang = max - min + 1;
  22.     
  23.     //开辟空间
  24.     int* count = (int*)malloc(sizeof(int)*rang);
  25.     if (count == NULL)
  26.     {
  27.         perror("malloc fail");
  28.         exit(-1);
  29.     }
  31.     //把辅助数组的区间设置为0。
  32.     memset(count, 0, sizeof(int)*rang);
  34.     //根据对应关系写入辅助数组
  35.     for (int i = 0; i < n; i++)
  36.     {
  37.         //写入时，根据对应关系一定是下标原数组数据减去最小值。
  38.         count[a[i] - min]++;
  39.     }
  41.     //根据对应关系写回原数组
  42.     int j = 0;
  44.     //判断区间为是否结束
  45.     for (int i = 0; i < rang; i++)
  46.     {
  47.         //此时判断的是辅助数组的数据是否为0
  48.         while (count[i]--)
  49.         {
  50.             a[j++] = i + min;
  51.         }
  52.     }
  54.     //释放空间
  55.     free(count);
  56.     count = NULL;
  57. }

基数排序：

基数排序算法思想：

** 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，将要排序的元素分配至某些“桶”中，以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。**

奇数排序实现流程：

1. 我们首先明确基数，一般是0~9这10个数字为基数。

2. 选取最大数的位数作为排序的次数。

3.然后根据个位上的数据排序，拷贝回原数组，再根据十位上的数据排序，拷贝回原数组（不足的位数补0，比如 2 ，2不到10，所以十位为 0 ）

4.一直拷贝到最大数的最高位数停止，此时数据已经有序。

基数排序图示：

下面是一些随机数，然后我们排序，首先我们确定基数是 0~9 。然后我们确定最大数的最高位次是3，表示排序 3 次 。

下面我们按照个位上的数进行分配数据。

然后在进行回收数据，先放的数据先取出（先进先出）：

根据十位上的数据分发数据：

回收十位上排序好的数据：

根据百位上的数据分发：

在回收百位上排序好的数据：

因为最大的数只有百位，所以此时排序完成。

代码实现（用队列辅助实现）：

  1. //最大数据的位数，在数据量较小时，我们可以看出所以直接定义了最大的位数
  2. #define K 3
  4. //定义全局的10个队列，对应基数为0 ~ 9
  5. Queue q0,q1, q2, q3, q4, q5, q6, q7, q8, q9;
  7. //获取该数据第几位的数字
  8. int GetKey(int val, int k)
  9. {
  10.     int keyi = 0;
  11.     while (k >= 0)
  12.     {
  13.         keyi = val % 10;
  14.         val /= 10;
  15.         k--;
  16.     }
  18.     return keyi;
  19. }
  21. //分发数据
  22. void Distribute(int* a, int left, int right, int k)
  23. {
  24.     for (int i = left; i < right; i++)
  25.     {
  26.         //获取当前要排序的位上的数据。
  27.         int key = GetKey(a[i], k);
  29.         //按照数据的每个位上的数字，分别进入对应的队列
  30.         switch (key)
  31.         {
  32.         case 0:
  33.             QueuePush(&q0, a[i]);
  34.             break;
  35.         case 1:
  36.             QueuePush(&q1, a[i]);
  37.             break;
  38.         case 2:
  39.             QueuePush(&q2, a[i]);
  40.             break;
  41.         case 3:
  42.             QueuePush(&q3, a[i]);
  43.             break;
  44.         case 4:
  45.             QueuePush(&q4, a[i]);
  46.             break;
  47.         case 5:
  48.             QueuePush(&q5, a[i]);
  49.             break;
  50.         case 6:
  51.             QueuePush(&q6, a[i]);
  52.             break;
  53.         case 7:
  54.             QueuePush(&q7, a[i]);
  55.             break;
  56.         case 8:
  57.             QueuePush(&q8, a[i]);
  58.             break;
  59.         case 9:
  60.             QueuePush(&q9, a[i]);
  61.             break;
  62.         default:
  63.             break;
  64.         }
  65.     }
  66. }
  68. //回收数据
  69. void Collect(int* a)
  70. {
  71.     //下标值
  72.     int i = 0;
  74.     //依次取出0到9队列中的数据
  75.     while (!QueueEmpty(&q0))
  76.     {
  77.         a[i++] = QueueFront(&q0);
  78.         QueuePop(&q0);
  79.     }
  80.     while (!QueueEmpty(&q1))
  81.     {
  82.         a[i++] = QueueFront(&q1);
  83.         QueuePop(&q1);
  84.     }
  85.     while (!QueueEmpty(&q2))
  86.     {
  87.         a[i++] = QueueFront(&q2);
  88.         QueuePop(&q2);
  89.     }
  90.     while (!QueueEmpty(&q3))
  91.     {
  92.         a[i++] = QueueFront(&q3);
  93.         QueuePop(&q3);
  94.     }
  95.     while (!QueueEmpty(&q4))
  96.     {
  97.         a[i++] = QueueFront(&q4);
  98.         QueuePop(&q4);
  99.     }
  100.     while (!QueueEmpty(&q5))
  101.     {
  102.         a[i++] = QueueFront(&q5);
  103.         QueuePop(&q5);
  104.     }
  105.     while (!QueueEmpty(&q6))
  106.     {
  107.         a[i++] = QueueFront(&q6);
  108.         QueuePop(&q6);
  109.     }
  110.     while (!QueueEmpty(&q7))
  111.     {
  112.         a[i++] = QueueFront(&q7);
  113.         QueuePop(&q7);
  114.     }
  115.     while (!QueueEmpty(&q8))
  116.     {
  117.         a[i++] = QueueFront(&q8);
  118.         QueuePop(&q8);
  119.     }
  120.     while (!QueueEmpty(&q9))
  121.     {
  122.         a[i++] = QueueFront(&q9);
  123.         QueuePop(&q9);
  124.     }
  125.     
  126. }
  129. void RadixSort(int* a, int left, int right)
  130. {
  131.     //初始化队列
  132.     QueueInit(&q0);
  133.     QueueInit(&q1);
  134.     QueueInit(&q2);
  135.     QueueInit(&q3);
  136.     QueueInit(&q4);
  137.     QueueInit(&q5);
  138.     QueueInit(&q6);
  139.     QueueInit(&q7);
  140.     QueueInit(&q8);
  141.     QueueInit(&q9);
  143.     for (int i = 0; i < K; i++)
  144.     {
  145.         //分发数据
  146.         Distribute(a, left, right, i);
  147.         
  148.         //回收数据
  149.         Collect(a);
  150.     }
  152.     //销毁队列
  153.     QueueDestroy(&q0);
  154.     QueueDestroy(&q1);
  155.     QueueDestroy(&q2);
  156.     QueueDestroy(&q3);
  157.     QueueDestroy(&q4);
  158.     QueueDestroy(&q5);
  159.     QueueDestroy(&q6);
  160.     QueueDestroy(&q7);
  161.     QueueDestroy(&q8);
  162.     QueueDestroy(&q9);
  164. }

因为我们使用纯C来写的，所以在一些代码上比较麻烦，需要注意一下几点：

1 . 队列要定义为全局的，方便我们直接使用，否则作为参数传递太过麻烦。

2. 我们可以直接写入要排的数据的最大位数，也可以写入的位数大一点，比如最大值只有百位的数据，我们可以写入千位，也就是比预定的要多排序一次，只会影响效率，不会影响结果。

3.使用队列的好处是我们不用考虑数据先进先出这点啦，因为这是队列的性质。

4.我们需要先写好一个队列才能使用上面的方法。

上述的写法十分麻烦，下面我们使用数组方式实现。

代码实现（数组实现）：

  1. //求数据的最大值
  2. int GetMaxBitCount(int* array, int size)
  3. {
  4.     //设定位数初始值
  5.     int max_count = 1;
  6.     
  7.     //设定初始边界值
  8.     int bound = 10;
  9.     
  10.     // 针对数组中的每一个元素, 都使用边界值来进行试探.
  11.     // 看看边界值是否能够涵盖数组中的当前值.
  12.     int i = 0;
  13.     for (; i < size; ++i) 
  14.     {
  15.         while (array[i] >= bound) 
  16.         {
  17.             ++max_count;
  18.             bound *= 10;
  19.         }
  20.     }
  22.     //返回数据中最大的位数
  23.     return max_count;
  24. }
  26. void RadixSort1(int* array, int size) {
  27.     // 1. 求出最大的数字是多少位
  28.     int max_bit_count = GetMaxBitCount(array, size);
  29.     //开辟临时数组
  30.     int* bucket = (int*)malloc(sizeof(int)* size);
  32.     // 2. 最大的数字有多少位, 就需要进行多少次的排序
  33.     int radix = 1;  // 表示当前要取个位, 十位, 还是百位...
  34.     int count = 0;
  35.     for (; count < max_bit_count; ++count, radix *= 10) 
  36.     {
  37.         // 统计每个桶中的元素个数（基数桶）
  38.         int bucket_count[10] = { 0 };
  39.         int i = 0;
  40.         for (; i < size; ++i) 
  41.         {
  42.             ++bucket_count[array[i] / radix % 10];
  43.         }
  44.         // 根据每个桶的元素的个数, 分配起始位置.（辅助数组）
  45.         // 一维数组表示二维数组
  46.         int start_addr[10] = { 0 };
  47.         for (i = 1; i < 10; ++i) 
  48.         {
  49.             start_addr[i] = start_addr[i - 1] + bucket_count[i - 1];
  50.         }
  51.         // 代码运行到这里, 就已经把地盘瓜分好了.
  52.         // 接下来将所有的元素放到桶中
  53.         for (i = 0; i < size; ++i) 
  54.         {
  55.             int bucket_no = array[i] / radix % 10;
  56.             // 这里的 start_addr[bucket_no]++ 相当于线性表的尾插.
  57.             // 通过 start_addr[bucket_no] 记录每个桶当前写到了哪个位置.
  58.             bucket[start_addr[bucket_no]++] = array[i];
  59.         }
  60.         memcpy(array, bucket, sizeof(int)* size);
  61.     }
  62. }

使用数组方式更为简洁，但是理解上更为麻烦些：

1.我们先试探边界求出最大数的位数。

2.在根据每次个位或者十位等等，这些位上的数据放入一个基数桶中。

3.最后我们要按照0~9这样的顺序插入到临时数组中

4.在插入时我们要根据辅助数组的顺序依次插入，这个类似一维数组表示二维数组的形式。

5.最后拷贝回原数组，释放空间。

**今天到这里就结束啦！ **

标签： 数据结构 算法 排序算法
本文转载自: https://blog.csdn.net/m0_64770095/article/details/125648259
版权归原作者 沙漠下的胡杨 所有， 如有侵权，请联系我们删除。
登录后发布评论

“排序算法之非比较排序（基数排序和计数排序）”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？