北京外贸网站开发,凡客诚品老板,杭州哪家网站建设好,电商平台建设实施方案基数排序
属于分配式排序,又称桶子法,通过键值的各个位上的值,将要排序的元素分配至某些桶中,达到排序的作用.
基数排序属于稳定性排序,是效率高的稳定性排序法
是桶排序的扩展,将整数按照位数进行切割,再按各个位数进行比较
是用空间换时间的经典算法
在使用8kw个数据进行…基数排序
属于分配式排序,又称桶子法,通过键值的各个位上的值,将要排序的元素分配至某些桶中,达到排序的作用.
基数排序属于稳定性排序,是效率高的稳定性排序法
是桶排序的扩展,将整数按照位数进行切割,再按各个位数进行比较
是用空间换时间的经典算法
在使用8kw个数据进行测试时
需要8kw*11个数组 *4个字节 /1024k/1024m/1024g 3.3G
不难看出基数排序对空间的要求非常高
排序思路
eg:{53,3,542,748,14,214}
第一轮:
1,取出每个元素的个位数
2,判断这个数应该放在对应的哪一个桶
3,按照桶的顺序依次放回原数组
//个位小的在放回去后会在前面
第二轮:
1,取出每个元素的十位数
2,判断这个数应该放在哪一个桶,如果没有十位则补零
3,按照桶顺序依次放回原数组
//十位小的在放回去后会在前面
…
//此时在依次放入桶中时,最高位相同的数,十位小的会被先放入
直到最高位放入桶中
此时再按最高位放入队列
记录每个桶中放置了多少数据
代码实现
定义一个二维数组,表示10个桶,每个桶为一个一维数组
定义一个10个元素的一维数组用以保存从0-9的桶中数量
按位循环遍历数组中每个元素直到遍历到最高位结束
public void bucketsort(int[] arr) {int[][] arr1 new int[10][arr.length];int max arr[0];for (int i 0; i arr.length; i) {max Math.max(max, arr[i]);}for (int i 0; i Integer.toString(max).length(); i) {int[] count new int[10];for (int i1 0; i1 arr.length; i1) {int temp arr[i1] / (int) (Math.pow(10, i)) % 10;arr1[temp][count[temp]] arr[i1];count[temp];}int t 0;for (int i1 0; i1 10; i1) {for (int k 0; k count[i1]; k) {arr[t] arr1[i1][k];t;}}}
}总结
并不复杂的思路,典型的空间换时间算法
