mergesortapp.java

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

// MergeSortApp.java
import java.awt.*;

public class MergeSortApp extends SortApp
{
   private Stack stack;

   public MergeSortApp(SortStarter ss, boolean runsFromApplet, String _arrayString,
                       CompareTable table, int[] array)
   {
      super(ss, runsFromApplet, SortStarter.MERGE, "Mergesort", table, array != null);
      arrayString = _arrayString;
      if (isSpecial)
      {
         A = array;
         AToCopy();
         copyToRandomCopy();
      }

      algCode = new String[15];
      algCode[0]  = "MERGESORT (A, lo, hi)";
      algCode[1]  = " 1. if lo < hi then";
      algCode[2]  = " 2.    mid = (lo + hi) / 2";
      algCode[3]  = " 3.    MERGESORT (A, lo, mid)";
      algCode[4]  = " 4.    MERGESORT (A, mid+1, hi)";
      algCode[5]  = " 5.    L = lo";
      algCode[6]  = " 6.    H = mid + 1";
      algCode[7]  = " 7.    for k <- lo to hi";
      algCode[8]  = " 8.       do if L <= mid and (H > hi or A[L] < A[H])";
      algCode[9]  = " 9.             then scratch[k] = A[L]";
      algCode[10] = "10.                  L <- L + 1";
      algCode[11] = "11.             else scratch[k] = A[H]";
      algCode[12] = "12.                  H <- H + 1";
      algCode[13] = "13.    for k <- lo to hi";
      algCode[14] = "14.       do A[k] <- scratch[k]";

      program = new ProgramCanvas(algCode);

      stackArea = new StackArea();
      stackPane = new ScrollPane(ScrollPane.SCROLLBARS_AS_NEEDED);
      stackPane.setBackground(Color.white);
      stackPane.add(stackArea);
      stackPane.setSize(300, 100);
      stackArea.setPane(stackPane);

      Panel programPanel = new Panel();
      programPanel.setLayout(new GridBagLayout());
      gbc.insets = new Insets(0, 0, 0, 0);
      gbc.anchor = GridBagConstraints.CENTER;
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 0;
      gbc.weighty = 100;
      gbc.fill = GridBagConstraints.BOTH;
      programPanel.add(new Canvas(), gbc);
      gbc.weighty = 0;
      programPanel.add(program, gbc);
      gbc.weighty = 100;
      programPanel.add(new Canvas(), gbc);

      Panel leftPanel = new Panel();
      leftPanel.setLayout(new GridBagLayout());
      gbc.anchor = GridBagConstraints.CENTER;
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.weighty = 100;
      gbc.fill = GridBagConstraints.BOTH;
      leftPanel.add(new Box(programPanel, algorithmName + " Algorithm", Box.LEFT), gbc);
      gbc.insets = new Insets(5, 0, 0, 0);
      gbc.anchor = GridBagConstraints.CENTER;
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weighty = 0;
      gbc.fill = GridBagConstraints.HORIZONTAL;
      leftPanel.add(stackPane, gbc);

      numOfVars = 6;
      labels = new Label[numOfVars];
      labels[0] = new Label("lo: ", Label.RIGHT);
      labels[1] = new Label("L: ", Label.RIGHT);
      labels[2] = new Label("mid: ", Label.RIGHT);
      labels[3] = new Label("k: ", Label.RIGHT);
      labels[4] = new Label("hi: ", Label.RIGHT);
      labels[5] = new Label("H: ", Label.RIGHT);
      variables = new TextField[numOfVars];
      for(int i = 0; i < numOfVars; i++)
      {
         variables[i] = new TextField(2);
         variables[i].setEditable(false);
         variables[i].setBackground(Color.white);
      }
      arrayPointers = new String[3];
      arrayPointers[0] = "k";
      arrayPointers[1] = "L";
      arrayPointers[2] = "H";
      arrayPointersPos = new int[3];
      scratchPointers = new String[1];
      scratchPointers[0] = "k";
      scratchPointersPos = new int[1];

      Panel varPanel0 = new Panel();
      varPanel0.setLayout(new GridLayout(2, 1));
      varPanel0.add(labels[0]);
      varPanel0.add(labels[1]);

      Panel varPanel1 = new Panel();
      varPanel1.setLayout(new GridLayout(2, 1));
      varPanel1.add(variables[0]);
      varPanel1.add(variables[1]);

      Panel varPanel2 = new Panel();
      varPanel2.setLayout(new GridLayout(2, 2));
      for(int i = 2; i < 4; i++)
      {
         varPanel2.add(labels[i]);
         varPanel2.add(variables[i]);
      }

      Panel varPanel3 = new Panel();
      varPanel3.setLayout(new GridLayout(2, 2));
      for(int i = 4; i < 6; i++)
      {
         varPanel3.add(labels[i]);
         varPanel3.add(variables[i]);
      }

      Panel variablesPanel = new Panel();
      variablesPanel.setLayout(new FlowLayout());
      variablesPanel.add(varPanel0);
      variablesPanel.add(varPanel1);
      variablesPanel.add(varPanel2);
      variablesPanel.add(varPanel3);

      Panel arrayVarPanel = new Panel();
      arrayVarPanel.setLayout(new GridBagLayout());
      gbc.insets = new Insets(0, 5, 0, 5);
      gbc.anchor = GridBagConstraints.CENTER;
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.weighty = 100;
      gbc.fill = GridBagConstraints.BOTH;
      arrayVarPanel.add(arrayPane, gbc);

      gbc.insets = new Insets(0, 0, 0, 0);
      gbc.anchor = GridBagConstraints.CENTER;
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 0;
      gbc.weighty = 0;
      gbc.fill = GridBagConstraints.NONE;
      arrayVarPanel.add(variablesPanel, gbc);

      setLayout(new GridBagLayout());

      gbc.insets = new Insets(0, 0, 0, 0);
      gbc.anchor = GridBagConstraints.NORTH;
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.fill = GridBagConstraints.HORIZONTAL;
      add(topPanel, gbc);

      gbc.anchor = GridBagConstraints.WEST;
      gbc.gridwidth = 1;
      gbc.weightx = 0;
      gbc.fill = GridBagConstraints.BOTH;
      add(new Box(inputPanel, "Array Data", Box.LEFT), gbc);

      gbc.anchor = GridBagConstraints.EAST;
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.fill = GridBagConstraints.BOTH;
      add(new Box(speedPanel, "Speed Controls", Box.LEFT), gbc);

      gbc.anchor = GridBagConstraints.CENTER;
      gbc.gridwidth = 1;
      gbc.weightx = 0;
      gbc.weighty = 100;
      gbc.fill = GridBagConstraints.BOTH;
      add(leftPanel, gbc);



      gbc.anchor = GridBagConstraints.CENTER;
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.weighty = 100;
      gbc.fill = GridBagConstraints.BOTH;
      add(new Box(arrayVarPanel, "Array and Pointers", Box.LEFT), gbc);

      gbc.anchor = GridBagConstraints.WEST;
      gbc.gridwidth = 1;
      gbc.weightx = 0;
      gbc.weighty = 0;
      gbc.fill = GridBagConstraints.BOTH;
      add(new Box(statsPanel, "Algorithm Statistics", Box.LEFT), gbc);

      gbc.anchor = GridBagConstraints.EAST;
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.fill = GridBagConstraints.BOTH;
      add(new Box(buttonPanel, "User Options", Box.LEFT), gbc);

      validate();
      pack();
      setVisible(true);
      if (arrayString != null)
        arrayLine.setText(arrayString);
   }

