排序系列之插入排序的两种思想

交换思想

大体思想就是类似于玩扑克牌时，对新拿到的扑克进行对应位置的插入，相对小的放在左边，大的放在右边；详细来说是以第一张牌为基础，后面的数值依次与第一张进行比较，比较到比它小的，就从开始位置向后依次两两交换位置，比他大的不用动(不过不是一定不动，如果别它大的这个元素的位置 的左边的元素仍比该元素大，则也需要进行交换)，可能稍微有些难理解，还是看例子吧

举例：
以6 3 2 9 8为例，如图

这里注意，2比6小两者交换位置，2比3还小继续交换位置；8比6大，按说应该不动，但是8小于与它相邻的左边的元素，则继续交换，直至不小于其左边的元素为止，停止交换

记住模板，做题时手到擒来(关键还是理解后记它的思想)：

for(int begin = 1;begin < array.length;begin ++){
	int cur = begin; // 记录当前下标
	while(cur > 0 && array[cur] < array[cur-1]){
		int tmp = array[cur];
		array[cur] = array[cur-1];
		array[cur-1] = tmp;
		cur --;
	}
}

挪动思想

直接上例子了，便于理解，举例：
数组下标1 2 3 4对应着不同大小的值
挪动的思想在此体现，这里是2和3对应的数值是有序的，且都比4对应的值要大;那么我们可以假设一下，如果有多个这样的有序的数值在一起，则相当于直接把他们一起平移(挪动)了一个位置，

之后，空出一个位置，再将虚拟的数值 赋值给它即可

直到排序成功
模板在手，题目我有：

for(int begin = 1;begin < array.length;begin ++){
	int cur = begin;
	int value = array[cur]; // 这里至关重要，记录当前的下标的值
	while(cur > 0 && value < array[cur-1]){ // 这里用到了value
		array[cur] = array[cur-1];
		cur --;
	}
	array[cur] = value;
}

总结：
1.插入排序的时间复杂度与序列的逆序对成正比，比如5,3,6,2,1,这里3相对于5就是一个逆序对，这样的逆序对越多时间复杂度越大
2.另外插入排序时间复杂度最坏为O(n^2),最好为O(n)
3.当序列中挪动的个数越多时(也就是说无需排序的个数越多时，类似于刚才提到的2、3对应的那种情况，只不过是数量多了)，则使用挪动思想时间效率相对会更高，因为挪动思想核心是挪动，是对值覆盖; 而交换思想核心还是交换，交换一次就需要执行三个语句，次数一多效率可想而知

愿经历千帆，归来仍是少年

本文地址：https://blog.csdn.net/qq_44230700/article/details/108169780