java - 排序复杂度

Question

给定一个数组，其中偶数索引中的值按递增顺序排列，奇数索引中的值按递减顺序排列。例如:

[1,99,16,65,45,23,97]

我考虑过两种不同的排序方式:

1. 从 i=0 开始，j=a.length-2 并且比较 a[i] 和 a[j] 的值。如果 a[i] 较小，则 i+=2 或如果 a[j] 较小，则 j-=2。为此需要一个额外的数组。时间是 O(n)，空间是 O(n)。

2. 将索引为奇数的元素进行倒序，然后对整个数组进行冒泡排序。空间是 O(1).. 时间呢？

哪个更有效率？每种情况下最坏的时间和空间复杂度是多少？冒泡排序可能需要更长的时间，不是吗？

Answer 1

我还没有在真实场景中看到冒泡排序的良好用例。如果您使用选项二，一旦您翻转奇数索引中的单元格，您就会得到一个数组，该数组可能会或可能不会自行排序，并应用 O(n²) 气泡种类。一个微不足道的改进是使用快速排序或合并排序并获得 O(n log(n)) 时间复杂度。