如何在Java中有效地对大型整数数组进行排序？

Question

我正在开发一个项目，需要在 Java 中对非常大的整数数组进行排序。

我尝试过使用

Arrays.sort()

方法，但对于我的数据集大小而言，它似乎效率低下。谁能建议一种更有效的排序算法或方法来对 Java 中的大型整数数组进行排序？我对能够处理大型数据集而不消耗过多内存或花费太多时间的方法特别感兴趣。预先感谢您的帮助！

Answer 1

如果您正在为 Java 中的大型整数数组寻找更有效的排序算法，您可能需要考虑使用基数排序算法。基数排序对于整数排序特别有效，因为它根据数字的各个数字进行排序。

基数排序的时间复杂度为O(n * k)，其中n是数组中元素的个数，k是最大数的位数。对于大型整数数组来说，它非常有效，特别是当值的范围不明显大于元素数量时。

Answer 2

使用此函数实现归并排序。这个函数比 Arrays.sort() 快得多

public int[] mergeSort(int[] arr, int l, int m, int r) {
    int n1 = m-l+1;
    int n2 = r-m;
    int[] L = new int[n1];
    int[] R = new int[n2];
    for(int i = 0;i < n1; i++) {
        L[i] = arr[l+i];
    }
    for(int i = 0;i < n2; i++) {
        R[i] = arr[m+1+i];
    }
    int i = 0, j = 0, k =l;
    while(i < n1 && j < n2) {
        if(L[i] <= R[j]) {
            arr[k++] = L[i++];
        }
        else {
            arr[k++] = R[j++];
        }
    }
    while(i < n1) {
        arr[k++] = L[i++];
    }
    while(j < n2) {
        arr[k++] = R[j++];
    }
    
    return arr;
}