比较排序算法

Question

我实现了不同类型的排序（冒泡、插入、选择）。现在我想比较它们的实现方式，对于每种排序，我想按照以下方式进行比较（这里以冒泡排序为例）：

例如，这是我的冒泡排序：

private static int[] bubbleSort(int[] tabToSort) {
   int [] tab = tabToSort.clone();
   boolean tabSort = false;
   while(!tabSort){
        tabSort = true;
        for(int i = 0; i < tab.length -1; i++){
            if(tab[i]> tab[i+1]){
                int temp = tab[i+1];
                tab[i+1] = tab[i];
                tab[i] = temp;
                tabSort = false;
            }
        }
    }
    return tab;
}

我启动了GUI，并在上面放置了1000个随机点和线 y=x：

@Override
    public void paintComponent (Graphics g){
        super.paintComponent(g);
        Graphics2D g2d  = (Graphics2D) g;
        g2d.setColor(Color.BLACK);
        Dimension size = getSize();
        Insets  insets= getInsets();
        int w =  size.width - insets.left - insets.right;
        int h =  size.height - insets.top - insets.bottom;
        
        g2d.drawLine(size.width ,0, 0, size.height);
        Random r = new Random();

        for (int i  =0; i < 1000; i++) {
           int x = Math.abs(r.nextInt()) % w;
           int y = Math.abs(r.nextInt()) % h;
           Point p = new Point(x, y);
           g2d.drawLine(p.x, p.y, p.x, p.y);
        }
    }

这是我所做的: 现在我陷入了困境，不知道如何开始。有人能告诉我实现它的步骤/提示吗？

谢谢 :)

- user2336315

Answer 1

您必须定义点的含义。从动画中可以看出，y轴代表一个值，而x轴代表该值在数组中的位置。

在您的paint方法中，您需要遍历项目列表并绘制一个点，其中x点是数组中的位置，y点是y轴上的位置。假设这些值在已知范围内。

此外，请记住图形中的y轴从顶部开始为0，因此您可能需要将值转换为坐标（具体取决于您想要的外观）。

- Steve

Answer 2

我已经为我的学士论文完成了这个，并且我是这样做的（它不完美，但可能会帮助你）:

（下面的代码中删除了一些不重要的方法/函数。 它主要是为了说明我如何将其可视化。 例如，您可以使用简单的java.awt.Point替换GRectangle类。）

初始化方法为您提供了一个示例，说明如何查找数据的最大值和最小值，以便您知道如何将数据值转换为坐标。

public class DotVisualisation extends Visualisation {

    private ArrayList<GRectangle> m_points;

    private Comparable[] m_data;

    private Comparable m_maxValue;
    private Comparable m_minValue;

    private int MAX_HEIGHT; // max height in pixels of visualization

    /**
     * Creates a new DotVisualisation.<br>
     * <br>
     * This class is a runnable JComponent that will visualize data as a function. 
     * The visualisation will plot the data with X and Y coordinates on the window. 
     * The X coordinate of the point is index of the dataelement. 
     * The Y coordinate of the point is relative to the value of the dataelement.<br>
     * <br>
     * This visualisation should be used for medium and large arrays.
     * 
     * @author David Nysten
     */
    public DotVisualisation()
    {
        m_points = new ArrayList<GRectangle>();
        MAX_HEIGHT = 150;
    }

    /**
     * Returns the maximum supported dimension by this visualisation.
     * 
     * @return The supported dimension.
     */
    public static int getSupportedDimension()
    {
        return 1;
    }

    @Override
    public Dimension getMaximumSize() 
    {
        return getPreferredSize();
    }

    @Override
    public Dimension getPreferredSize() 
    {
        return new Dimension(m_points.size() + 2, MAX_HEIGHT + 6);
    }

    @Override
    public Dimension getMinimumSize() 
    {
        return getPreferredSize();
    }

    @Override
    public void paintComponent(Graphics g)
    {
        for(int i = 0; i < m_points.size(); ++i)
            m_points.get(i).paintComponent(g);
    }

    private void swap(int index, int index2) { // See below }

    private void initialise()
    {
        findMinimum();
        findMaximum();
        m_points.clear();
        double multiplier;
        int x = 0, y = 0, h;
        for(int i = 0; i < m_data.length; ++i)
        {
            if(m_data[i].compareTo(-1) <= 0)
                h = 0;
            else
            {
                Integer value = (Integer) m_data[i];
                Integer min = (Integer) m_minValue;
                Integer diff = (Integer) m_maxValue - min;
                multiplier = MAX_HEIGHT / diff.doubleValue();
                h = (int) ((value - min) * multiplier);
            }
            y = (int) (MAX_HEIGHT - h);
            GRectangle r = new GRectangle(x, y, 1, 1); // 1, 1 = width and height
            r.setColor(Color.BLACK);
            m_points.add(r);
            ++x;
        }
    }

    private void findMaximum()
    {
        Comparable max = null;
        if(m_data.length > 0)
        {
            max = m_data[0];
            for(int i = 1; i < m_data.length; ++i)
                if(m_data[i].compareTo(max) > 0)
                    max = m_data[i];
        }
        m_maxValue = max;
    }

    private void findMinimum()
    {
        Comparable min = null;
        if(m_data.length > 0)
        {
            min = m_data[0];
            for(int i = 1; i < m_data.length; ++i)
                if(m_data[i].compareTo(min) < 0)
                    min = m_data[i];
        }
        m_minValue = min;
    }
}

请注意： 在高度为150像素的情况下可视化0到150之间的整数是很简单的。但在同样高度下可视化介于565和3544545之间的一组整数就不那么容易了。

附注：该代码使用输入数组中元素的索引作为X坐标。 附注：该类保留对输入数组（m_data变量）的引用，但这当然是不必要的，您只需要它来初始化您的点。 附注：我的“可视化”类是所有可视化所扩展的基本JPanel。 附注：上述代码仅适用于正整数，因此可能需要额外编码来处理负整数; )。

然后为了可视化算法的操作，我使用了观察者模式。例如，冒泡排序的算法如下：

    for(int i = 0; i < size(); ++i)
        for(int j = 1; j < size(); ++j)
            if(greaterThan(j - 1, j))
                swap(j - 1, j);

函数swap的定义如下（再次简化版）：

protected void swap(int index1, int index2)
{
    if(index1 != index2)
    {
        incrementSwap(); // counting swaps and visualizing counter

        m_command.clear();
        m_command.setAction(Action.SWAP);
        m_command.addParameter(index1);
        m_command.addParameter(index2);
        setChanged();
        notifyObservers(m_command);

        E temp = m_data[index1];
        m_data[index1] = m_data[index2];
        m_data[index2] = temp;
    }
}

我在通知我的观察者（可视化）发生了索引1和索引2的交换。m_command变量是Command类的一个实例（我自己编写的），它只是可视化所需信息的包装器。这些信息包括：发生的操作和相关信息（例如交换操作的索引）。因此，在可视化中，我也交换了这些索引上的GRectangle以及它们的X坐标。

private void swap(int index, int index2)
{
    if(index == index2)
        return;
    GRectangle r1 = m_points.get(index);
    GRectangle r2 = m_points.get(index2);

    int tempX = r1.getX();
    r1.setLocation(r2.getX(), r1.getY());
    r2.setLocation(tempX, r2.getY());

    m_points.set(index, r2);
    m_points.set(index2, r1);
}

您可以添加类似于这样的行：

        try {
            Thread.sleep(100);
        } catch(InterruptedException ignore) {}

在继续执行之前让线程休眠100毫秒。如果可视化过快，这可能会很有用。

因此，对于一个包含随机整数的数组，代码可能如下所示：

排序后： （当然，这不是一条直线，因为输入数组中的值在本例中是随机生成的）

如果你必须像我一样允许多个算法与同一可视化进行交互，我建议你将可视化类和算法类分开，并使用观察者模式来让可视化在发生动作（设置、交换等）时更新。然后你可以为比较创建类似于这样的东西；

http://i445.photobucket.com/albums/qq179/ultddave/DotVisualizationMany_zps63269d2a.png http://i445.photobucket.com/albums/qq179/ultddave/DotVisualizationMany2_zps65e96fa9.png

祝你好运！

- ultddave

Answer 3

最简单的方法是将您的绘图方法转换为一个使用预定义的List点作为参数而不是随机点的方法。在每次排序方法的迭代中，将排序后的数组传递到绘图方法中并重绘点。

- svz

Answer 4

您需要

1. 创建一个成员变量为随机值的 int[] 数组。我们称其为 data。你可能想先从固定的数组大小和范围为 100 开始。当简单版本可用时，可以调整值以适应窗口大小。甚至更好的是保持固定大小和范围，并仅根据 paintComponent 中可用的空间进行缩放，使行为独立于窗口大小。
2. 将 paintComponent 更改为循环遍历 data。循环索引是您的 x 值，data[x] 确定 y 值。
3. 测试代码是否仍绘制初始随机数组。现在它只能在左上角，不要担心，当动画工作时可以修复它。
4. 您需要在排序方法的最内层循环中添加某种 sleep() 调用，以便您有机会观察步骤。否则，即使是冒泡排序也会太快而无法观察到。我建议从一秒钟开始（参数值为 1000）。等一切都正常后再加快速度。
5. 在新线程中启动 bubbleSort 方法，并确保您的组件在每个步骤中都被重绘。这可能是最棘手的部分。也许把组件交给 bubbleSort 方法（或将 bubbleSort 设为组件的非静态方法），并让它在每个步骤时请求 repaint()（幸运的是，这是 Swing 中仅有的几个线程安全方法之一）。
6. 微调您的代码：通过乘以可用空间然后除以数组大小或值范围来缩放 x 和 y 坐标。根据需要调整睡眠时间。添加对不同排序算法的支持....

如果有任何步骤不清楚，请添加注释。

- Stefan Haustein