QBl*_*QBl 3 c arrays sorting algorithm complexity-theory
假设我们有一个填充了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.对这些数组进行排序所执行的操作总数将完全相同.实际上,如果您使用这些算法对每个数组进行排序并观察元素的移动,您会发现执行完全相同的移动.
如果您正在讨论排序适合单个机器字的整数,那么移动的成本与存储在该机器字中的数值无关.比较这些元素的成本可能也相同.因此,我预测您会看到使用这些算法对这些数组进行排序所需的时间完全没有区别.
如果存在任何差异,则意味着您使用的处理器可以在不同的时间内比较或移动不同大小的数字.据我所知,没有真正的处理器架构可以做到这一点.
现在,在另一方面,排序算法像是在数排序或基数排序,这是不是比较排序,并做取决于你在处理数字的大小,可能需要更长的时间对这些数组进行排序,因为他们的工作或者一个数字在一段时间或分配到一个数组,其大小取决于问题中数字的大小.在这些情况下,您应该看到运行时之间的差异,前提是您使用的算法实现得很好.