java - 不能缩短具有大字符串数字的字符串数组

Question

我必须对仅包含数字的长字符串(长度最多 100 万个字符)的大型数据集进行排序。 还将所有字符串仅视为大的正数。

我修改了合并排序代码，如果字符串的长度在 18 以内(因此我可以将其转换为长数字以进行比较)，该代码对于大型数据集(数组大小为 200000)非常有效。

我还实现了一个理论上应该适用于任何长度的字符串(数字字符串)的逻辑。但是我的代码中存在一些小故障，不允许使用长(长度 > 18)字符串对数组进行排序。 我在下面的代码块中添加了大写注释。

注意:代码在几秒钟内成功执行了所有长度的数据集，并给出了不太正确的输出，如最后所示。

下面是我的代码:

    package algorithms;
    import java.math.BigInteger;
    import java.util.Scanner;
    public class BigSort {

    static void merge(String arr[], int l, int m, int r)
    {
        int n1 = m - l + 1;
        int n2 = r - m;

        String L[] = new String [n1];
        String R[] = new String [n2];

        for (int i=0; i<n1; ++i)
            L[i] = arr[l + i];
        for (int j=0; j<n2; ++j)
            R[j] = arr[m + 1+ j];

        int i = 0, j = 0;
        int k = l;

        while (i < n1 && j < n2){   
        if (L[i].length() <= R[j].length()){
            if(L[i].length()<=18 && R[j].length() <=18) {
                if(BigInteger.valueOf(Long.parseLong(L[i])).compareTo(BigInteger.valueOf(Long.parseLong(R[j]))) <=0){   
                    //this will convert strings to numbers and compare them.
                    //I have used it just to possibly decrease load of-
                    //comparing each characters for sorting smaller strings.
                    arr[k] = L[i];
                    i++;
                }else{
                    arr[k] = R[j];
                    j++;
                }
            }else{//THIS ELSE PART IS HAVING SOME PROBLEM.
                //if length of string is greater than 18digits
                //it will compare two string character by character to find 
                //the larger string or if they are equal.
                char[] c1 = L[i].toCharArray();
                char[] c2 = R[j].toCharArray();
                int c1leng= c1.length;
                int c2leng= c2.length;
                //int shorter= c1leng < c2leng ? c1leng : c2leng ;
                if(c1leng==c2leng){
                    for(int p=0; p<c1leng; p++){
                    if(c1[p]==c2[p]){
                        if(p == c1leng-1) {
                            arr[k] = L[i];
                            i++;
                            break;
                        }
                        continue;
                    }else if(c1[p]<c2[p]){
                        arr[k] = L[i];
                        i++;
                        break;
                    }else if(c1[p]>c2[p]){
                        arr[k] = R[j];
                        j++;  
                        break;
                    }
                    }
                }else{
                    arr[k] = R[j];
                    j++;     
                }
            }
        }else{
            arr[k] = R[j];
            j++;
        }
        k++;
        }

        while (i < n1){
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2){
            arr[k] = R[j];
            j++;
            k++;
        }
    }


    static void sort(String arr[], int l, int r)
    {
        if (l < r){
            int m = (l+r)/2;
            sort(arr, l, m);
            sort(arr , m+1, r);
            merge(arr, l, m, r);
        }
    }

    static String[] bigSorting(String[] arr) {
        sort(arr, 0, arr.length-1);
        return arr; 
    }

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String[] arr = new String[n];

        for(int arr_i = 0; arr_i < n; arr_i++){
              arr[arr_i] = in.next().trim();
        }

        System.out.println("result is:");
        String[] result = bigSorting(arr);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + (i != result.length - 1 ? "\n" : ""));
        }
        in.close();
    }
}

这些是我使用的输入(第一行取字符串数，然后是所有要排序的字符串。输出是每行中排序后的数字字符串):

input(1) 
10
5454545454
212101225515
51212
5141215
52
521
52145
5
5
5

Output(1)//correct
5
5
5
52
521
51212
52145
5141215
5454545454
212101225515

Input(2)
10
5454545454
212101225515
51212
5141215
52
5465156165164215612616546954512202496421
2121564
216451564561564651564561256065
11
55

Output(2)//incorrect
11
52
55
216451564561564651564561256065
51212
2121564
5465156165164215612616546954512202496421
5141215
5454545454
212101225515

Answer 1

您可以改用 new BigInteger(String)。

static void merge(String arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    String L[] = new String[n1];
    String R[] = new String[n2];

    for (int i = 0; i < n1; ++i)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[m + 1 + j];

    int i = 0, j = 0;
    int k = l;

    while (i < n1 && j < n2) {
        if (L[i].length() <= R[j].length()) {
            if (new BigInteger(L[i]).compareTo(new BigInteger(R[j])) <= 0) {
                //this will convert strings to numbers and compare them.
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}