heapsortapp.java

来自「本程序提供了各种排序算法及演示,由java实现,可以清楚看到各算法的流程演示.」· Java 代码 · 共 570 行 · 第 1/2 页

// HeapSortApp.java
import java.awt.*;

public class HeapSortApp extends SortApp
{
   private int heapSize, line1, line2, line3;

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

      algCode = new String[23];
      algCode[0]  = "HEAPSORT (A)";
      algCode[1]  = "1. BUILD-HEAP (A)";
      algCode[2]  = "2. for k <- length[A] - 1 downto 1";
      algCode[3]  = "3.    do exchange A[0] <-> A[k]";
      algCode[4]  = "4.       heap-size[A] <- heap-size[A] - 1";
      algCode[5]  = "5.       HEAPIFY (A, 0)";
      algCode[6]  = "\n";
      algCode[7]  = "BUILD-HEAP (A)";
      algCode[8]  = "1. heap-size[A] <- length[A]";
      algCode[9]  = "2. for j <- (length[A] div 2) - 1 downto 0";
      algCode[10] = "3.    do HEAPIFY (A, j)";
      algCode[11] = "\n";
      algCode[12] = "HEAPIFY (A, i)";
      algCode[13] = " 1. l = 2 * i + 1";
      algCode[14] = " 2. r = 2 * i + 2";
      algCode[15] = " 3. if l < heap-size[A] and A[l] > A[i]";
      algCode[16] = " 4.    then max <- l";
      algCode[17] = " 5.    else max <- i";
      algCode[18] = " 6. if r < heap-size[A] and A[r] > A[max]";
      algCode[19] = " 7.    then max <- r";
      algCode[20] = " 8. if max <> i";
      algCode[21] = " 9.    then exchange A[i] <-> A[max]";
      algCode[22] = "10.         HEAPIFY (A, max)";

      program = new ProgramCanvas(algCode);

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

      numOfVars = 7;
      labels = new Label[numOfVars];
      labels[0] = new Label("heap-size[A]: ", Label.RIGHT);
      labels[1] = new Label("l: ", Label.RIGHT);
      labels[2] = new Label("k:  ", Label.RIGHT);
      labels[3] = new Label("r:  ", Label.RIGHT);
      labels[4] = new Label("j:  ", Label.RIGHT);
      labels[5] = new Label("i:  ", Label.RIGHT);
      labels[6] = new Label("max:  ", 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[4];
      arrayPointers[0] = "k";
      arrayPointers[1] = "i";
      arrayPointers[2] = "l";
      arrayPointers[3] = "r";
      arrayPointersPos = new int[4];

      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 varPanel4 = new Panel();
      varPanel4.setLayout(new GridLayout(1, 2));
      varPanel4.add(labels[6]);
      varPanel4.add(variables[6]);

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

      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(new Box(programPanel, algorithmName + " Algorithm", Box.LEFT), gbc);

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

      gbc.anchor = GridBagConstraints.CENTER;
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.weighty = 0;
      gbc.fill = GridBagConstraints.BOTH;
      rightPanel.add(new Box(statsPanel, "Algorithm Statistics", Box.LEFT), gbc);

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

      gbc.anchor = GridBagConstraints.CENTER;
      gbc.gridwidth = GridBagConstraints.REMAINDER;
      gbc.weightx = 100;
      gbc.weighty = 100;
      gbc.fill = GridBagConstraints.BOTH;
      add(rightPanel, gbc);

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

   private void clearHeapify()
   {
      arrayPointers[1] = "i";
      arrayPointers[2] = "l";
      arrayPointers[3] = "r";
      for(int x = 1; x < arrayPointersPos.length; x++)
        arrayPointersPos[x] = -2;
      variables[1].setText("");
      variables[3].setText("");
      variables[5].setText("");
      variables[6].setText("");
   }

   private void heapsort(Thread thisThread)
   {
      if (runner == thisThread)
      {
         line1 = 1;
         program.selectLines(line1, line2, line3);
         pause();
      }
      if (runner == thisThread)
         buildHeap(thisThread);
      for(int k = A.length - 1; k > 0; k--)
      {
         if (runner != thisThread)
            break;
         if (runner == thisThread)
         {
            line1 = 2;
            program.selectLines(line1, line2, line3);
            variables[2].setText(Integer.toString(k));
            arrayPointersPos[0] = k;
            arrayCanvas.repaint();
            pause();
         }
         if (runner == thisThread)
         {
            line1 = 3;
            program.selectLines(line1, line2, line3);
            exchangeCt++;
            exchangeField.setText(Integer.toString(exchangeCt));
            arrayCanvas.setStatus(0, SWAPPING);
            arrayCanvas.setStatus(k, SWAPPING);
            arrayCanvas.repaint();
            pause();
         }
         if (runner == thisThread)
         {
            int temp = A[0];
            A[0] = A[k];
            A[k] = temp;
            arrayCanvas.repaint();
            pause();
         }
         if (runner == thisThread)
         {
            arrayCanvas.setStatus(0, UNSORTED);
            arrayCanvas.setStatus(k, DONE);
            arrayCanvas.repaint();
            line1 = 4;
            program.selectLines(line1, line2, line3);
            heapSize--;
            variables[0].setText(Integer.toString(heapSize));
            pause();
         }
         if (runner == thisThread)
         {
            line1 = 5;
            program.selectLines(line1, line2, line3);
            pause();
         }
         if (runner == thisThread)
            heapify(0, thisThread);
      }
      if (runner == thisThread)
         arrayCanvas.setStatus(0, DONE);
   }

   private void buildHeap(Thread thisThread)
   {
      if (runner == thisThread)