   private void mergesort(int lo, int hi, Thread thisThread)
   {
      int mid = 0, tempHi = 0, tempLo = 0;
      if (runner == thisThread)
      {
         program.selectLine(1);
         compCt++;
         compField.setText(Integer.toString(compCt));
      }
      if (lo < hi)
      {
         if (runner == thisThread)
            pause();
         if (runner == thisThread)
         {
            program.selectLine(2);
             mid = (lo + hi) / 2;
            variables[2].setText(Integer.toString(mid));
            pause();
         }
         if (runner == thisThread)
         {
            stack.push((mid + 1) + ".." + hi);
            stackArea.setData(stack);
            program.selectLine(3);
            variables[0].setText(Integer.toString(lo));
            variables[2].setText("");
            variables[4].setText(Integer.toString(mid));
            for(int i = lo; i <= mid; i++)
              arrayCanvas.setStatus(i, WORKING);
            for(int i = mid + 1; i < A.length; i++)
              arrayCanvas.setStatus(i, UNSORTED);
            arrayCanvas.repaint();
            pause();
         }
         if (runner == thisThread)
            mergesort(lo, mid, thisThread);
         if (runner == thisThread)
         {
            String dummy;
            if (!stack.isEmpty())
              dummy = stack.pop();
            stackArea.setData(stack);
            program.selectLine(4);
            variables[0].setText(Integer.toString(mid + 1));
            variables[2].setText("");
            variables[4].setText(Integer.toString(hi));
            for(int i = mid+1; i <= hi; i++)
              arrayCanvas.setStatus(i, WORKING);
            for(int i = hi + 1; i < A.length; i++)
              arrayCanvas.setStatus(i, UNSORTED);
            arrayCanvas.repaint();
            pause();
         }
         if (runner == thisThread)
            mergesort(mid + 1, hi, thisThread);
         if (runner == thisThread)
         {
            program.selectLine(5);
            variables[0].setText(Integer.toString(lo));
            variables[2].setText(Integer.toString(mid));