插入排序

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

思想

可以想一下扑克牌,假如你先拿到牌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)

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章