Java 使用字符串数组列表进行插入排序

Question

我有一个关于排序的作业，它要求我通过将以相同字母开头的字母放在 group/zones 中并按字母顺序对该组进行排序来对随机单词列表进行排序。我的代码对单词进行了排序，但我的问题是某些单词发生了变化。例如，而不是输出为

angela
APPLE
A苹果
a苹果
Baboon
B全部
C在
cat
PINK
P墨水
S特维

我的输出为：

苹果
苹果
苹果
苹果
球
球
猫
猫
粉色
粉色
史蒂夫

如您所见，有些单词已经更改，在某些情况下，大写字母的单词变成了小写字母，例如“cat”，我似乎找不到我的错误所在。

这是我的排序代码；我的 driver class 只接受随机单词列表：

import java.util.ArrayList;
import java.util.Collections;

public class ZoneSort 
{


ArrayList[] arrayOfZones;
ArrayList<String> words; 

public ZoneSort(ArrayList<String> words)
{
    arrayOfZones = new ArrayList [ 26 ];
    
    for(int index = 0; index < 26;index++)
        arrayOfZones [ index ] = new ArrayList();
    
    this.words = words; 
    
    putWordsIntoZones();
}

private  void putWordsIntoZones()
{
    for(String word: words)
    {
        int index = Character.toLowerCase(word.charAt(0)) - 97; 
        ArrayList<String> zoneAtIndex = arrayOfZones[index];
        zoneAtIndex.add(word);
    }
}

public  void sortTheArrayOfZones() 
    {
        for(ArrayList<String> zone : arrayOfZones )
        {
            sortZone(zone);
        }
    }


private  void sortZone(ArrayList<String> zone)
{
        for(int i = 1; i < zone.size(); i++)
        {
            String key = zone.get(i);
            int j = i-1;
            while(j>=0 && key.compareTo(zone.get(j)) > 0)
            {
                String x = zone.get(j+1);
                zone.set(j, x);
                j--;
            }
            
            String x = zone.get(j+1);
            x = key;
        }
}   

public   void printArrayOfZones()
{
    System.out.println("The sorted words are");
    for(ArrayList<String> zone:arrayOfZones)
    {
        for(String word: zone)
        {
            
            System.out.println(word);
        }
    }
}

Answer 1

阅读你的代码并查看你的结果，你的代码似乎覆盖了值而不是交换它们。要解决此问题，您需要查看函数排序。我已经修改了你的代码，这样你就可以交换两个元素而不是覆盖：

private  void sortZone(ArrayList<String> zone){
    for(int i = 1; i < zone.size(); i++){
        String key = zone.get(i);
        int j = i-1;
        while(j>=0 && key.compareTo(zone.get(j)) > 0){
            String x = zone.get(j+1);
            zone.set(j+1,zone.get(j)); // line added
            zone.set(j, x);
            j--;
        }
        String x = zone.get(j+1);
        x = key;
    }
}

希望这能解决您的问题。

Answer 2

如果我将您的 sortZone 实现与参考插入排序实现进行比较，例如 https://www.baeldung.com/java-insertion-sort 我看到以下差异 - 请参阅内联评论

        for(int i = 1; i < zone.size(); i++)
        {
            String key = zone.get(i);
            int j = i-1;

// The sort order is reversed.
// You've used "key > zone[j]" when it should be "key < zone[j]"

            while(j>=0 && key.compareTo(zone.get(j)) < 0)
            {
// This is copying items backwards, towards the beginning of the array. 
//                String x = zone.get(j+1);
//                zone.set(j, x);
// It should be copying items forwards, towards the end, to make room for "key"
// Like this:
                String x = zone.get(j);
                zone.set(j+1, x);
                j--;
            }
            
// You should be setting zone[j+1] = "key" - this does not do it: 
//            String x = zone.get(j+1);
//            x = key;
// This is how you set a value in a list:
            zone.set(j+1, key);
          
        }

Java 使用字符串数组列表进行插入排序

Java Insertion Sorting with ArrayLists of Strings

java

arrays

sorting

arraylist

insertion-sort