选择排序
将数组分为两个子数组，其中一个子数组为有序数组，另一个为无序数组。然后从无序数组中取到最值元素，然后依次将这些最值元素追加到有序数组中。
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 |
由等差数列求和公式可知 $$sum_n = \frac{n(n+1)}{2} $$ 所以，时间复杂度为≈O(n2)
最好情况当数组为正序时，内外循环操作次数关系是：
| 外循环指针 | 内循环操作次数 |
|---|---|
| i == 0 | 0 |
| i == 1 | 1 |
| i == 2 | 1 |
| i == n - 1 | 1 |
所以，这种情况下的时间复杂度为O(n)