当字符串的长度不同时，基数排序会错误地对字符串数组进行排序

Question

所以我目前正在尝试对 Java 中的给定字符串数组进行排序。我使用基数排序将时间复杂度保持在 O(N+K)。 N是数组的长度，k是所有字符的长度。我的意图是排序算法应该按照数字顺序首先出现的数字进行排序，然后按字母顺序排列任何字母。因此，如果输入数组是 {"cd", "12", "ab"}，则排序结果将类似于 {"12", "ab", "cd"}。我的问题是处理不同长度的字符串。为了补偿不同的长度，我通过在每个字符串的末尾添加空格来预处理数据，使每个字符串的长度相同。但是，在实际的排序过程中，这会导致字符串的顺序不正确。我一直在调试，我知道与处理人工空间的排序算法相关的问题。在实际排序时，我使用哈希映射来确定所有字符的优先级。不知道如何解决这个问题。我在相同长度的字符串数组上对其进行了测试，并且排序正确。所以问题肯定是处理空间。我该如何解决？

import java.util.HashMap;
public class StringSort {

    public static void main(String[] args) {
        String[] arr = {"apple", "beans", "cool5407", "algorithm", "number", "2021", "cs"};
        //String[] arr = {"34", "45", "23", "67","12", "ab", "56"};
        System.out.print("Initial Array: ");
        print(arr);
        radixSort(arr);
        
    }
    
    static void radixSort(String[] arr)
    {       
        /*If initial list has nothing in it, then ignore it.
         * If initial list has only 1 item in it, then its already sorted.
         * If it has more than 1 item, then sorting may be required. */      
        if(arr.length > 1)
        {
                        
            //Find Longest String
            int maxLength = 0;
            for(int i = 0; i < arr.length; i++)
            {
                if(arr[i].length() > maxLength)
                    maxLength = arr[i].length();
                
            }
            
            System.out.println("Max Length : " + maxLength);
            
            //Process Strings to make them all same length
            for(int STRIndex = 0; STRIndex < arr.length; STRIndex++)
            {
                if(arr[STRIndex].length() < maxLength)
                {
                    while(arr[STRIndex].length() < maxLength)
                    {
                        arr[STRIndex] = arr[STRIndex] + " ";
                    }
                    System.out.println("Remade String: [" + arr[STRIndex] + "] " + "Length: " + arr[STRIndex].length());
                }
                
            }
            
            //Sort by letter column via iterating
            for(int column = 0; column < maxLength; column++)
            {
                System.out.println("Sotring Column: " + column);
                countingSort(arr, column);
            }
            
            //Print Final Result
            System.out.print("Final Result: ");
            print(arr);
            
        }
    }// End of Radix Sort
    
    static void countingSort(String[] arr, int letterColumn)
    {
        int NUM_CHARACTERS = 37; //Number of Unique Characters that can be found in strings
        
        //Create Map to Map Letters to Numbers
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        //Map Numbers to Values (Higher Numbers belong in front)
        map.put(' ', 0); map.put('0',1); map.put('1',2); map.put('2',3); map.put('3',4); map.put('4',5); map.put('5',6); map.put('6',7); 
        map.put('7',8); map.put('8',9); map.put('9',10);
        //Map Letters to Values (Higher Numbers belong in front)
        map.put('a',11); map.put('b',12); map.put('c',13);  map.put('d',14); map.put('e',15); map.put('f',16); map.put('g',17); 
        map.put('h',18); map.put('i',19); map.put('j',20); map.put('k',21); map.put('l',22); map.put('m',23); map.put('n',24);
        map.put('o',25); map.put('p',26); map.put('q',27); map.put('r',28); map.put('s',29); map.put('t',30); map.put('u',31); 
        map.put('v',32);map.put('w',33); map.put('x',34); map.put('y',35); map.put('z',36); 
        
        String[] result = new String[arr.length];
        int[] count = new int[NUM_CHARACTERS];
        
        print(arr);
        
        
        //Store number of instances of each letter/number in a given column for each string
        for(int index = 0; index < arr.length; index++)
        {
            String currentString = arr[index];//Get Current String          
            int currentChar = map.get(currentString.charAt(letterColumn)); //Get int value of the Current Character
            count[currentChar]++; //Count the instance
            
        }
        
        //Edit count[index] so it contains position of digit in result
        for(int index = 1; index < NUM_CHARACTERS; index++)
        {
            count[index] += count[index-1];
        }
        
        //Create Result
        for(int index = arr.length - 1; index >= 0; index--)
        {
            String currentString = arr[index]; //Get Current String 
            int currentChar = map.get(arr[index].charAt(letterColumn)); //Get int value of the Current Character
            
            result[count[currentChar]-1] = arr[index]; //Set Character in Result to be sorted element
            count[currentChar]--;//Subtract from the current character count
            
        }
        
        //Override original arr[] to that it contains new array
        for(int index = 0; index < arr.length; index++)
        {
            arr[index] = result[index];
        }
        
    }//End of Counting Sort
    
    
    static void print(String[] arr)
    {
        System.out.print("[");
        //Print Final Result
        for(int index = 0; index < arr.length; index++)
        {
            System.out.print(arr[index] + ", ");
        }
        System.out.print("]");
        System.out.println();
    }
    
}

