arrays - 如果只有从 1 到 n 的元素，是否可以在 O(n) 中对数组进行排序？

Question

假设比较数组中的元素需要 O(n)，当数组中有从 1 到 n 的元素时，是否可以在 O(n) 中对数组进行排序？

我们需要创建一个这样的算法，但不知道它是否可行。我能想到 O(n^2) 中的一个。我不是要算法，我会花时间创建一个算法，但需要知道它是否可行。

Answer 1

这绝对是可行的，您只需创建一个带有计数器的数组并计算元素 i 出现的次数，因为元素的范围从 1 到 < em>n，你知道这个计数器的长度是 n。

接下来是生成步骤，如果您遇到 k_{，您只需生成 ki 个元素 i我}这样的元素。

Java 示例代码:

int[] data = {5,1,2,4,5,1,2,3};

//assuming data contains only values from 1 to n (included) with n the length
public static int[] sort_int_limited (int[] data) {
    int n = data.length;
    int[] counters = new int[data.length];

    //counter phase
    for(int i = 0; i < n; i++) {
        counters[data[i]-1]++;
    }

    //generate phase
    int k = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < counters[i]; j++) {
            data[k++] = i+1;
        }
    }

    return data;
}

jDoodle demo

正如@Aivaen 在 his/her comment 中所说的那样，这个算法叫做计数排序。