插入排序

724 阅读1分钟

插入排序

插入排序是一种简单且稳定的算法,适用于已排好序的序列,往其他插入某个元素,保证数据有序。

思想

可以想一下扑克牌,假如你先拿到牌1,5,9 然后你又起了一个8这时候你需要和1,5,9比较然后把8插入到5,9的中间让它成为有序的1,5,8,9 详细看下面动图。 在数组的操作中,由于数组并不像手那么灵活,每次插入操作都需要移动元素。

代码

public void insertSort(int a[]){ 
	for(int i=1;i<a.length;i++){
		//和前面的依次比较
		for(int j=i;j>0;j--){
			if(a[j]<a[j-1]){
				int temp=a[j];
				a[j]=a[j-1];
				a[j-1]=temp;
			}
		}
	}
}

复杂度分析

空间复杂度O(1) 时间复杂度外层循环n次 内层循环(1+2+3+....+i+....+n)所以复杂度是n的平放 最优的时间复杂度O(n)

稳定性分析

相同的两个元素不存在相对顺序的互换比如4,3,5,7,3 第一个三会插入到4的前面,第二个三并不会受第一个三顺序的影响

更多推荐

归并排序详解

快速排序详解

选择排序详解