Answer 1

问题

当前代码也不适用于相同长度的输入。

String[] arr = {"11", "20"};

原因

            //Sort by letter column via iterating
            for(int column = 0; column < maxLength; column++)

当前代码从第一个（左）移动到最后一个（右）
这将导致当前代码最终根据最后一个索引进行排序（因此将覆盖到目前为止所做的更改）。

建议

在计数排序的每次迭代中，索引应该从最后（右）移动到第一个（左）上面的代码应该改为

//Sort by letter column via iterating in reverse order
for (int column = maxLength - 1; column >= 0; column--)

或者，如果需要从左向右移动，则根据到目前为止排序创建子分段并对这些子分段递归排序。（永远不要改变首字母的顺序）

工作简化代码

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class StringSort {

    private final Map<Character, Integer> order;
    private final int charCount;

    public StringSort() {
        String characters = " 0123456789abcdefghijklmnopqrstuvwxyz";
        order = Collections.unmodifiableMap(IntStream.range(0, characters.length()).boxed()
            .collect(Collectors.toMap(characters::charAt, Function.identity())));
        charCount = characters.length();
    }

    public static void main(String[] args) {
        String[] arr = {"apple", "beans", "cool5407", "algorithm", "number", "2021", "cs"};
        StringSort stringSort = new StringSort();
        stringSort.radixSort(arr);
    }

    static void print(String prefix, String[] input) {
        System.out.println(prefix + Arrays.deepToString(input));
    }

    void radixSort(String[] input) {
        print("Initial Array: ", input);

        if (input.length < 2) {
            return;
        }

        int maxLength = Arrays.stream(input).map(s -> s.length())
            .max(Comparator.comparingInt(Integer::intValue)).get();
        System.out.println("Max Length : " + maxLength);

        input = Arrays.stream(input)
            .map(s -> s + new String(new char[maxLength - s.length()])
                .replace("[=13=]", " "))
            .toArray(String[]::new); // repeat " "
        print("Filled Array: ", input);

        //Sort by letter column via iterating
        for (int column = maxLength - 1; column >= 0; column--) {
            System.out.println("Sotring by column: " + column);
            countingSort(input, column);
            print("Updated State: ",  input);
        }
        print("Final Result: ", input);
    }

    void countingSort(String[] input, final int letterColumn) {
        final int stringCount = input.length;
        String[] result = new String[input.length];
        int[] counter = new int[charCount];

        Arrays.stream(input).map(s -> order.get(s.charAt(letterColumn))).forEach(c -> counter[c]++);

        IntStream.range(1, order.size()).forEach(i -> counter[i] += counter[i - 1]);

        for (int index = stringCount - 1; index >= 0; index--) {
            int currentChar = order.get(input[index].charAt(letterColumn));
            result[counter[currentChar] - 1] = input[index];
            --counter[currentChar];
        }

        IntStream.range(0, stringCount).forEach(i -> input[i] = result[i]);
    }
}

当字符串的长度不同时，基数排序会错误地对字符串数组进行排序

Radix sort incorrectly sorts an array of strings when they have different lengths

java

arrays

sorting

string

radix

问题

原因

建议

工作简化代码