插入排序字符串

Question

我读取了一个包含城市及其人口的文件，我正在尝试使用插入排序按字母顺序对城市进行排序。问题是它对除第一个元素之外的所有元素进行排序。未排序列表中的第一个值保留在已排序列表的索引 [0] 中。这是代码：

    int i, j;
    String v;
    for (i = 1; i < cities.size()-1; i++)
    {
        v = cities.get(i);
        j = i;
        while (cities.get(j-1).compareToIgnoreCase(v) > 0 && j >=2)
        {
            cities.set(j, cities.get(j-1));
            j--;
        }
        cities.set(j, v);
    }

知道哪里出了问题吗？

谢谢。

Answer 1

你可能想要 for (i = 0; i < cities.size(); i++).

访问数组和列表从0开始计数，但list/array的实际大小从1开始计数。

示例：要访问大小为 1 的数组 a 的第一个（也是唯一一个）元素，您可以使用 a[0].

Answer 2

首先，这个...

for (i = 1; i < cities.size()-1; i++)

应该是……

for (i = 1; i < cities.size(); i++)

第二，这个...

j = i;

应该是……

int j = i - 1;

三、这个...

while (cities.get(j - 1).compareToIgnoreCase(v) > 0 && j >= 2) {

一团糟。在确定该值是否实际可访问（即 j 是否在 List 的范围内）之前，您尝试从 List 访问该值，并且可能应该更像。 ..

while ((j > -1) && (cities.get(j).compareToIgnoreCase(key) > 0)) {

说了这么多，这意味着 cities.set(j, cities.get(j - 1)); 需要变成 cities.set(j + 1, cities.get(j));，cities.set(j, v); 需要变成 cities.set(j + 1, key);

类似...

    List<String> cities = new ArrayList<>(25);
    cities.add("D");
    cities.add("C");
    cities.add("B");
    cities.add("A");

    for (int i = 1; i < cities.size(); i++) {
        String key = cities.get(i);
        int j = i - 1;
        while ((j > -1) && (cities.get(j).compareToIgnoreCase(key) > 0)) {
            cities.set(j + 1, cities.get(j));
            j--;
        }
        cities.set(j + 1, key);
    }

例如...

插入排序字符串

Insertion Sort Strings

java

sorting

string

insertion-sort