原地归并排序是否可以算作是那个神秘的排序算法
来源：4-13 排序算法总结
道临
2019-06-17
归并排序的缺点就是开辟了额外的空间
于是我在网上搜索了一下原地的归并排序是否可以实现, 发现的确有原地归并
因为使用递归所以依然有 logn 的空间复杂度, 为了避免这个开销, 使用循环来进行实现
那么如果使用循环实现原地归并排序,
并且对有序的情况进行优化, 即arr[mid] < arr[mid+1] 直接return, 时间复杂度就应该是 O(n)的了
是不是就是那个神秘的排序算法呢?
以上只是个人猜测
写回答
1回答
-
时间复杂度不可能是O(n)：）
arr[mid] < arr[mid+1] 的时候直接return，只能保证在数组有序的时候，进化成O(n)，是带条件的。但是对于一个随机数组，依然是O(nlogn)。
基于比较的排序算法，时间下届是O(nlogn)的：）
计数排序，桶排序，基数排序，是O(n)级别的。但是他们的排序方式，不是基于两个元素之间的比较的。如果有兴趣，可以在网上查一查这三种排序的原理：）
加油！：）
042019-07-16
相似问题