java - 此插入排序算法仅交换前 2 个元素并停止。我该如何解决？

Question

给定一个数组、一个开始索引和一个结束索引，按排序顺序输出数组。示例 {"c","b","d","a"} --> {"a","b","c","d"}

问题是算法只在第一个索引和它之前的索引之间执行所需的交换（如果满足交换条件）。

    public void insertionSort(String[] array, int start, int how_many_elements) { // ndx start
        for (int i = start + 1; (i < start + 1 + how_many_elements) && (i < data.length - 1); i++) { // assume in bounds
            String key = data[i];
            int j = fi;
            while (j >= 0 && key.compareTo(data[j]) < 0) { // swap
                String temp = data[j];
                data[j] = key;
                data[i] = temp;
                j--; // continue down to first element
            }
        }
    }

标签： javasortingnested

Answer 1

1. j应该是i - 1每次，而不是开始索引。
2. 在循环中，只需将下一个元素的值设置为当前元素。（这必须在循环之后再做一次。）

public void insertionSort(String[] data, int fi, int how_many_elements) {
    for (int i = fi + 1; (i < fi + 1 + how_many_elements) && (i < data.length); i++) {
        String key = data[i];
        int j = i - 1;
        while (j >= 0 && key.compareTo(data[j]) < 0) {
            data[j + 1] = data[j];
            j--;
        }
        data[j + 1] = key;
    }
}