直接插入排序思想
主要思想就是从第二个元素开始，依次和前面的元素比较，如果比前面的元素小则将元素依次向后移位，给需要插入的元素腾出空间。与选择排序类似的是当前索引左边的所有元素都是有序的，但是它们最终的位置不确定，因为后面可能还会出现更小或更大的元素。所以为了给更小或更大的元素腾出空间，它们随时都可能被移动。如果到达了数组的右端时，数组顺序就完成了。
算法导论例子
排序方式像我们打牌时排序手中的扑克牌，开始时，我们手中的扑克牌为空，我们从牌堆中拿到第一张牌到手中，然后在不停的抓牌中，从右到左的比较手中每一张牌，左手中的牌总是排序好的，所以从第二张牌开始左手中的牌就是有序的，一直到抓完牌堆中的牌。
2.png
直接插入排序算法的特点
插入排序所需的时间取决于输入中元素的初始顺序。如果初始顺序基本有序，那么排序就会快很多。然后在键不重复的前提下，最坏情况(就是需要正序排序，结果数组里面的元素都是逆序的)：（N-1）+（N-2）+...............+2+1=N^2/2次比较和交换。最好情况：就是直接比较一遍，无需交换。就是比较N-1次，交换0次。
直接插入排序算法的实现
public static void printArr(int[] objArr) {
for (int i : objArr) {
System.out.println(i);
}
}
public static int[] insertSort(int[] arr) {
for (int i = 1 ; i < arr.length ; i++) {
int insertValue = arr[i];
int j = i - 1;
while (j>=0) {
if(arr[j] > insertValue) {
arr[j+1] = arr[j];
} else {
break;
}
j--;
}
arr[j+1] = insertValue;
}
return arr;
}
public static void main(String[] args) {
int[] arr ={5,2,3,6,4,5};
insertSort(arr);
printArr(arr);
}
运行结果
2.png
直接插入排序：
最大时间O(n^2)
最小时间O(n)
平均时间O(n)
辅助空间O(1)
稳定性：稳定
