插入排序之直接插入排序

suveng

发布于 2019-09-18 14:31:59

3880

发布于 2019-09-18 14:31:59

本文链接：https://blog.csdn.net/qq_37933685/article/details/84792290

个人博客：https://suveng.github.io/blog/ title: 插入排序之直接插入排序 date: 2018-12-01 19:00:00 +0800 update: 2018-12-01 19:00:00 +0800 author: suveng tags:

算法 preview: 插入排序之直接插入排序

文章目录

插入排序之直接插入排序
- 原理
- 时间复杂度
- 空间复杂度
- 稳定性
- 算法实现
  - Java

插入排序之直接插入排序

原理

列表第一个元素和前面元素比较，如果小于前面元素（其实不存在），则交换位置。（这步其实可以没有）
列表第二个元素和前面元素（第一个元素）比较，如果小于前面元素，则交换位置。
列表第三个元素和前面元素（第二个元素）比较，如果小于前面元素，则交换位置。如果和前面元素交换了位置，现在在第二个位置上，则接着继续和前面元素比较（第一个元素），如果小于前面元素，接着再次交换位置，然后再次重复比较过程…
继续重复以上过程，直到最后一个元素完成比较

时间复杂度

最坏时间复杂度	最优时间复杂度	平均时间复杂度
O(n^2)	O(n)	O(n^2)

空间复杂度

O(1)

稳定性

稳定

**稳定性定义：**排序前后两个相等的数相对位置不变，则算法稳定。

算法实现

Java

class InsertionSort {
	public static void main(String[] args) {
		System.out.println("hello，直接插入排序");
		InsertSort is=new InsertSort();
		int[] des=is.directInsertSort(new int[]{72,78,42,60,84,74,60,79,72,52});
		for(int i=0;i<des.length;i++){
			System.out.println(" "+des[i]);
		}
		System.out.println();
	}
	
	public int[] directInsertSort(int[] source){
		int n=source.length;
		//可以直接从第二个元素开始
		for(int i=1;i<n;i++){
			for(int j=i;j>0;j--){
				if(source[j]<source[j-1]){
					//异或法 交换变量，减少临时变量
					source[j]=source[j]^source[j-1];
					source[j-1]=source[j]^source[j-1];
					source[j]=source[j]^source[j-1];
				}
			}
		}
		return source;
	}
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018年12月04日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法