欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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();

    }
}