java - 对包含一系列元素 k 的整数数组进行排序

Question

我正在寻找一个解决方案，其中我们在整数数组中有一系列元素 k 说 [1-4]，比如 [1,2,1,3,4,2,1,3,2,3,1,4, 2] 像这样，它们需要在 Core Java 中以最小的时间复杂度进行排序。

有人可以帮我以最小的时间复杂度解决这个问题。

Answer 1

数一数你有多少个 1、2、3 和 4，然后根据计数把数字放回去：

int[] count = new int[5]; // 0..4
for (int a : data) {
    data[a]++;
}
int p = 0;
for (int i = 0 ; i != count.length ; i++) {
    for (int j = 0; j != count[i] ; j++) {
        data[p++] = i;
    }
}

尽管有两个嵌套循环，但它具有线性时间复杂度，因为执行最内层赋值的次数正好等于原始数组中的项目数。

Answer 2

您可以只扫描一次输入，计数到一个数组并再次展开它；据我所知，这将给出n+m复杂性，n数组的长度在哪里，范围的长度在哪里m；如果您使用有序 O(1) 散列而不是数组，则可以将其推到接近 O(n)。

    int range_min = 1, range_max = 4;

    int[] input        = {1, 2, 1, 3, 4, 2, 1, 3, 2, 3, 1, 4, 2};
    int[] output       = new int[input.length];
    int[] intermediate = new int[range_max-range_min+1];

    for(int num : input)                        
        intermediate[num-range_min]++;

    int cnt = 0;
    for(int i=0; i<range_max-range_min+1; i++)  
        for(int j=0; j<intermediate[i]; j++)
            output[cnt++] = i+range_min;

Answer 3

可能Arrays.sort(...)会有最小的时间复杂度，因为它是一个直接在 Java 中可用的解决方案。更重要的是它基于快速排序（平均复杂度 O(n lg n)），所以很有可能它会是最好的解决方案。

Answer 4

当 k 是“小范围”时，计数排序最适合这种情况。它具有线性 (O(n+k)) 复杂度。

Answer 5

如果您只对整数进行排序 Arrays.sort() (Quicksort) 可能是最好的方法，我通常会编写自己的排序接口，所以我可以有一个带有 compareTo(Obj,Obj) 的接口，我可以在其中设置2. Obj 作为参数，在不同的Category 中进行排序。例如，如果我想按视图排序，则通过 1，如果按喜欢排序，则通过 2。

如果你有很多数据要排序（例如碎片整理），这可能会比你有更多的内存，你会使用合并排序，因为你不需要在你的内存中拥有所有数据来对它进行排序。