heapsortapp.java

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

      {
         line2 = 7;
         program.selectLines(line1, line2, line3);
         pause();
      }
      if (runner == thisThread)
      {
         line2 = 8;
         program.selectLines(line1, line2, line3);
         heapSize = A.length;
         variables[0].setText(Integer.toString(heapSize));
         pause();
      }
      for(int j = A.length / 2 - 1; j >= 0; j--)
      {
         if (runner != thisThread)
            break;
         if (runner == thisThread)
         {
            line2 = 9;
            program.selectLines(line1, line2, line3);
            variables[4].setText(Integer.toString(j));
            pause();
         }
         if (runner == thisThread)
         {
            line2 = 10;
            program.selectLines(line1, line2, line3);
            pause();
         }
         if (runner == thisThread)
            heapify(j, thisThread);
      }
      if (runner == thisThread)
      {
         line2 = -1;
         variables[4].setText("");
      }
   }

   private void heapify(int i, Thread thisThread)
   {
      int max = 0, l = 0, r = 0;
      if (runner == thisThread)
      {
         clearHeapify();
         variables[5].setText(Integer.toString(i));
         line3 = 12;
         program.selectLines(line1, line2, line3);
         arrayPointersPos[1] = i;
         arrayCanvas.repaint();
         pause();
      }
      if (runner == thisThread)
      {
         line3 = 13;
         program.selectLines(line1, line2, line3);
         l = 2 * i + 1;
         variables[1].setText(Integer.toString(l));
         if (l < A.length)
           arrayPointersPos[2] = l;
         else
           arrayPointersPos[2] = -2;
         arrayCanvas.repaint();
         pause();
      }
      if (runner == thisThread)
      {
         line3 = 14;
         program.selectLines(line1, line2, line3);
         r = 2 * i + 2;
         variables[3].setText(Integer.toString(r));
         if (r < A.length)
           arrayPointersPos[3] = r;
         else
           arrayPointersPos[3] = -2;
         arrayCanvas.repaint();
         pause();
      }
      if (runner == thisThread)
      {
         line3 = 15;
         program.selectLines(line1, line2, line3);
         compCt++;
         compField.setText(Integer.toString(compCt));
         pause();
      }
      if ((runner == thisThread) && (l < heapSize) && (A[l] > A[i]))
      {
         line3 = 16;
         program.selectLines(line1, line2, line3);
         max = l;
         variables[6].setText(Integer.toString(max));
         arrayPointers[2] = "max";
         arrayCanvas.repaint();
         pause();
      }
      else
      {
         if (runner == thisThread)
         {
            line3 = 17;
            program.selectLines(line1, line2, line3);
            max = i;
            variables[6].setText(Integer.toString(max));
            arrayPointers[1] = "max";
            arrayCanvas.repaint();
            pause();
         }
      }
      if (runner == thisThread)
      {
         line3 = 18;
         program.selectLines(line1, line2, line3);
         compCt++;
         compField.setText(Integer.toString(compCt));
         pause();
      }
      if ((runner == thisThread) && (r < heapSize) && (A[r] > A[max]))
      {
         line3 = 19;
         program.selectLines(line1, line2, line3);
         max = r;
         variables[6].setText(Integer.toString(max));
         arrayPointers[1] = "i";
         arrayPointers[2] = "l";
         arrayPointers[3] = "max";
         arrayCanvas.repaint();
         pause();
      }
      if (runner == thisThread)
      {
         line3 = 20;
         program.selectLines(line1, line2, line3);
         compCt++;
         compField.setText(Integer.toString(compCt));
         pause();
      }
      if (max != i)
      {
         if (runner == thisThread)
         {
            line3 = 21;
            program.selectLines(line1, line2, line3);
            exchangeCt++;
            exchangeField.setText(Integer.toString(exchangeCt));
            arrayCanvas.setStatus(i, SWAPPING);
            arrayCanvas.setStatus(max, SWAPPING);
            arrayCanvas.repaint();
            pause();
         }
         if (runner == thisThread)
         {
            int temp = A[i];
            A[i] = A[max];
            A[max] = temp;
            arrayCanvas.repaint();
            pause();
         }
         if (runner == thisThread)
         {
            arrayCanvas.setStatus(i, UNSORTED);
            arrayCanvas.setStatus(max, UNSORTED);
            arrayCanvas.repaint();
            line3 = 22;
            program.selectLines(line1, line2, line3);
            pause();
         }
         if (runner == thisThread)
            heapify(max, thisThread);
      }
      if (runner == thisThread)
      {
         line3 = -1;
         clearHeapify();
      }
   }

   public void run()
   {
      thisThread = Thread.currentThread();
      if (runner == thisThread)
      {
         line1 = line2 = line3 = -1;
         compCt = exchangeCt = 0;
         compField.setText("0");
         exchangeField.setText("0");
      }
      if (runner == thisThread)
         heapsort(thisThread);
      if (runner == thisThread)
      {
         arrayCanvas.repaint();
         program.selectLines(-1, -1, -1);
         ok.setEnabled(true);
         contPause.setEnabled(false);
         clear.setEnabled(false);
         arrayLine.requestFocus();
         if (runsFromApplet)
         {
            if (isSpecial)
              ss.sortInfo[ss.HEAP].setData(arrayString, compCt, exchangeCt);
            else
              ss.sortInfo[ss.HEAP].setData(copy, compCt, exchangeCt);
            if (table != null)
              table.update(ss.HEAP, ss.sortInfo);
         }
         MessageBox mb = new MessageBox(ss, this, "Information",
                                        "Heapsort complete.", "information.gif");
      }
      stop();
   }

   private void noGraphicsHeapsort()
   {
      noGraphicsBuildHeap();
      for(int k = A.length - 1; k > 0; k--)
      {
         exchangeCt++;
         int temp = A[0];
         A[0] = A[k];
         A[k] = temp;
         heapSize--;
         noGraphicsHeapify(0);
      }
   }

   private void noGraphicsBuildHeap()
   {
      heapSize = A.length;
      for(int j = A.length / 2 - 1; j >= 0; j--)
         noGraphicsHeapify(j);
   }

   private void noGraphicsHeapify(int i)
   {
      int l = 2 * i + 1;
      int r = 2 * i + 2;
      int max;
      compCt++;
      if ((l < heapSize) && (A[l] > A[i]))
        max = l;
      else
        max = i;
      compCt++;
      if ((r < heapSize) && (A[r] > A[max]))
        max = r;
      compCt++;
      if (max != i)
      {
         exchangeCt++;
         int temp = A[i];
         A[i] = A[max];
         A[max] = temp;
         noGraphicsHeapify(max);
      }
   }

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

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

}