假设我们有一个用 long long unsigned int 填充的数组。每个相邻元素之间的距离很小。例如我们有:[0,1,0,1,0,1] 我们有另一个相同大小的数组，每个相邻元素之间的距离现在很重要。 然后我们有以下数组:[1, 1000000000, 1, 1000000000, 1, 1000000000]。
最后一步是用插入排序或合并排序或快速排序对两个数组进行排序。 第二个数组的处理时间是否可能因为元素之间的距离更大而更长？
提前致谢!
最佳答案
插入排序、快速排序和归并排序等排序算法称为比较排序，因为它们纯粹根据这些元素的相对顺序而不是它们的对元素进行排序绝对大小。从快速排序、合并排序或插入排序的角度来看，数组 [0, 1, 0, 1, 0] 和 [0, 100000, 0, 100000, 0] 是完全相同的，因为它们无法知道 100000比 1“大得多”。对这些数组进行排序所执行的操作总数将彼此完全相同。事实上，如果您使用这些算法对每个数组进行排序并观察元素移动，您会发现执行了完全相同的移动。
如果您正在谈论对适合单个机器字的整数进行排序，那么移动的成本与存储在该机器字中的数值无关。比较这些元素的成本可能也相同。因此，我预测您会发现使用这些算法对这些数组进行排序所需的时间绝对没有差异。
如果有任何差异，则意味着您使用的处理器可以在不同的时间内比较或移动不同大小的数字。据我所知，没有真正的处理器架构可以做到这一点。
另一方面，计数排序或基数排序等排序算法不是比较排序，确实取决于您处理的数字的大小，可能 对这些数组进行排序需要更长的时间，因为它们要么一次处理一个数字，要么分配到一个数组中，该数组的大小取决于所讨论数字的大小。在这些情况下，您应该看到运行时之间的差异，前提是您使用的算法实现良好。
关于c - 排序算法和数字之间的距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42725751/