常用排序算法总结10一一桶排序

定义

桶排序（英文：Bucket Sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ(n)）。但桶排序并不是比较排序，他不受到O(n log n)下限的影响。

算法步骤

桶排序以下列程序进行：

• 设置一个定量的数组当作空桶子。
• 寻访序列，并且把项目一个一个放到对应的桶子去。
• 对每个不是空的桶子进行排序。
• 从不是空的桶子里把项目再放回原来的序列中。

代码实现（java）

/**
 *
 * Description: 桶排序
 *
 * 桶排序适用于固定范围大小内数据的排序
 * @param: @param nums
 * @return: void
 * @throws
 */
public static void bucketSort(int[] nums)
{   
    // 假设现在是对年龄排序，最大年龄为120
    int BUCKETSIZE = 120;
    int bucket[] = new int[BUCKETSIZE];
    for (int i = 0; i < nums.length; ++i) {
        if (i <= BUCKETSIZE && i >= 0) {
            bucket[nums[i]]++;
        }
    }
    int index = 0;
    for (int i = 0; i < bucket.length; i++) {
        while (bucket[i] > 0) {
            nums[index++] = i;
            bucket[i]--;
        }
    }
}

参考文章

• 桶排序