插入排序
将数组分成两部分，一部分是有序数组，一部分是无序数组。每次从无序数组中拿出一个元素，将这个元素放置到有序数组中合适的位置。直到整个数组都有序为止。
public void sort(int[] arr) {
for(int i = 0; i < arr.length; i++) {
int currPos = i;
for(int j = i - 1; j >= 0; j--) {
if(arr[currPos] > arr[j]) {
swap(arr, j, currPos);
currPos = j;
}
}
}
}
整个算法只借助了currPos这一个辅助变量，所以空间复杂度是O(1)
最坏情况 当数组是倒序排列时。内外循环的操作次数关系是：
| 外循环指针 | 内循环操作次数 |
|---|---|
| i == 0 | 0 |
| i == 1 | 1 |
| i == 2 | 2 |
| i == n - 1 | n - 1 |
所以，时间复杂度为O(n2)
最好情况 当数组为正序时，内外循环操作次数关系是：
| 外循环指针 | 内循环操作次数 |
|---|---|
| i == 0 | 0 |
| i == 1 | 1 |
| i == 2 | 1 |
| i == n - 1 | 1 |
所以，这种情况下的时间复杂度为O(n)