桶排序、计数排序、基数排序（不是基于比较的排序）
- 非基于比较的排序，与被排序的样本的实际数据状况很有关系，所以实际中并不经常使用
- 时间复杂度O(N)，额外空间复杂度O(N)
- 稳定的排序
桶排序算法如下：
public class BucketSort {
public static void bucketSort (int[] arr) {
if (arr==null && arr.length<2) {
return;
}
int max = Integer.MIN_VALUE;
for (int i=0; i<arr.length; i++) {
max = Math.max(max, arr[i]);
}
int[] bucket = new int[max+1];
for (int j = 0; j<arr.length; j++) {
bucket[arr[j]]++;
}
int i = 0;
for (int k=0; k<bucket.length; k++) {
while (bucket[k]-- >0) {
arr[i++] = k;
}
}
}
public static void main(String[] args) {
int[] arr = {3,9,12,5,8,13,1};
bucketSort(arr);
System.out.println(Arrays.toString(arr));
}
}
| 
转播
