直接插入排序思想
主要思想就是從第二個元素開始，依次和前面的元素比較，如果比前面的元素小則將元素依次向后移位，給需要插入的元素騰出空間主胧。與選擇排序類似的是當前索引左邊的所有元素都是有序的，但是它們最終的位置不確定习勤，因為后面可能還會出現(xiàn)更小或更大的元素踪栋。所以為了給更小或更大的元素騰出空間，它們隨時都可能被移動图毕。如果到達了數(shù)組的右端時夷都，數(shù)組順序就完成了。
算法導論例子
排序方式像我們打牌時排序手中的撲克牌予颤，開始時囤官，我們手中的撲克牌為空厢破，我們從牌堆中拿到第一張牌到手中，然后在不停的抓牌中治拿，從右到左的比較手中每一張牌，左手中的牌總是排序好的笆焰，所以從第二張牌開始左手中的牌就是有序的劫谅，一直到抓完牌堆中的牌。
2.png
直接插入排序算法的特點
插入排序所需的時間取決于輸入中元素的初始順序嚷掠。如果初始順序基本有序捏检，那么排序就會快很多。然后在鍵不重復的前提下不皆，最壞情況(就是需要正序排序贯城，結(jié)果數(shù)組里面的元素都是逆序的)：（N-1）+（N-2）+...............+2+1=N^2/2次比較和交換。最好情況：就是直接比較一遍霹娄，無需交換能犯。就是比較N-1次，交換0次犬耻。
直接插入排序算法的實現(xiàn)
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);
}
運行結(jié)果
2.png
直接插入排序：
最大時間O(n^2)
最小時間O(n)
平均時間O(n)
輔助空間O(1)
穩(wěn)定性：穩(wěn)定
