Java字符串去重插入排序遇到首字母相同内容时运行异常求助

原代码核心问题 #

• 去重逻辑错误：遇到重复元素时执行break直接终止整个排序循环，后续所有未处理元素都会被丢弃，应该改为continue仅跳过当前重复元素
• 插入逻辑缺失：仅将当前元素和已排序数组的最后一位对比，没有向前遍历所有已排序元素找到正确的插入位置，这就是首字母相同的单词无法正确排序的核心原因
• 结果数组冗余：初始化排序数组长度和原数组一致，去重后剩余位置会保留null值，输出时会出现无效内容
• 索引用错：遍历原数组的索引i不能直接用来定位已排序数组的位置，已排序数组的有效长度应该用单独变量记录

修复后可运行代码 #

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        String[] words = {"big", "ALL", "zebra", "END", "great", "FOX", "quit", "episode", "zebra", "big", "all", "1"};
        System.out.println("Unsorted array: " + Arrays.toString(words));
        stringInsertionSort(words);
    }

    public static void stringInsertionSort(String array[]) {
        // 最坏情况无重复，和原数组等长
        String[] sortedArray = new String[array.length];
        sortedArray[0] = array[0];
        // 记录已排序的有效元素个数
        int sortedCount = 1;

        for (int i = 1; i < array.length; i++) {
            String current = array[i];
            // 1. 去重判断：如果当前元素已存在，跳过
            boolean isDuplicate = false;
            for (int j = 0; j < sortedCount; j++) {
                // 如果需要忽略大小写去重，改为sortedArray[j].equalsIgnoreCase(current)
                if (sortedArray[j].equals(current)) {
                    isDuplicate = true;
                    break;
                }
            }
            if (isDuplicate) {
                continue;
            }

            // 2. 插入排序：从已排序数组末尾向前遍历找插入位置
            int insertPos = sortedCount;
            while (insertPos > 0 && current.compareTo(sortedArray[insertPos - 1]) < 0) {
                sortedArray[insertPos] = sortedArray[insertPos - 1];
                insertPos--;
            }
            sortedArray[insertPos] = current;
            sortedCount++;
        }

        // 3. 截取有效元素，去掉后面的null
        String[] result = Arrays.copyOf(sortedArray, sortedCount);
        System.out.println("Sorted array:   " + Arrays.toString(result));
    }
}

运行结果说明 #

测试用例运行后输出排序结果为[1, ALL, END, FOX, all, big, episode, great, quit, zebra]，符合字典序排序要求，且自动过滤了重复的big、zebra元素。如果需要忽略大小写排序，可以将compareTo替换为compareToIgnoreCase即可。

内容的提问来源于stack exchange，提问作者Cameron