1、思想
现将第一个数看做一个有序的序列，然后将第2个数插入到正确的位置，然后将第3个数插入到正确的位置，每次插入都从已有序列的最后一个数开始，从后向前比较。直到所有的数都插入完毕。
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
2、代码
public class Main23 {
public static int[] insertSort(int [] a) {
for(int i=1;i<a.length;i++){//分别将第二个数到最后一个数插入到前面
for(int j=i;j>0&&a[j]<a[j-1];j--){
int temp = 0;
temp = a[j-1];
a[j-1] = a[j];
a[j] = temp;
}
}
return a;
}
public static void main(String[] args) {
// TODO Auto-generated method stu
int [] arr = {7,3,4,8,1};
Main23.insertSort(arr);
for(int c:arr){
System.out.println(c);
}
}
}
3、时间复杂度
O(n^2)
4、空间复杂度
O(1)
版权声明：本文为g1607058603原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。