排序算法是一种按特定顺序排列列表组件的算法。最常用的顺序是数字顺序和字典顺序。
基数排序是一种非比较排序算法。基数排序算法是未排序列表的首选算法。
它通过最初对相同位值的各个数字进行分组来对元素进行排序。基数排序的思想是按照递增/递减顺序从最低有效数字（LSD）到最高有效数字（MSD）进行逐位排序。基数排序是一种小方法，在按字母顺序排列超大名称列表时会多次使用。具体来说，名称列表最初是根据每个名称的首字母进行排序的，即名称被组织为二十六个类别。
让我们回顾一下下面的插图，以便清楚地了解工作原理基数排序算法。显然，传递/迭代的次数取决于最高个体数字的大小。
在上面的示例中，输入的是主列。其余列显示对越来越重要的数字位置进行连续排序后的列表。
基数排序的复杂性分析 O(m.n)。
但是，如果我们看一下这两个值，键的大小与键的数量相比相对较小。举个例子，如果我们有六位数字的密钥，我们可能有 1,000,000 条完全不同的记录。
在这里，我们往往会看到密钥的大小并不重要，并且该算法是线性质量 O(n)
算法
Radix_sort (list, n)shift = 1for loop = 1 to keysize do for entry = 1 to n do bucketnumber = (list[entry].key / shift) mod 10 append (bucket[bucketnumber], list[entry])list = combinebuckets()shift = shift * 10
示例
这是一个实现基数排序的 C 程序。
现场演示
#includeint get_max (int a[], int n){ int max = a[0]; for (int i = 1; i max) max = a[i]; return max;}void radix_sort (int a[], int n){ int bucket[10][10], bucket_cnt[10]; int i, j, k, r, NOP = 0, divisor = 1, lar, pass; lar = get_max (a, n); while (lar > 0){ NOP++; lar /= 10; } for (pass = 0; pass < NOP; pass++){ for (i = 0; i < 10; i++){ bucket_cnt[i] = 0; } for (i = 0; i < n; i++){ r = (a[i] / divisor) % 10; bucket[r][bucket_cnt[r]] = a[i]; bucket_cnt[r] += 1; } i = 0; for (k = 0; k < 10; k++){ for (j = 0; j < bucket_cnt[k]; j++){ a[i] = bucket[k][j]; i++; } } divisor *= 10; printf ("After pass %d : ", pass + 1); for (i = 0; i < n; i++) printf ("%d ", a[i]); printf (""); }}int main (){ int i, n, a[10]; printf ("Enter the number of items to be sorted: "); scanf ("%d", &n); printf ("Enter items: "); for (i = 0; i < n; i++){ scanf ("%d", &a[i]); } radix_sort (a, n); printf ("Sorted items : "); for (i = 0; i < n; i++) printf ("%d ", a[i]); printf ("
"); return 0;}
输出
Enter number of items to be sorted 6Enter items:567 789 121 212 563 562After pass 1 : 121 212 562 563 567 789After pass 2 : 212 121 562 563 567 789After pass 3 : 121 212 562 563 567 789Sorted items : 121 212 562 563 567 789
以上就是基数排序的C程序的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444298.html
微信扫一扫 
支付宝扫一扫 
