Java linear bucket sort
程序员文章站
2022-04-01 16:53:01
...
public class MyTimer {
private static long begin;
public static void time_start(){
begin = System.nanoTime();
}
public static double time_end_milli_seconds(){
return System.nanoTime()-begin/1e6;
}
public static double time_end_seconds(){
double total_time = (System.nanoTime()-begin)/1e6;
return ((double)((int)total_time))/1000;
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class RandomGenerator {
public int[] random_generate(int min,int max,int numtrials){
int[] int_array = new int[numtrials];
Random random = new Random();
for (int i = 0; i < numtrials; i++) {
int random_num = random.nextInt(max)%(max-min+1) + min;
int_array[i] = random_num;
}
return int_array;
}
}
import java.util.ArrayList;
import java.util.List;
public class BucketSort {
public int[] bucket_sort(int[] original_array,int max){
// index: 0-99 but max is : 100 . the point is the array index for bucketsort
int[] store_array = new int[max+1];
for (int i = 0; i < original_array.length; i++) {
int int_num = original_array[i];
// here is the miracle of bucketsort
store_array[int_num]= ++store_array[int_num];
}
int[] final_sorted_array = new int[original_array.length];
int cherry_pointer = 0;
for (int cherry = 0; cherry < store_array.length; cherry++) {
int cherry_num = store_array[cherry];
for (int j = 0; j < cherry_num; j++) {
final_sorted_array[cherry_pointer]=cherry;
++cherry_pointer;
}
}
return final_sorted_array;
}
}
public class TestBucketSort {
public double test_bucketsort(){
MyTimer.time_start();
int min = 1;
int max = 300;
int num_trails = 10000;
BucketSort bucketSort = new BucketSort();
RandomGenerator randomGenerator = new RandomGenerator();
int[] random_array = randomGenerator.random_generate(min,max,num_trails);
for (int i = num_trails-100; i < random_array.length; i++) {
System.out.println(random_array[i]);
}
int[] sorted_array = bucketSort.bucket_sort(random_array,max);
double time_end = MyTimer.time_end_seconds();
for (int i = 0; i < sorted_array.length; i++) {
System.out.println(sorted_array[i]);
}
System.out.println("Time elapse : "+time_end+"s sorted_array.length: "+sorted_array.length);
return time_end;
}
public static void main(String[] args) {
TestBucketSort testBucketSort = new TestBucketSort();
testBucketSort.test_bucketsort();
}
}
推荐阅读
-
JAVA基于Arrays.sort()实现数组升序和降序
-
Java.lang.Arrays中的toString()和sort()基本使用形式
-
5.4 集合的排序(Java学习笔记)(Collections.sort(),及Arrays.sort()底层分析)
-
Java排序的那些事之sort方法的使用详解
-
java冒泡排序Bubble Sort算法代码
-
Java对学生成绩排序——通过list.sort()对list进行排序
-
Java中Arrays.sort()的三种常用用法(自定义排序规则)
-
Rank Sort in Java -Yuan.
-
浅谈Java中Collections.sort对List排序的两种方法
-
java中Arrays.sort()对二位数组进行排序