观焦点：【插入排序】详细讲解

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

观焦点：【插入排序】详细讲解

2023-01-03 21:15:04 来源：博客园

总体思路

排序流程：

一共十个数排序，先用第二个数55跟第一个数99比较，如果55小于99，那么交换55和99，此时前两个数（即55和99）已经有序了。

接下来用第三个数11跟第二个数99比较，如果11小于99，那么交换11和99，再用第二个数（此时是11）和第一个数55比较，如果11小于55，那么交换11和55，此时前三个数已经有序了。

(资料图片仅供参考)

按照此方法，排序len-1次即可。

抽象流程：

举个例子，假如有十个人，要按照年龄大小排队站好，年龄小的站排头，年龄大的站排尾，实际上这个事就是，第一个人不用动，第二到第十个人，每个人重复一次流程：问前面的人：“嘿，哥们你多大”。如果前面的人比自己年龄小，那么就原地站好结束行动，如果前面的人比自己年龄大，那么就让他站到自己身后。

代码流程：

那么肯定是两层循环嵌套。

第一层循环：代表着从第二到第十个人每个人都要重复一次“找自己位置”的流程

第二层循环：代表着每个人要不断询问前面人的年龄，直到前面的人比自己小或已经到头了为止。

所以接下来考虑一下两层循环的条件。

第一次循环：

//为了更直观的关注循环的实现，就不贴函数了，假设函数传入两个参数，数组data[10]和数组长度length.int i = 0；int j = 0;int temp = 0;//一个临时的值，交换两个数自然需要一个临时的值了。for (i = 1; i < length; i++)//i = 1代表从第二个人开始，因为第一个人就自己=有序。i < length代表到最后一个人结束{    temp = data[i];//“找自己位置的人”先记下自己的年龄    //j = 1代表首先询问自己前面一个人的年龄。    //j >= 0 && temp < data[j] 条件前面说过了，什么时候交换？前面的人比我小，并且还没到头的时候    //j-- 如果这次询问完并且交换了，那么下一次怎么做？当然是去问问前面的前面那个人多大了，所以j--;    for(j = i-1; j >= 0 && temp < data[j]; j--)    {        //发现自己确实比前面的人年龄大，因此进行交换，否则也进不来这次循环。代码的意思是，自己的位置被前面的人占了。        data[j+1] = data[j];  //此处很多新手疑问，为什么不是data[j] = data[i]直接赋值,请看最后的说明。    }    //自己（temp就是记下的自己的年龄嘛）占到前面的人的位置，完成交换。    data[j] = temp;}

说明一下，为什么不是data[j] = data[i]直接赋值？

两个值交换必然经过一直中间变量，此话是废话，废就废在懂的人不用说，不懂的人说了也不懂，因此我要举个例子，请诸位静听。假如你在上学，老师让你和你的同桌换个座位，请问怎么换？

流程必然是：1、有一个人先腾出自己的座位 2、另一个人坐上去 3、让出座位的人坐到另一个人的位置

想象一下这个场景，如果你腾出自己的位置，在你等你的同桌坐到你座位上的过程中，你站在哪里？你站在旁边对不对？这个旁边这片空间，就是temp。

只不过人比机器聪明，让你忽略了原来你让出位置并且站在了其他的空间，而你只关注于你和同桌交换的结果。

但是机器不是，如果你不去temp等着，你的同桌就会把你吃了，然后你就消失了。

再想象一下，一个长方形盒子2立方米的体积，有两个1立方米的正方体放进去，严丝合缝没有空间剩余，不利用外界空间的情况下，两个盒子就是死的，谁也动不了，因为没空间给他活动。如果你想交换两个正方体的位置，你只能先把一个拿出来，拿到一个temp空间中，才能完成交换。