文章图片标题

基数排序 Java 代码

分类:算法与数据结构 作者:阳光倾城 评论:0 点击: 364 次 日期:2016-08-01


基数排序 Java 代码

/*
* @!RadixSortAlgorithm.java
* By: Alvin Raj
* Date: 12 August 2002
* Algorithm adapted from: C++ Data Structures, Nell Dale
* Additional Comments added by Jason Harrison <harrison@cs.ubc.ca>
*
*  Algorithm comments from
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/radixsort.html
*
*/
public class RadixSortAlgorithm extends SortAlgorithm {
// for each of the 10 digits
   private LinkedQueue[] Q =
     { new LinkedQueue(),  //0
       new LinkedQueue(),  //1
       new LinkedQueue(),  //2
       new LinkedQueue(),  //3
       new LinkedQueue(),  //4
       new LinkedQueue(),  //5
       new LinkedQueue(),  //6
       new LinkedQueue(),  //7
       new LinkedQueue(),  //8
       new LinkedQueue()}; //9
    // Assumes all positive integers
        // numbDigits is the number of digits in the largest number
    void sort(int a[] , int numDigits) throws Exception {
        int arrayPos;
        // i is the radix
        for (int i = 1; i <= numDigits; i++) {
            if (stopRequested) {
                return;
            }
            arrayPos = 0;
            // Put values into queues according to radix
                        // least significant digit first, then second,...
                        // first pass sorts on least significant digit
            for (int j = 0; j < a.length; j++) {
                Q[getRadix(a[j],i)].enqueue(a[j]);
                                pause(-1,j); // JH
            }
            // Collect the queues and put them back into the array
                        // queues contain partially sorted lists after first
                        // pass -- moving to next significant digit will
                        // maintain this ordering.
            for (int j = 0; j < Q.length; j++) {
                while(!Q[j].isEmpty()) {
                    a[arrayPos] = Q[j].dequeue();
                    arrayPos++;
                }
                pause(-1,arrayPos);
            }
        }
    }
    void sort(int a[]) throws Exception {
        // Find the largest entry in a[]
        int max = 0;
                int maxIndex = 0;  // JH
        for (int i = 0; i < a.length; i++) {
            if (max < a[i]) {
                            max = a[i];
                            maxIndex = i; // JH
                            pause(maxIndex, i); // JH
            }
        }
        int numDigits = 1;
        int temp = 10;
                // compute the max number of digits
                // JH: this could be more easily be computed by using
                //     numDigits = (int) log(base10, max)
        while (true) {
            if (max >= temp) {
                numDigits++;
                temp*=10;
            }
            else
                break;
        }
        //call the sort
        sort(a,numDigits);
    }
    //returns the radix of the given number
    //EG:
    //2nd radix of 79981 is 8
    //1st radix of 79981 is 1
    public static int getRadix(int number, int radix) {
        return (int)(number / Math.pow(10,radix-1)) % 10;
    }
}




声明: 除非注明,本文属( 阳光倾城 )原创,转载请保留链接: http://www.tomrrow.com/archives-7829.html