标签:radixsort

基数排序RadixSort与桶排序BucketSort

发表于3年前(Dec 24, 2014 10:21:45 AM)  阅读 740  评论 0

分类: Java 算法 排序

标签: bucketsort radixsort 基数排序 桶排序

基数排序:对于十进制数字来说,将要排序的数字对齐排成一列,我们可以从低位起,假设目标数组元素不超过3位,第一次我们把这列数字按个位数排序,在这基础上第二次我们把这些数字再按十位数排序,第三次按百位数排序,三趟下来得到的数组就是已排序的数组。在对个位数排序时,我们可以采用下面的方法,用10个标志为0..9的桶,桶0放入所有个位数为0的数,桶1放入所有个位数为1的数,最后将所有桶的数从桶0开始输出,这样得到的数组就是按个位数排序的数组。然后,其余高位数类似处理。

桶排序:其实基数排序已经用到了桶排序的思想。桶排序假设输入数组符合均匀发布,假设n个元素都是均匀而独立的分布在区间[0,1)上, 然后将区间[0,1)划分为n个相同大小的子区间,这些子区间就是桶,然后对桶中的元素进行排序(一般使用插入排序),最后输出桶中的元素,得到排序数组。桶排序假设输入均匀分布,所以一般每个桶中的元素不会很多,因而运行得很快。

基数排序跟桶排序的时间复杂度都是O(n)。