基数排序 Java 代码

2016-08-01 11:36:29 暂无评论阳光倾城算法与数据结构 704

基数排序 java 代码

/*
* @!RadixSortAlgorithm.java
* By: Alvin Raj
* Date: 12 August 2002
* Algorithm adapted from: C++ Data Structures, Nell Dale

*
* Algorithm comments from
* https://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

            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

                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.

                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

                            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;
    }
}