mergesortapp.java

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

            variables[4].setText(Integer.toString(hi));
            tempLo = lo;
            variables[1].setText(Integer.toString(tempLo));
            arrayPointersPos[1] = tempLo;
            for(int i = lo; i <= hi; i++)
              arrayCanvas.setStatus(i, WORKING);
            arrayCanvas.repaint();
            pause();
         }
         if (runner == thisThread)
         {
            program.selectLine(6);
            tempHi = mid + 1;
            variables[5].setText(Integer.toString(tempHi));
            arrayPointersPos[2] = tempHi;
            arrayCanvas.repaint();
            pause();
         }
         if (runner == thisThread)
            arrayCanvas.setLabels("Merging", null);
         for(int k = lo; k <= hi; k++)
         {
            if (runner != thisThread)
               break;
            if (runner == thisThread)
            {
               program.selectLine(7);
               variables[3].setText(Integer.toString(k));
               scratchPointersPos[0] = k;
               arrayCanvas.repaint();
               pause();
            }
            if (runner == thisThread)
            {
               program.selectLine(8);
               compCt++;
               compField.setText(Integer.toString(compCt));
               pause();
            }
            if ((tempLo <= mid) && ((tempHi > hi) || (A[tempLo] < A[tempHi])))
            {
               if (runner == thisThread)
               {
                  program.selectLine(9);
                  exchangeCt++;
                  exchangeField.setText(Integer.toString(exchangeCt));
                  arrayCanvas.setScratchStatus(k, SWAPPING);
                  arrayCanvas.setArrow(tempLo, k, arrayCanvas.ARROW_DOWN);
                  arrayCanvas.repaint();
                  pause();
               }
               if (runner == thisThread)
               {
                  scratch[k] = A[tempLo];
                  arrayCanvas.repaint();
                  pause();
               }
               if (runner == thisThread)
               {
                  arrayCanvas.setScratchStatus(k, UNSORTED);
                  arrayCanvas.clearArrow();
                  arrayCanvas.repaint();
                  program.selectLine(10);
                  tempLo++;
                  variables[1].setText(Integer.toString(tempLo));
                  arrayPointersPos[1] = tempLo;
                  arrayCanvas.repaint();
                  pause();
               }
            }
            else
            {
               if (runner == thisThread)
               {
                  program.selectLine(11);
                  exchangeCt++;
                  exchangeField.setText(Integer.toString(exchangeCt));
                  arrayCanvas.setScratchStatus(k, SWAPPING);
                  arrayCanvas.setArrow(tempHi, k, arrayCanvas.ARROW_DOWN);
                  arrayCanvas.repaint();
                  pause();
               }
               if (runner == thisThread)
               {
                  scratch[k] = A[tempHi];
                  arrayCanvas.repaint();
                  pause();
               }
               if (runner == thisThread)
               {
                  arrayCanvas.setScratchStatus(k, UNSORTED);
                  arrayCanvas.clearArrow();
                  arrayCanvas.repaint();
                  program.selectLine(12);
                  tempHi++;
                  variables[5].setText(Integer.toString(tempHi));
                  arrayPointersPos[2] = tempHi;
                  arrayCanvas.repaint();
                  pause();
               }
            }
         }
         if (runner == thisThread)
            arrayCanvas.setLabels(null, "Copying Back");
         for(int k = lo; k <= hi; k++)
         {
            if (runner != thisThread)
               break;
            if (runner == thisThread)
            {
               program.selectLine(13);
               variables[3].setText(Integer.toString(k));
               arrayPointersPos[0] = k;
               scratchPointersPos[0] = k;
               arrayCanvas.repaint();
               pause();
            }
            if (runner == thisThread)
            {
               program.selectLine(14);
               exchangeCt++;
               exchangeField.setText(Integer.toString(exchangeCt));
               arrayCanvas.setStatus(k, SWAPPING);
               arrayCanvas.setArrow(k, k, arrayCanvas.ARROW_UP);
               arrayCanvas.repaint();
               pause();
            }
            if (runner == thisThread)
            {
               A[k] = scratch[k];
               arrayCanvas.repaint();
               pause();
            }
            if (runner == thisThread)
            {
               if ((lo == 0) && (hi == A.length - 1))
                 arrayCanvas.setStatus(k, DONE);
               else
                 arrayCanvas.setStatus(k, PARTSORTED);
               arrayCanvas.clearArrow();
               arrayCanvas.repaint();
            }
         }
         if (runner == thisThread)
         {
            variables[3].setText("");
            arrayPointersPos[0] = -2;
            scratchPointersPos[0] = -2;
            arrayCanvas.setLabels(null, null);
            arrayCanvas.repaint();
         }
      }
      else
      {
         if (runner == thisThread)
         {
            for(int i = 0; i < lo; i++)
              arrayCanvas.setStatus(i, UNSORTED);
            arrayCanvas.setStatus(lo, PARTSORTED);
            arrayCanvas.repaint();
            pause();
         }
      }
   }

   public void run()
   {
      thisThread = Thread.currentThread();
      if (runner == thisThread)
      {
         compCt = exchangeCt = 0;
         compField.setText("0");
         exchangeField.setText("0");
         stack = new Stack();
         variables[0].setText(Integer.toString(0));
         variables[2].setText("");
         variables[4].setText(Integer.toString(A.length-1));
         arrayCanvas.clearArrow();
         for(int i = 0; i < A.length; i++)
           arrayCanvas.setStatus(i, WORKING);
         arrayCanvas.repaint();
      }
      if (runner == thisThread)
         mergesort(0, A.length-1, thisThread);
      if (runner == thisThread)
      {
         program.selectLines(-1, -1);
         ok.setEnabled(true);
         contPause.setEnabled(false);
         clear.setEnabled(false);
         arrayLine.requestFocus();
         if (runsFromApplet)
         {
            if (isSpecial)
              ss.sortInfo[ss.MERGE].setData(arrayString, compCt, exchangeCt);
            else
              ss.sortInfo[ss.MERGE].setData(copy, compCt, exchangeCt);
            if (table != null)
              table.update(ss.MERGE, ss.sortInfo);
         }
         MessageBox mb = new MessageBox(ss, this, "Information",
                                        "Mergesort complete.", "information.gif");
      }
      stop();
   }

   private void noGraphicsMergesort(int lo, int hi)
   {
      compCt++;
      if (lo < hi)
      {
         int mid = (lo + hi) / 2;
         noGraphicsMergesort(lo, mid);
         noGraphicsMergesort(mid + 1, hi);
         int tempLo = lo;
         int tempHi = mid + 1;
         for(int k = lo; k <= hi; k++)
         {
            compCt++;
            if ((tempLo <= mid) && ((tempHi > hi) || (A[tempLo] < A[tempHi])))
            {
               exchangeCt++;
               scratch[k] = A[tempLo];
               tempLo++;
            }
            else
            {
               exchangeCt++;
               scratch[k] = A[tempHi];
               tempHi++;
            }
         }
         for(int k = lo; k <= hi; k++)
         {
            exchangeCt++;
            A[k] = scratch[k];
         }
      }
   }

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

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

}