在 Θ(n) 时间内对列表进行排序的算法
Algorithm to sort a list in Θ(n) time
问题是对包含 n 个不同整数的列表进行排序，这些整数的值范围从 1 到 kn（含），其中 k 是一个固定的正整数。设计一个算法，在 Θ(n) 时间内解决问题。
我不只是想要一个答案。解释会有所帮助，或者如果有人可以让我指出正确的方向。
我知道 Θ(n) 时间意味着算法时间与元素数量成正比。不知道从那里去哪里。
固定 k 很容易：创建一个 kn 计数器数组。将它们全部设置为零。遍历数组，如果数组元素等于 i，则将计数器 i 增加 1。使用计数器数组 re-create 排序数组。
显然，如果 k > log n，这是低效的。
关键是整数只有1到kn，所以长度是有限的。这有点棘手：
当我们说排序算法是 O(N) 时，常见的假设是数字 N 适合恒定数量的机器字，这样我们就可以在恒定时间内对那个大小的数字进行数学运算。 根据这个假设，kN 也适合固定数量的机器字，因为k是固定的正整数。因此你的输入是 O(N) 字长，每个字都是固定位数，所以你的输入是 O(N) 位长。
因此，任何花费时间与输入中的位数成正比的算法都被视为 O(N)。
实际上有很多选择，但是当以这种特定方式问这个特定问题时，提问的人通常希望您提出基数排序：
https://en.wikipedia.org/wiki/Radix_sort
MSB-first基数排序只是将整数根据其前W位的值划分为2^W个桶，然后根据下W位划分每个桶，依此类推，直到所有位被处理。
这个花费的时间是O(N*(word_size/W))，但是正如我们所说的字长是常数，W是常数，所以这是O(N)。
问题是对包含 n 个不同整数的列表进行排序，这些整数的值范围从 1 到 kn（含），其中 k 是一个固定的正整数。设计一个算法，在 Θ(n) 时间内解决问题。
我不只是想要一个答案。解释会有所帮助，或者如果有人可以让我指出正确的方向。
我知道 Θ(n) 时间意味着算法时间与元素数量成正比。不知道从那里去哪里。
固定 k 很容易：创建一个 kn 计数器数组。将它们全部设置为零。遍历数组，如果数组元素等于 i，则将计数器 i 增加 1。使用计数器数组 re-create 排序数组。
显然，如果 k > log n，这是低效的。
关键是整数只有1到kn，所以长度是有限的。这有点棘手：
当我们说排序算法是 O(N) 时，常见的假设是数字 N 适合恒定数量的机器字，这样我们就可以在恒定时间内对那个大小的数字进行数学运算。 根据这个假设，kN 也适合固定数量的机器字，因为k是固定的正整数。因此你的输入是 O(N) 字长，每个字都是固定位数，所以你的输入是 O(N) 位长。
因此，任何花费时间与输入中的位数成正比的算法都被视为 O(N)。
实际上有很多选择，但是当以这种特定方式问这个特定问题时，提问的人通常希望您提出基数排序：
https://en.wikipedia.org/wiki/Radix_sort
MSB-first基数排序只是将整数根据其前W位的值划分为2^W个桶，然后根据下W位划分每个桶，依此类推，直到所有位被处理。
这个花费的时间是O(N*(word_size/W))，但是正如我们所说的字长是常数，W是常数，所以这是O(N)。