shearsortapp.java

本程序提供了各种排序算法及演示,由java实现,可以清楚看到各算法的流程演示.

      }
      for(int i = 1; i <= (int)Math.sqrt(A.length); i++)
      {
         if (runner != thisThread)
            break;
         if (runner == thisThread)
         {
            program.selectLine(2);
            variables[iIndex].setText(Integer.toString(i));
            pause();
         }
         if (runner == thisThread)
         {
            program.selectLine(3);
            pause();
         }
         if ((runner == thisThread) && (A.length % i == 0))
         {
            program.selectLine(4);
            rows = i;
            variables[rowsIndex].setText(Integer.toString(rows));
            pause();
         }
      }
      if (runner == thisThread)
      {
         variables[iIndex].setText("");
         program.selectLine(5);
         cols = A.length / rows;
         variables[colsIndex].setText(Integer.toString(cols));
         pause();
      }
      while ((runner == thisThread) && (pow <= rows))
      {
         if (runner == thisThread)
         {
            program.selectLine(6);
            pause();
         }
         if (runner == thisThread)
         {
            program.selectLine(7);
            pow *= 2;
            variables[powIndex].setText(Integer.toString(pow));
            log += 1;
            variables[logIndex].setText(Integer.toString(log));
            pause();
         }
      }
      if (runner == thisThread)
      {
         program.selectLine(6);
         pause();
      }
      for(int k = 0; k < log; k++)
      {
         if (runner != thisThread)
            break;
         if (runner == thisThread)
         {
            program.selectLines(8, -1);
            variables[kIndex].setText(Integer.toString(k));
            pause();
         }
         for(int j = 0; j < cols / 2; j++)
         {
            if (runner != thisThread)
               break;
            if (runner == thisThread)
            {
               program.selectLines(9, -1);
               variables[jIndex].setText(Integer.toString(j));
               pause();
            }
            for(int i = 0; i < rows; i++)
            {
               if (runner != thisThread)
                  break;
               if (runner == thisThread)
               {
                  program.selectLines(10, -1);
                  variables[iIndex].setText(Integer.toString(i));
                  variables[jIndex].setText(Integer.toString(j));
                  pause();
               }
               if (runner == thisThread)
               {
                  line1 = 11;
                  program.selectLines(line1, -1);
                  pause();
               }
               if (runner == thisThread)
                  sortWithGraphics(i*cols, (i+1)*cols, 0, 1, i % 2 == 0, thisThread);
            }
            for(int i = 0; i < rows; i++)
            {
               if (runner != thisThread)
                  break;
               if (runner == thisThread)
               {
                  program.selectLines(12, -1);
                  variables[iIndex].setText(Integer.toString(i));
                  variables[jIndex].setText(Integer.toString(j));
                  pause();
               }
               if (runner == thisThread)
               {
                  line1 = 13;
                  program.selectLines(line1, -1);
                  pause();
               }
               if (runner == thisThread)
                  sortWithGraphics(i*cols, (i+1)*cols, 1, 1, i % 2 == 0, thisThread);
            }
         }
         for(int j = 0; j < rows / 2; j++)
         {
            if (runner != thisThread)
               break;
            if (runner == thisThread)
            {
               program.selectLines(14, -1);
               variables[jIndex].setText(Integer.toString(j));
               pause();
            }
            for(int i = 0; i < cols; i++)
            {
               if (runner != thisThread)
                  break;
               if (runner == thisThread)
               {
                  program.selectLines(15, -1);
                  variables[iIndex].setText(Integer.toString(i));
                  variables[jIndex].setText(Integer.toString(j));
                  pause();
               }
               if (runner == thisThread)
               {
                  line1 = 16;
                  program.selectLines(line1, -1);
                  pause();
               }
               if (runner == thisThread)
                  sortWithGraphics(i, rows*cols+i, 0, cols, true, thisThread);
            }
            for(int i = 0; i < cols; i++)
            {
               if (runner != thisThread)
                  break;
               if (runner == thisThread)
               {
                  program.selectLines(17, -1);
                  variables[iIndex].setText(Integer.toString(i));
                  variables[jIndex].setText(Integer.toString(j));
                  pause();
               }
               if (runner == thisThread)
               {
                  line1 = 18;
                  program.selectLines(line1, -1);
                  pause();
               }
               if (runner == thisThread)
                  sortWithGraphics(i, rows*cols+i, cols, cols, true, thisThread);
            }
         }
         if (runner == thisThread)
            variables[jIndex].setText("");
      }
      if (runner == thisThread)
         variables[kIndex].setText("");
      int tempJ = 0;
      for(int j = 0; j <= cols / 2; j++)
      {
         if (runner != thisThread)
            break;
         if (runner == thisThread)
         {
            program.selectLines(19, -1);
            tempJ = j;
            variables[jIndex].setText(Integer.toString(j));
            pause();
         }
         for(int i = 0; i < rows; i++)
         {
            if (runner != thisThread)
               break;
            if (runner == thisThread)
            {
               program.selectLines(20, -1);
               variables[iIndex].setText(Integer.toString(i));
               variables[jIndex].setText(Integer.toString(j));
               pause();
            }
            if (runner == thisThread)
            {
               line1 = 21;
               program.selectLines(line1, -1);
               pause();
            }
            if (runner == thisThread)
               sortWithGraphics(i*cols, (i+1)*cols, 0, 1, true, thisThread);
         }
         for(int i=0; i < rows; i++)
         {
            if (runner != thisThread)
               break;
            if (runner == thisThread)
            {
               program.selectLines(22, -1);
               variables[iIndex].setText(Integer.toString(i));
               variables[jIndex].setText(Integer.toString(j));
               pause();
            }
            if (runner == thisThread)
            {
               line1 = 23;
               program.selectLines(line1, -1);
               pause();
            }
            if (runner == thisThread)
               sortWithGraphics(i*cols, (i+1)*cols, 1, 1, true, thisThread);
         }
      }
      if (runner == thisThread)
      {
         variables[jIndex].setText(Integer.toString(tempJ));
         for(int i = 0; i < A.length; i++)
           arrayCanvas.setStatus(i, DONE);
         arrayCanvas.repaint();
         program.selectLines(-1, -1);
         ok.setEnabled(true);
         contPause.setEnabled(false);
         clear.setEnabled(false);
         arrayLine.requestFocus();
         if (runsFromApplet)
         {
            if (isSpecial)
              ss.sortInfo[ss.SHEAR].setData(arrayString, compCt, exchangeCt);
            else
              ss.sortInfo[ss.SHEAR].setData(copy, compCt, exchangeCt);
            if (table != null)
              table.update(ss.SHEAR, ss.sortInfo);
         }
         MessageBox mb = new MessageBox(ss, this, "Information",
                                        "Shearsort complete.", "information.gif");
      }
      stop();
   }

   private void sort(int lo, int hi, int offset, int n, boolean up)
   {
      int j = lo + offset;
      while (j+n < hi)
      {
         compCt++;
         if ((up && (A[j] > A[j+n])) || (!up && (A[j] < A[j+n])))
         {
            exchangeCt++;
            int temp = A[j];
            A[j] = A[j+n];
            A[j+n] = temp;
         }
         j += 2*n;
      }
   }

   private void noGraphicsShearsort()
   {
      int log = 0, pow = 1, rows = 1, cols;
      for(int i = 1; i <= (int)Math.sqrt(A.length); i++)
        if (A.length % i == 0)
          rows = i;
      cols = A.length / rows;
      while (pow <= rows)
      {
         pow *= 2;
         log += 1;
      }
      for(int k = 0; k < log; k++)
      {
         for(int j = 0; j < cols / 2; j++)
         {
            for(int i = 0; i < rows; i++)
              sort(i*cols, (i+1)*cols, 0, 1, i % 2 == 0);
            for(int i = 0; i < rows; i++)
              sort(i*cols, (i+1)*cols, 1, 1, i % 2 == 0);
         }
         for(int j = 0; j < rows / 2; j++)
         {
            for(int i = 0; i < cols; i++)
              sort(i, rows*cols+i, 0, cols, true);
            for(int i = 0; i < cols; i++)
              sort(i, rows*cols+i, cols, cols, true);
         }
      }
      for(int j = 0; j <= cols / 2; j++)
      {
         for(int i = 0; i < rows; i++)
           sort(i*cols, (i+1)*cols, 0, 1, true);
         for(int i=0; i < rows; i++)
           sort(i*cols, (i+1)*cols, 1, 1, true);
      }
   }

   public void noGraphics()
   {
      int n = A.length;
      compCt = exchangeCt = 0;
      noGraphicsShearsort();
      if (runsFromApplet)
      {
         if (isSpecial)
           ss.sortInfo[ss.SHEAR].setData(arrayString, compCt, exchangeCt);
         else
           ss.sortInfo[ss.SHEAR].setData(copy, compCt, exchangeCt);
         if (table != null)
           table.update(ss.SHEAR, ss.sortInfo);
      }
      compField.setText(Integer.toString(compCt));
      exchangeField.setText(Integer.toString(exchangeCt));
      MessageBox mb = new MessageBox(ss, this, "Information",
                                     "Shearsort complete.", "information.gif");
   }

   public static void main(String[] args)
   {
      ShearSortApp ssa = new ShearSortApp(null, false, null, null, null);
   }

}