爲什麼這種排序可視化如此緩慢？

昨天我看到一些關於比較排序算法的很酷的視頻。我決定寫同樣的內容，但剛開始後我發現這種排序可視化非常慢。與此代碼爲什麼這種排序可視化如此緩慢？

import javax.swing.*; 
import java.awt.*; 

class ViewSort extends JFrame implements Runnable{ 
    private int N = 100; 
    private int max = 500; 
    private int[] array; 
    private Thread th; 
    private DrawPanel drawPanel; 
    long startTime; 
    int iter = 0; 

    public ViewSort(){ 
     init(); 
    } 

    private void init(){ 
     this.setSize(N*2 + 50, max + 50); 
     this.setLayout(new GridLayout(1, 1)); 
     this.setResizable(false); 
     this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); 
     this.setTitle("Stupid Sort Viewer"); 
     drawPanel = new DrawPanel(); 
     this.getContentPane().add(drawPanel); 
     array = generateArray(N, max); 
     th = new Thread(this); 
     th.start(); 
     startTime = System.nanoTime(); 
    } 

    public static int[] generateArray(int N, int max){ 
     int[] array = new int[N]; 
     for(int i = 0; i < N; i++){ 
      array[i] = (int) (Math.random() * max); 
     } 
     return array; 
    } 

    @Override 
    public void run(){ 
     for(int i = 0; i < N - 1; i++){ 
      iter++; 
      if(array[i] > array[i + 1]){ 
       int tmp = array[i]; 
       array[i] = array[i + 1]; 
       array[i + 1] = tmp; 
       i = 0; 
      } 
      try{ 
       th.sleep(1); 
      }catch(InterruptedException ie){ 
       ie.printStackTrace(); 
      } 
      drawPanel.repaint(); 
     } 
     System.out.print((System.nanoTime() - startTime)/1000/1000/1000); 
     System.out.print(" seconds left on "); 
     System.out.print(iter); 
     System.out.print(" iterations on sorting an array of "); 
     System.out.print(N); 
     System.out.print(" integers"); 
    } 

    private void printArray(){ 
     StringBuilder sb = new StringBuilder(); 
     for(int i = 0; i < N; i++){ 
      sb.append(array[i]); 
      sb.append(" "); 
     } 
     System.out.println(new String(sb)); 
    } 

    class DrawPanel extends JPanel{    
     public void paintComponent(Graphics g){ 
      super.paintComponent(g); 
      g.setColor(Color.white); 
      g.fillRect(0, 0, getWidth(), getHeight()); 
      g.setColor(Color.black); 
      for(int i = 0; i < N; i++){ 
       g.fillRect(i*2 + 25, getHeight() - array[i], 2, array[i]); 
      } 
     } 
    } 

    public static void main(String[] args){ 
     SwingUtilities.invokeLater(new Runnable(){ 
      public void run(){ 
       new ViewSort().setVisible(true); 
      } 
     }); 
    } 
}

與該代碼我有一個像上排序100點的整數
P.S.的陣列上留下116441次迭代
170秒輸出
我知道排序是最慢的（除了隨機排序），但不是這樣！

來源

2015-07-11 Aero

擺脫'paintChildren'方法並將邏輯放在'paintComponent'方法中。在做任何自定義繪畫之前調用'super.paintComponent' – MadProgrammer

@MadProgrammer super.paintComponent在具有哪個參數的構造函數中？ – Aero

調用'super.paintComponent（g）;'在'paintComponent'方法的開頭 – MadProgrammer

i = 0;

你有兩個問題，既造成上述行：

1）你發現兩個號碼不按順序每次回到0，然後重新進行比較。但是，如果您交換24和25的值，則您已經知道24之前的值是正確的，因此您只需要返回並比較23和24的值。

2）您的值設爲零，但隨後的for循環的增量「我」的一個，所以你永遠只開始在索引1比較，所以第一個值將始終是亂序（除非它隨機發生是最小的值）。

您可以通過使用解決這兩個問題：

i = Math.max(-1, i - 2);

注：

儘管該類將與paintChildren（）方法中的繪畫代碼，代碼真的應該被移動到的paintComponent工作（）方法由MadProgrammer建議。自定義繪畫應該在paintComponent（）方法中完成。 Swing使用paintChildren（）方法繪製添加到面板的Swing組件。

來源

2015-07-12 00:06:50 camickr

此問題不是排序。我把所有的圖形都放在了paintComponent中，它的開始和結果都好了5％。順便說一句：那種真正排序數組爲4341178 NANOS。 – Aero

@Aero，就是這樣。你的代碼會在你所做的循環的每一次迭代中休眠。您正在執行'116441'迭代，這意味着您需要117秒才能運行代碼，因爲您每次迭代都需要睡眠1ms。然後，您需要時間重新繪製圖形117441次。減少迭代次數並減少排序時間。 – camickr

圖形 - 170000000000納米，非圖形 - 4341178納米。圖形使它慢了39159.8倍。我對這種巨大的過載提出了要求。 – Aero

爲什麼這種排序可視化如此緩慢？

回答

相關問題