排序（三）插入排序移位法和交换法

╰+哭是因爲堅強的太久メ 2022-12-10 14:57 125阅读 0赞

先看下图哦  
![6d867acd56e40fb32975f9e91d041fa9.png][]  
还是将问题拆分

插入就相当于打牌 打牌会将牌有顺序的插入到某个位置 最终达到有序的状态

这样方便出顺子 炸弹什么的

插入也是一样

思路是这样的 一步步的排序 把第一个元素变有序 有人说这不废话嘛 一个元素哪来的有序之分呢？

对！

所以我们插入排序应跳过第一个元素 直接从第二个元素开始比较 默认第一个元素是有序的

随后可以将数组想成两部分

每次循环完毕后 前一部分都是有序的 后一部分都是无序的 直到所有都有序为止

因此我们将第二个元素与第一个元素做比较

如果发现arr\[0\]>arr\[1\] 如第一个元素为30 第二个元素为10

30>10

那么就要将1位置的元素插入到0位置

变成10 30 酱紫

所以1位置的元素要先储存起来 记做 temp=arr\[1\]

然后将1位置的元素 直接用arr\[0\]替换 变成30 30

再将arr\[0\] 用temp来替换 就完成了交换 这就是移位法的思想

若arr\[0\]<=arr\[1\] 保持原样 开始下一次循环

我们可以先写内层循环的第一步

//跳过第一个元素 所以要先储存 因为移位会覆盖这个元素
    int temp=arr[1];
    
    int index=1-1;//或者index=0;
    
    while(index>=0 && arr[index]>temp){ 
    	//后移
    	arr[index+1]=arr[index];
    	//跳出循环
    	index--;
    }
    arr[index+1]=temp;
    
    //第二步
    int temp=arr[2];
    
    int index=2-1;//或者index=1;
    
    while(index>=0 && arr[index]>temp){ 
    	//后移
    	arr[index+1]=arr[index];
    	//跳出循环
    	index--;
    }
    arr[index+1]=temp;
    
    //第三步
    int temp=arr[3];
    
    int index=3-1;//或者index=1;
    
    while(index>=0 && arr[index]>temp){ 
    	//后移
    	arr[index+1]=arr[index];
    	//跳出循环
    	index--;
    }
    arr[index+1]=temp;

这样是不是可以写出内层循环了 动的地方改为i就行啦

那外层循环不是简简单单吗 记住 外层循环是从1开始的 因为要跳过第一个元素

完整代码如下

for(int i=1;i<arr.length;i++){ 
    	int temp=arr[i];
    	int index=i-1;
    	while(index>=0 && arr[index]>temp){ 
    		arr[index+1]=arr[index];
    		index--;
    	}
    	arr[index+1]=temp;
    }

完成！

这就是移位法的实现。

交换法

//知道一个核心 外层i是从1开始的 然后依次变得有序 j随着i变化 
    for(int i=1;i<arr.length;i++){ 
        for(int j=i;j>0;j--){ 
            if(arr[j]<arr[j-1]){ 
                //交换 两种思路 临时变量 位运算 这里直接上位运算了
                arr[j]^=arr[j-1];
                arr[j-1]^=arr[j];
                arr[j]^=arr[j-1];
            }else{ 
                //这一步跳出 是因为前面的循环已经有序 不需要再进行其他的比较了
                break;
            }
        }
    }

有人说

那么爆爆哥 交换法那么简单 还用啥移位法啊

好问题

在插入排序下 我测试了下 好像没多大差别

但是在下期的希尔排序下 两者性能差别就很大了 所以这是为后面打基础

ps:在小的帆也能远航

[6d867acd56e40fb32975f9e91d041fa9.png]: /images/20221123/1d59146740a04b2db4dd3cfbd157125d.png