朝花夕拾

A Development Engineer, a Life Liver, a Hope Holder

核心思想

将数组分为两个子数组,其中一个子数组为有序数组,另一个为无序数组。然后从无序数组中取到最值元素,然后依次将这些最值元素追加到有序数组中。

实现代码

public void sort(int[] arr){
for(int i = 0; i < arr.length; i++) {
int minPos = i;
for(int j = i; j < arr.length; j++) {
if(arr[minPos] > arr[j]) {
minPos = j;
}
}
swap(arr, i, minPos);
}
}

性能

空间复杂度

整个算法只借助了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)