java - 我怎样才能使这个插入排序方法一次运行一个步骤？

Question

我正在尝试以可视方式为该方法添加动画效果，并且我想使用计时器来控制插入排序，方法是让它每隔一段时间(100 毫秒)检查一个索引或交换一组索引。通过这种方式，我可以逐步了解它。

方法如下:

public static void sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int j = i;
        while(j > 0 && arr[j] < arr[j-1]){
            ArrayUtility.swap(j,j-1, arr);
            j--;
        }
    }
}

这样做的目的是，如果一对索引相互检查，该方法不会继续循环，它检查索引然后停止，直到允许该方法的下一部分运行 100 毫秒之后。

Answer 1

解释

记住当前的 i 和 j 索引，然后您可以随时通过提取所有可能的单个步骤轻松地暂停和恢复你的循环结构，即:

• 常规内循环迭代
• 内循环结束，推进外循环
• 外层循环结束，算法完成

我会创建一个 Sorter 类，其中包含这些索引和数组作为字段，然后您可以提供一个简单的 sortStep 方法，它只执行一个步骤并更新索引.

---

解决方案

public class Sorter {
    private final int[] values;
    private int i = 1;
    private int j = 1;

    public Sorter(int[] values) {
        this.values = values;
    }

    public int[] getValues() {
        return values;
    }

    // @returns Whether sorting algorithm has finished
    public boolean sortStep() {
        if (i >= values.length) {
            // Outer loop has finished
            return true;
        }

        if (j > 0 && values[j] < values[j - 1]) {
            // Inner loop iteration
            ArrayUtility.swap(j, j - 1, values);
            j--;
        } else {
            // Inner loop has finished, outer loop iteration
            i++;
            j = i;
        }
        return false;
    }
}

现在您可以简单地在循环中调用 sortStep 直到它完成:

int[] values = ...
Sorter sorter = new Sorter(values);

while (!sorter.sortStep()) {
    // Animate
    displayValues(values);
    Thread.sleep(100);
}

或者将该方法连接到 UI 上一些不错的暂停和恢复按钮。

---

注意事项

如果你不想治疗

• 常规内循环迭代
• 内循环结束，推进外循环

作为两个独立的步骤，但作为一个步骤，您可以简单地将 case 移出 if-else 构造并在内部迭代后直接执行:

if (j > 0 && values[j] < values[j - 1]) {
    // Inner loop iteration
    ArrayUtility.swap(j, j - 1, avaluesrr);
    j--;
}

if (j <= 0 || values[j] >= values[j - 1]) {
    // Inner loop has finished, outer loop iteration
    i++;
    j = i;
}

同样，您可以将 done 检测放在方法的末尾，让方法在真正完成时输出 true。这样，您就不必再次调用它而没有任何效果:

// Duplicated at the end of sortStep
if (i >= values.length) {
    // Outer loop has finished
    return true;
}