C及C++语言桶排序算法 C及C++语言八大排序算法之桶排序全过程示例详解
xr415 人气:0想了解C及C++语言八大排序算法之桶排序全过程示例详解的相关内容吗,xr415在本文为您仔细讲解C及C++语言桶排序算法的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C及C++八大排序算法,C及C++桶排序算法,下面大家一起来学习吧。
基本思路是将所有数的个位十位百位一直到最大数的最高位一步步装桶,先个位装桶然后出桶,直到最高位入桶出桶完毕。
首先我们要求出一个数组的最大数然后求出他的最大位数
//求最大位数的函数 int getmaxweisu(int* a,int len)// { int max = a[0]; for (int i = 0; i < len; i++) { if (max < a[i]) { max = a[i]; } } int count = 1; while (max/10) { count++; max /= 10; } return count; }
其次我们先按各位装桶然依次递推下
void buckle_sort(int* a, int len,int div)//div表示取位数的余数 { //要申请一个二维10*10的数组区保存数字 int bucket[10][10]; for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) { bucket[i][j] = -1; //随便什么数字只要不要与排序数字有相同就可以 } } int temp = 1; for (int i=1; i < div; i++) { temp = temp * 10;//求出第几位余数 } for (int i = 0; i < len; i++) { int k = (a[i]/temp) % 10;//求第几位的余数 for (int j = 0; j < 10; j++) { if (bucket[k][j] == -1) { bucket[k][j] = a[i]; break; } } } //出桶 int k = 0; for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { if (bucket[i][j] != -1) { a[k] = bucket[i][j]; k++;//去遍历桶 让桶的所有数字都出来 bucket[i][j] = -1; } } } }
最后通过最大的数的位数来表示要进行几次入桶和出桶
void Bucket_Sort(int* a, int len) { int n=getmaxweisu(a, len); for (int m = 1; m <= n; m++) { buckle_sort(a, len,m); } }
int a[10] = { 1,5,7,21,259,4,11,61,17,98 };代码演示全过程
第一次出桶后a数组的顺序1 ,21,11 ,61, 4, 5, 7, 17 ,98, 259
第二次入桶过程
出桶后a数组为1,4,5,7,11,17,21,259,61,98
说明:如果取余为没有那么他就是为0 的
最后一次出桶后就排序好了
a数组就为1,4,5,7,11,17,21,61,98,259
加载全部内容