1 基本思想
將一個記錄插入到已排好序的序列中狭瞎，從而得到一個新的有序序列（將序列的第一個數(shù)據(jù)看成是一個有序的子序列略吨，然后從第二個記錄逐個向該有序的子序列進行有序的插入症副，直至整個序列有序）
重點：使用哨兵捏顺，用于臨時存儲和判斷數(shù)組邊界面褐。
2 排序流程圖
image.png
3算法實現(xiàn) java
import java.util.Arrays;
public class Sort {
public static void main(String[] args) {
int arr[] = {2,1,5,3,6,4,9,8,7};
int temp;
for (int i=1;i<arr.length;i++){
//待排元素小于有序序列的最后一個元素時，向前插入
if (arr[i]<arr[i-1]){
temp = arr[i];
for (int j=i;j>=0;j--){
if (j>0 && arr[j-1]>temp) {
arr[j]=arr[j-1];
}else {
arr[j]=temp;
break;
}
}
}
}
System.out.println(Arrays.toString(arr));
}
}
4 運行結果
5 算法分析
1充择，當初始序列為正序時德玫，只需要外循環(huán)n-1次，每次進行一次比較椎麦，無需移動元素宰僧。此時比較次數(shù)（）和移動次數(shù)（
）達到最小值。
=n-1
=0
此時時間復雜度為观挎。
2琴儿，當初始序列為反序時，需要外循環(huán)n-1次嘁捷，每次排序中待插入的元素都要和[0,i-1]中的i個元素進行比較且要將這i個元素后移i次造成，加上tmp=arr[i]與arr[j]=temp的兩次移動，每趟移動次數(shù)為i+2,此時比較次數(shù)和移動次數(shù)達到最大值雄嚣。
= 1+2+...+(n-1) = n(n-1)/2=
= （1+2）+ （2+2）+.....+（n-1+2）=（n-1）(n+4)/2=
此時時間復雜度
3晒屎，在直接插入排序中只使用了i,j,tmp這三個輔助元素，與問題規(guī)模無關缓升，空間復雜度為鼓鲁。
4，相同元素的相對位置不變港谊，如果兩個元素相同骇吭，插入元素放在相同元素后面。是一種穩(wěn)定排序
