ranksort.java

来自「这是Java的模式编程」· Java 代码 · 共 55 行

package Strategy;
import java.lang.Comparable;
public class RankSort extends SortStrategy
{
   /** sort the array a using the rank sort method */
   public void rank(Comparable [] a, int [] r)
   {// Rank the objects in a[].
      // make sure rank array is large enough
      if (r.length < a.length)
         throw new IllegalArgumentException
               ("length of rank array cannot " +
                "be less than the number of objects");

      // set all ranks to zero
      for (int i = 0; i < a.length; i++)
         r[i] = 0;

      // compare all pairs of objects
      for (int i = 1; i < a.length; i++)
         for (int j = 0; j < i; j++)
            if (a[j].compareTo(a[i])<=0) r[i]++;
            else r[j]++;
   }

   public void sort(Comparable [] a)
   {
      // create rank array
      int [] r = new int[a.length];

      // rank the elements
      rank(a, r);

      // rearrange into sorted order
      rearrange(a, r);
      super.printArray(a);
   }

   /** rearrange objects by rank using an additional array
     * @param a is the object array
     * @param r is the rank array */
   private void rearrange(Comparable [] a, int [] r)
   {
      // create an additional array u
      Comparable [] u = new Comparable [a.length];

      // move references to correct place in u
      for (int i = 0; i < a.length; i++)
         u[r[i]] = a[i];

      // move back to a
      for (int i = 0; i < a.length; i++)
         a[i] = u[i];
   }

}