核心思想
将数组分为两个子数组,其中一个子数组为有序数组,另一个为无序数组。然后从无序数组中取到最值元素,然后依次将这些最值元素追加到有序数组中。
实现代码
|
性能
空间复杂度
整个算法只借助了minPos这一个辅助变量,所以空间复杂度是O(1)
时间复杂度
最坏情况当数组是倒序排列时。内外循环的操作次数关系是:
外循环指针 | 内循环操作次数 |
---|---|
i == 0 | n |
i == 1 | n - 1 |
i == 2 | n - 2 |
i == n | 0 |
由等差数列求和公式可知
所以,时间复杂度为≈O(n2)
最好情况当数组为正序时,内外循环操作次数关系是:
外循环指针 | 内循环操作次数 |
---|---|
i == 0 | 0 |
i == 1 | 1 |
i == 2 | 1 |
i == n - 1 | 1 |
所以,这种情况下的时间复杂度为O(n)