我正在探索以下算法:
- 计数排序
- 基数排序
- 桶排序
我知道这三个都能够在最好的情况下在线性时间内运行，但是我很难理解这些情况何时发生，除了计数排序的情况。
这是我对计数排序的理解，如果可能的话，我希望得到其他两种算法的答案:
计数排序在线性时间内运行，当您希望排序的信息之间没有很大的差距时。例如，1、10^5和545等将创建一个大数组，并且不能有效地使用内存和遍历，因此这将是使用计数排序的"最坏情况"，因此最好的情况是当间隙很小时。
如果有人能帮助我理解当线性时间发生时，基数和桶排序最佳情况的条件，我将不胜感激。
让我们从独立分析每个算法开始，看看我们是否可以确定在什么情况下它们将在线性时间内运行。
首先，让我们看一下计数排序。算法的工作原理如下:
- 查找要排序的最大整数
- 创建一个数组，每个整数有一个槽。
- 遍历主数组，用每个元素的频率更新第二个数组。
- 通过在输出数组中填充每个元素的适当数量的副本来构建排序数组。
第一步可以通过迭代主数组在时间O(n)内完成。让我们假设数组中的最大值是U。在这种情况下，第二步花费时间O(U)，因为我们必须将数组元素归零。第三步耗时O(n)最后一步需要时间O(n + U)，因为我们访问频率数组的每个元素正好一次(O(U))，并对输出数组O(n)进行总共n次写入。这意味着总运行时间为O(n + U)。请注意，这取决于需要排序的元素总数(较大的数组需要更长的排序时间)和数组中元素的大小(较大的数字将相应地需要更长的运行时间)。
如果我们希望这个运行时间是O(n)，我们需要要求U = O(n)。这样，我们就得到O(n + U) = O(n + n) = O(n)这意味着您需要让数组中最大元素的大小以与数组长度增加的速度大致相同的速度增长。例如，如果您保证数组中的所有元素都在1 ..n，那么计数排序将花费O(n)的时间来完成。这些元素在这个范围内如何分布并不重要。
基数排序本质上是通过一遍又一遍地重复执行计数排序，对数组中要排序的数字的每个数字进行一次排序。基数排序背后的关键思想是使前一个算法中的U值尽可能低。通过选取一个固定的基数，U的值被限制在某个常数。例如，如果您使用二进制基数排序，每次进行一位排序，那么要排序的数组中的每个元素本质上都被视为0或1。这意味着每一轮基数排序需要O(n)的时间来完成。对整个数组进行排序所需的轮数由数组中最大的数中的位数给出，即Θ(log U).这意味着算法的总运行时间最终为O(n log U).再次注意，运行时间取决于元素的数量和数组中最大元素的大小。
这次的优点是log U比U增长得慢得多。例如，2300大约是宇宙中原子的总数，但lg (2300) = 300，这是相当小的。
有些人会声称log U在任何固定的计算机上都是常数。在32位计算机上，所有整数都是32位(除非您使用任意精度的整数库，我们现在将忽略它)，而在64位系统上，所有整数都是64位。在第一种情况下，log U = 32，在第二种情况下，log U = 64。您可以声明，对于固定的系统，基数排序总是需要线性时间，因为运行时间将是O(n)。但是这个常数在不同的系统中是不同的。如果你更有理论头脑，想要更精确，你可以说，只要log U = O(1)基数排序在线性时间内运行，因为这样O(n log U) = O(n)这意味着，如果你对数字中的位数有一个恒定的上界，你可以保证基数排序将在线性时间内运行。
桶排序算法类似于基数排序，不同之处在于它使用最高有效位数而不是最低有效位数来分配元素。这意味着分析与以前几乎相同-只要log U = O(1)，算法在线性时间内运行。
希望这对你有帮助!