给定一个数组,其中偶数索引中的值按递增顺序排列,奇数索引中的值按递减顺序排列。例如:
[1,99,16,65,45,23,97]
我考虑过两种不同的排序方式:
从 i=0 开始,j=a.length-2 并且 比较 a[i] 和 a[j] 的值。如果 a[i] 较小,则 i+=2 或如果 a[j] 较小,则 j-=2。为此需要一个额外的数组。时间是 O(n),空间是 O(n)。
将索引为奇数的元素进行倒序,然后对整个数组进行冒泡排序。空间是 O(1).. 时间呢?
哪个更有效率?每种情况下最坏的时间和空间复杂度是多少?冒泡排序可能需要更长的时间,不是吗?
最佳答案
我还没有在真实场景中看到冒泡排序的良好用例。如果您使用选项二,一旦您翻转奇数索引中的单元格,您就会得到一个数组,该数组可能会或可能不会自行排序,并应用 O(n2) 气泡种类。一个微不足道的改进是使用快速排序或合并排序并获得 O(n log(n)) 时间复杂度。
关于java - 排序复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30746389/