认知算法(四)

简介: 认知算法(四),一起来学习吧。

嗨,欢迎来到异星球,我是小怪同志。这篇文章主要讲认识算法,请一起学习吧。

一、基数排序

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

  1. 基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法:

这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

基数排序:根据键值的每位数字来分配桶;
计数排序:每个桶只存储单一键值;
桶排序:每个桶存储一定范围的数值;

二、代码实现

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 = a[i];
}

}

while (m / exp > 0) {

int bucket[BASE] = { 0 };

for (i = 0; i < n; i++) {
  bucket[(a[i] / exp) % BASE]++;
}

for (i = 1; i < BASE; i++) {
  bucket[i] += bucket[i - 1];
}

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("%d", &n);
n = n < MAX ? n : MAX;

printf("Enter %d Elements : ", n);
for (i = 0; i < n; i++) {

scanf("%d", &arr[i]);

}

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

radixsort(&arr[0], n);

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

return 0;
}

相关文章
|
6月前
|
机器学习/深度学习 算法 搜索推荐
【高效率学习】探索最适合你的学习之路:从心理学、动机到教育学的深度解析
【高效率学习】探索最适合你的学习之路:从心理学、动机到教育学的深度解析
148 0
【高效率学习】探索最适合你的学习之路:从心理学、动机到教育学的深度解析
|
6月前
|
安全 测试技术
认识-认知
认识-认知
101 0
|
Kubernetes 负载均衡 网络协议
K8S 的新认知与初领会
我们今天开始正式进⼊ Kubernetes 的课程学习,Kubernetes 相信各位已经听过很多次了,那么什么是 Kubernetes呢?
K8S 的新认知与初领会
|
存储 算法 搜索推荐
认知算法(三)
认知算法(三),一起来学习吧。
认知算法(三)
|
算法 搜索推荐
认知算法(十)
认知算法(十),一起来学习吧。
|
算法 JavaScript 前端开发
认知算法(九)
认知算法(九),一起来学习吧。
|
机器学习/深度学习 算法 搜索推荐
认知算法(一)
认识算法(一),一起来学习吧。
|
算法 搜索推荐 索引
认知算法(七)
认知算法(七),一起来学习吧。
|
算法 搜索推荐
认知算法(五)
认知算法(五),一起来学习吧。
|
存储 算法 搜索推荐
认知算法(六)
认知算法(六),一起来学习吧。