直接插入排序
博客专区 > JiaChang 的博客 > 博客详情
直接插入排序
JiaChang 发表于1年前
直接插入排序
  • 发表于 1年前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

直接插入排序

算法思路

对于一个有 n 个元素的数据序列,排序需要进行 n-1 趟插入操作

第一趟插入:将第2个元素插入到前面的有序子序列中,此时前面只有一个元素,当然是有序的。

第二趟插入:将第3个元素插入到前面的有序子序列中,前面两个元素是有序的。

......

第n-1趟插入:将第n个元素插入到前面的有序子序列中,前面n-1个元素是有序的。

直接插入排序的实现

/***
	 * 直接插入排序
	 * @param data 待排序的数组
	 */
	public static void insertSort(int[] data){
		
		for(int i = 1; i<data.length; i++){
			//如果 i索引前面的元素比 i索引处的元素大,则需要往前插入
			if(data[i-1] > data[i]){
				//当数据整体后移时,保证data[i]处的元素不丢失
				int temp = data[i];
				//最多后移多少个元素
				int j = i-1;
				//循环判断,只要前面的元素比data[i]大,则需要后移
				for(; j>=0 && data[j]>temp; j--){
					data[j+1] = data[j];
				}
				//最后将data[i]插入到合适的位置
				data[j+1] = temp;
			}
		}
	}

测试代码
 

算法分析

(1)时间复杂度:O(n2)(注:这里是n的平方,由于编辑器的原因打不出来)

(2)空间复杂度:O(1)

(3)直接插入排序是稳定的

(4)更适合于初始记录基本有序(正序)的情况,当初始记录无序,n较大时,此算法的时间复杂度较高,不宜采用。

 

标签: 直接插入排序
共有 人打赏支持
粉丝 3
博文 32
码字总数 18002
×
JiaChang
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: