java - Shaker排序的条形演示一次对所有条形进行排序-Java

Question

我在接受的答案中找到了这段代码:Java swing repainting while computing: animating sorting algorithm

我一直在尝试修改它，使其适用于摇床排序，但我的代码一次性对整个事情进行排序。

import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Arrays;
import java.util.Collections;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
import javax.swing.Timer;

public class ShakerSortAnimate extends JPanel {
private static final int NUM_OF_ITEMS = 20;
private static final int DIM_W = 400;
private static final int DIM_H = 400;
private static final int HORIZON = 350;
private static final int VERT_INC = 15;
private static final int HOR_INC = DIM_W / NUM_OF_ITEMS;

private JButton startButton;
private Timer timer = null;
private JButton resetButton;

Integer[] list;
int currentIndex = NUM_OF_ITEMS - 1;

public ShakerSortAnimate() {
    list = initList();

    timer = new Timer(200, new ActionListener() {
        public void actionPerformed(ActionEvent e) {
            if (isSortingDone()) {
                ((Timer) e.getSource()).stop();
                startButton.setEnabled(false);
            } else {
                sortOnlyOneItem();
            }
            repaint();
        }
    });

    //button to run the program
    startButton = new JButton("Start");
    startButton.addActionListener(new ActionListener() {
        public void actionPerformed(ActionEvent e) {
            timer.start();
        }
    });

    //resets screen
    resetButton = new JButton("Reset");
    resetButton.addActionListener(new ActionListener() {
        public void actionPerformed(ActionEvent e) {
            list = initList();
            currentIndex = NUM_OF_ITEMS - 1;
            repaint();
            startButton.setEnabled(true);
        }
    });
    add(startButton);
    add(resetButton);
}

//boolean checks when array is sorted
public boolean isSortingDone() {
    return currentIndex == 0;
}

//initializes the array
public Integer[] initList() { 
    Integer[] nums = new Integer[NUM_OF_ITEMS];
    for (int i = 1; i <= nums.length; i++) {
        nums[i - 1] = i;
    }
    Collections.shuffle(Arrays.asList(nums)); //shuffles array
    return nums;
}

//draws each bar
public void drawItem(Graphics g, int item, int index) {
    int height = item * VERT_INC;
    int y = HORIZON - height;
    int x = index * HOR_INC;
    g.fillRect(x, y, HOR_INC, height);
}


//My shaker sort code
public void sortOnlyOneItem()
{
    boolean swapped = true;
    int start = 0;
    int end = currentIndex;

    while (swapped==true)
    {
        swapped = false;

        for (int i = start; i < end; ++i)
        {
            if (list[i] > list[i + 1])
            {
                int temp = list[i];
                list[i] = list[i+1];
                list[i+1] = temp;
                swapped = true;
            }
        }

        if (swapped==false)
            break;

        swapped = false;

        end = end-1;

        for (int i = end; i >=start; i--)
        {
            if (list[i] > list[i+1])
            {
                int temp = list[i];
                list[i] = list[i+1];
                list[i+1] = temp;
                swapped = true;
            }
        }

        start = start + 1;
    }

   currentIndex--; //currentIndex is updated each time shaker sort runs
}






//draws all bars
@Override
protected void paintComponent(Graphics g) {
    super.paintComponent(g);
    for (int i = 0; i < list.length; i++) {
        drawItem(g, list[i], i);
    }
}

@Override
public Dimension getPreferredSize() {
    return new Dimension(DIM_W, DIM_H);
}

public static void main(String[] args) {
    SwingUtilities.invokeLater(new Runnable() {
        public void run() {
            JFrame frame = new JFrame("Sort");
            frame.add(new ShakerSortAnimate());
            frame.pack();
            frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
            frame.setLocationRelativeTo(null);
            frame.setVisible(true);
        }
    });
}
  }

我确实意识到我的 Shaker Sort 代码必须为每次比较执行此操作，而不是整个比较，但老实说，我什至不知道如何开始编写代码。如果这里有人知道如何在摇床排序中对每个比较进行编码，你能帮我吗？

顺便说一句，我发布了整个内容，因此您也可以尝试运行它。

提前致谢!

Answer 1

所以，你需要这个...

public void sortOnlyOneItem()
{
    boolean swapped = true;
    int start = 0;
    int end = currentIndex;

    while (swapped==true)
    {
        swapped = false;

        for (int i = start; i < end; ++i)
        {
            if (list[i] > list[i + 1])
            {
                int temp = list[i];
                list[i] = list[i+1];
                list[i+1] = temp;
                swapped = true;
            }
        }

        if (swapped==false)
            break;

        swapped = false;

        end = end-1;

        for (int i = end; i >=start; i--)
        {
            if (list[i] > list[i+1])
            {
                int temp = list[i];
                list[i] = list[i+1];
                list[i+1] = temp;
                swapped = true;
            }
        }

        start = start + 1;
    }

   currentIndex--; //currentIndex is updated each time shaker sort runs
}

每次调用仅运行一次。它现在没有这样做，因为如果是 while-loop，那么我们需要摆脱它。

这样做时，只有在 swapped 为 true 时才应运行第二个循环，并且仅在 时才应递减 currentIndex swapped 仍然是 true

这给我们带来了类似......

public void sortOnlyOneItem() {
    boolean swapped = true;
    int start = 0;
    int end = currentIndex;

    for (int i = start; i < end; ++i) {
        if (list[i] > list[i + 1]) {
            int temp = list[i];
            list[i] = list[i + 1];
            list[i + 1] = temp;
            swapped = true;
        }
    }

    if (swapped) {
        swapped = false;

        end = end - 1;

        for (int i = end; i >= start; i--) {
            if (list[i] > list[i + 1]) {
                int temp = list[i];
                list[i] = list[i + 1];
                list[i + 1] = temp;
                swapped = true;
            }
        }
    }

    if (swapped) {
        currentIndex--; //currentIndex is updated each time shaker sort runs
    }
}

这仍然不太正确，因为两个 for 循环可以进行多项更改。

相反，我们需要一次迭代，最多只会进行两次更改，一次在开始，一次在结束

这可能看起来像......

protected void swap(int a, int b) {
    int tmp = list[a];
    list[a] = list[b];
    list[b] = tmp;
}

int endIndex = NUM_OF_ITEMS - 1;

//My shaker sort code
public void sortOnlyOneItem() {

    int startIndex = 0;
    while (startIndex < NUM_OF_ITEMS - 1 && list[startIndex] < list[startIndex + 1]) {
        startIndex++;
    }

    if (startIndex < NUM_OF_ITEMS - 1 && list[startIndex] > list[startIndex + 1]) {
        swap(startIndex, startIndex + 1);
        int end = endIndex;
        while (end > 0 && list[end - 1] < list[end]) {
            end--;
        }
        if (end > 0 && list[end - 1] > list[end]) {
            swap(end - 1, end);
        } else {
            endIndex--;
        }
    } else {
        endIndex = 0;
    }
}

现在，这基本上会查找可能会更改的两个索引(在 start 和 end 处)，并在可能的情况下交换它们。当您可以从 start 迭代到末尾而不进行任何更改时，排序就完成了。

现在，我不声明这是否准确，只是它尽力模仿您提供的算法