桶排序
简单的桶排序，适用于正整数且上界不大的数组排序，原理是把数组的值当做bucket的下标，然后遍历一遍bucket，值大于0的对应的下标就已经自动排好序，该映射是线性的。时间复杂度为
桶排序代码
public static final int MAX = 1000;
public static void bucketSort(int[] array, int len){
int[] bucket = new int[MAX]; //初始化为0
for (int i = 0; i < len; i++){
bucket[array[i]]++;
}
int j = 0;
for (int i = 0; i < MAX; i++){
while (bucket[i]-- > 0){
array[j++] = i;
}
}
}
测试样例
- 100 599 300 99 7
7 99 100 300 599
----- end -----