用Java代码写一个桶排序
时间: 2023-01-29 21:34:26 浏览: 120
sort_utility:不同排序算法的 Java 实现(bucket、count)
桶排序是一种非常快速的排序算法,它的时间复杂度为 O(n),只要有足够的空间。
下面是用 Java 实现桶排序的代码示例:
```
public class BucketSort {
public static void sort(int[] arr) {
// 找到数组中的最大值和最小值
int max = arr[0];
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
// 创建桶,并将每个元素放入桶中
int bucketNum = (max - min) / arr.length + 1;
List<List<Integer>> bucketList = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketList.add(new ArrayList<>());
}
for (int i = 0; i < arr.length; i++) {
int index = (arr[i] - min) / arr.length;
bucketList.get(index).add(arr[i]);
}
// 对每个桶内部进行排序
for (int i = 0; i < bucketList.size(); i++) {
Collections.sort(bucketList.get(i));
}
// 将排序后的桶中的元素放回原数组中
int k = 0;
for (int i = 0; i < bucketList.size(); i++) {
for (int j = 0; j < bucketList.get(i).size(); j++) {
arr[k++] = bucketList.get(i).get(j);
}
}
}
}
```
使用方法:
```
int[] arr = {4, 5, 6, 3, 2, 1};
BucketSort.sort(arr);
System.out.println(Arrays.toString(arr)); // 输出:[1, 2, 3, 4, 5, 6]
```
希望这些内容对你有帮助。
阅读全文