>插入排序
插入排序的思路:
1. 从第一个元素开始,该元素可以认为已经被排序;
2. 取出下一个元素,在前面已排序的元素序列中,从后向前扫描;
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
5. 将新元素插入到该位置后;
6. 重复步骤2~5。

平均时间复杂度:O(n²)
空间复杂度:O(1)
算法稳定性:稳定
```java
public class InsertSort3 {
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i;
while (j > 0 && arr[j-1] > temp) {
arr[j] = arr[j-1];
j--;
}
if (i != j) {
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int a[] = new int[]{32, 43, 23, 13, 5};
insertSort(a);
for (int i=0; i<a.length; i++) {
System.out.print(a[i] + ",");
}
}
}
```

插入排序