汉扬编程 C语言入门 「图解数据结构」五分钟彻底理解桶排序

「图解数据结构」五分钟彻底理解桶排序

「图解数据结构」五分钟彻底理解桶排序

桶排序

「图解数据结构」五分钟彻底理解桶排序

桶排序(Bucket sort)是一种基于计数的排序算法(计数排序可参考上节的内容),工作的原理是将数据分到有限数量的桶子里,然后每个桶再分别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)

「图解数据结构」五分钟彻底理解桶排序

算法步骤

「图解数据结构」五分钟彻底理解桶排序

设置固定数量的空桶。把数据放到对应的桶中。对每个不为空的桶中数据进行排序。拼接不为空的桶中数据,得到结果。算法演示

「图解数据结构」五分钟彻底理解桶排序

动画演示GIF加载有点慢,请稍等片刻^_^

排序动画过程解释

首先,设置固定数量的空桶,在这里为了方便演示,设置桶的数量为 5 个空桶遍历整个数列,找到最大值为 56 ,最小值为 2 ,每个桶的范围为 ( 56 – 2 + 1 )/ 5 = 11再次遍历整个数列,按照公式 floor((数字 – 最小值) / 11) 将数字放到对应的桶中比如,数字 7 代入公式 floor((7 – 2) / 11) = 0 放入 0 号桶数字 12 代入公式 floor((12 – 2) / 11) = 0 放入 0 号桶数字 56 代入公式 floor((56 – 2) / 11) = 4 放入 4 号桶当向同一个索引的桶,第二次插入数据时,判断桶中已存在的数字与新插入数字的大小,按照左到右,从小到大的顺序插入(可以使用前面讲解的插入排序)实现比如,插入数字 19 时, 1 号桶中已经有数字 23 ,在这里使用插入排序,让 19 排在 23 前面遍历完整个数列后,合并非空的桶,按从左到右的顺序合并0,1,2,3,4桶。这样就完成了 桶排序代码实现

为了更好的让读者用自己熟悉的编程语言来理解动画,笔者将贴出多种编程语言的参考代码,代码全部来源于网上。

C++代码实现

Java代码实现

JavaScript代码实现

c语言归并排序,基数排序

  void merge(int *a, int low, int center, int high){
int m,n,i,j,k;
int *L,*R;
if(low >= high) return;
m = center – low 1;
n = high – center;
L = (int *)malloc(m * sizeof(int));
R = (int *)malloc(n * sizeof(int));
for(i=0; i R[j])
a[k] = R[j ];
else
a[k] = L[i ];
}
while(i while(j}
void m_sort(int *a, int low, int high){
int center;
if(low center = (low high)/2;
m_sort(a, low, center);
m_sort(a, center 1, high);
merge(a, low, center, high);
}
}
int main(){
int i;
int a[] = {23, 2, 45, 78, 1, 99, 3,65,43,55};
m_sort(a, 0, 6);
for(i=0; i printf(\”%d \”,a[i]);
}
return 0;
}。
  

本文来自网络,不代表汉扬编程立场,转载请注明出处:http://www.hyzlch.com/cjia/6457.html

C语言中的字符串处理库函数介绍与实现

RedHatLinux新手入门教程有何特点?

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

返回顶部