/// 桶排序法(遞增)。
pub fn bucket_sort(array: &mut [i32], min: i32, max: i32, bucket_capacity: usize) {
let bucket_count = ((max - min) as usize + bucket_capacity) / bucket_capacity;
let mut buckets: Vec<Vec<i32>> = Vec::with_capacity(bucket_count);
for _ in 0..bucket_count {
let bucket = Vec::new();
buckets.push(bucket);
}
for n in array.iter().copied() {
let k = (n - min) as usize / bucket_capacity;
buckets[k].push(n);
}
let mut p = 0;
for mut bucket in buckets {
bucket.sort();
for n in bucket {
array[p] = n;
p += 1;
}
}
}
/// 桶排序法(遞減)。
pub fn bucket_sort_desc(array: &mut [i32], min: i32, max: i32, bucket_capacity: usize) {
let bucket_count = ((max - min) as usize + bucket_capacity) / bucket_capacity;
let mut buckets: Vec<Vec<i32>> = Vec::with_capacity(bucket_count);
for _ in 0..bucket_count {
let bucket = Vec::new();
buckets.push(bucket);
}
for n in array.iter().copied() {
let k = (n - min) as usize / bucket_capacity;
buckets[k].push(n);
}
let mut p = 0;
for mut bucket in buckets.into_iter().rev() {
bucket.sort_by(|a, b| b.cmp(a));
for n in bucket {
array[p] = n;
p += 1;
}
}
}
/**
* 桶排序法(遞增)。
*/
public static void bucketSort(final int[] array, final int min, final int max, final int bucketCapacity) {
final int bucketCount = (max - min + bucketCapacity) / bucketCapacity;
final ArrayList<Integer>[] buckets = new ArrayList[bucketCount];
for (int i = 0; i < bucketCount; ++i) {
final ArrayList<Integer> bucket = new ArrayList<>();
buckets[i] = bucket;
}
for (final int n : array) {
final int k = (n - min) / bucketCapacity;
buckets[k].add(n);
}
int p = 0;
for (final ArrayList<Integer> bucket : buckets) {
Collections.sort(bucket);
for (final int n : bucket) {
array[p++] = n;
}
}
}
/**
* 桶排序法(遞減)。
*/
public static void bucketSortDesc(final int[] array, final int min, final int max, final int bucketCapacity) {
final int bucketCount = (max - min + bucketCapacity) / bucketCapacity;
final ArrayList<Integer>[] buckets = new ArrayList[bucketCount];
for (int i = 0; i < bucketCount; ++i) {
final ArrayList<Integer> bucket = new ArrayList<>();
buckets[i] = bucket;
}
for (final int n : array) {
final int k = (n - min) / bucketCapacity;
buckets[k].add(n);
}
int p = 0;
for (int i = bucketCount - 1; i >= 0; --i) {
final ArrayList<Integer> bucket = buckets[i];
Collections.sort(bucket, (a, b) -> b - a);
for (final int n : bucket) {
array[p++] = n;
}
}
}
/**
* 桶排序法(遞增)。
*/
function bucketSort(array: number[], min: number, max: number, bucketCapacity: number) {
const bucketCount = Math.floor((max - min + bucketCapacity) / bucketCapacity);
const buckets = new Array<number[]>(bucketCount);
for (let i = 0;i < bucketCount;++i) {
buckets[i] = [];
}
for (const n of array) {
const k = Math.floor((n - min) / bucketCapacity);
buckets[k].push(n);
}
let p = 0;
for (const bucket of buckets) {
bucket.sort((a, b) => a - b);
for (const n of bucket) {
array[p] = n;
p += 1;
}
}
}
/**
* 桶排序法(遞減)。
*/
function bucketSortDesc(array: number[], min: number, max: number, bucketCapacity: number) {
const bucketCount = Math.floor((max - min + bucketCapacity) / bucketCapacity);
const buckets = new Array<number[]>(bucketCount);
for (let i = 0;i < bucketCount;i++) {
buckets[i] = [];
}
for (const n of array) {
const k = Math.floor((n - min) / bucketCapacity);
buckets[k].push(n);
}
let p = 0;
for (let i = buckets.length - 1;i >= 0;i--) {
const bucket = buckets[i];
bucket.sort((a, b) => b - a);
for (const n of bucket) {
array[p] = n;
p += 1;
}
}
}
// 桶排序法(遞增)。
func BucketSort(array []int, min int, max int, bucketCapacity int) {
bucketCount := (max - min + bucketCapacity) / bucketCapacity
buckets := make([][]int, 0, bucketCount)
for i := 0; i < bucketCount; i += 1 {
bucket := make([]int, 0)
buckets = append(buckets, bucket)
}
for _, n := range array {
k := (n - min) / bucketCapacity
buckets[k] = append(buckets[k], n)
}
p := 0
for _, bucket := range buckets {
sort.Ints(bucket)
for _, n := range bucket {
array[p] = n
p += 1
}
}
}
// 桶排序法(遞減)。
func BucketSortDesc(array []int, min int, max int, bucketCapacity int) {
bucketCount := (max - min + bucketCapacity) / bucketCapacity
buckets := make([][]int, 0, bucketCount)
for i := 0; i < bucketCount; i += 1 {
bucket := make([]int, 0)
buckets = append(buckets, bucket)
}
for _, n := range array {
k := (n - min) / bucketCapacity
buckets[k] = append(buckets[k], n)
}
p := 0
for i := bucketCount - 1; i >= 0; i -= 1 {
bucket := buckets[i]
sort.Sort(sort.Reverse(sort.IntSlice(bucket)))
for _, n := range bucket {
array[p] = n
p += 1
}
}
}
