插入排序

大家好,小范来为大家解答以上的问题。插入排序这个很多人还不知道,现在让我们一起来看看吧！

1、插入排序(insertion sort)如果需要对一个小型数组进行升序排列，那么可以选用插入排序，插入排序可以用打牌时对摸起的牌根据牌的点数来对其进行插入排列来描述。

2、可以把左手中的牌比做已经摸起的牌，即已经被排列好的牌，左手可以容纳的牌数的空间可以假想为和要摸的牌的总数相同；而在桌子上的那部分没摸的牌则是未被排序的牌，这二者的关系可以抽象为数组中已经被排序好的部分和未被排序好的部分。

3、一开始摸起的第一张牌不需要排序，可以认定其为已排序的牌。

4、如果用外层循环for来表示摸起的牌的话，则可以抽象为：// 对象数组// 桌子上的牌int A[] = {5,1,3,6,2,4};// 从数组的第二个元素开始抽取for(int i = 1; i < sizeof A/sizeof A[0]; ++i){int pick = A[i]; // 被摸起的牌int j = i - 1; // j记录已排序部分的最后一张牌的位置. . .}而后摸起的排要根据排列策略和先前摸起的牌的点数的大小来确定其插入的合适位置，这里示范的排列策略是升序排列，摸起了这张牌后，便自右向左地和手中的牌进行比较。

5、把pick称作摸起的牌，如果pick比手中的牌小，则手中较大的那张牌就向右挪一位，pick再和下一张牌做比较，如果下一张牌仍然比pick大，那么那张牌便也向右移动一个位置，依此类推。

6、如果手中下一张和pick比较的牌比pick小，那么pick就被插入在了手中前一张牌移动后空下的位置；或者手中所有的牌都比pick大，那么所有的牌就都向右移动过一个位置，所以pick最终被插入在了手中最左边的位置。

7、这个过程可以抽象为：// 对象数组// 桌子上的牌int A[] = {5,1,3,6,2,4};// 从数组的第二个元素开始抽取for(int i = 1; i < sizeof A/sizeof A[0]; ++i){int pick = A[i]; // 被摸起的牌int j = i - 1; // j记录已排序部分的最后一张牌的位置// 如果循环了j+1次，即j = -1时还未找到比pick小的牌// 那么pick就是最小的牌被插入在位置A[0]处// A[j]是当前手中和pick进行比较的牌while(j >= 0 && A[j] > pick){// 未找到可插入位置，则A[j]向后挪一位A[j+1] = A[j];// j减1继续向左定位手中下一张供和pick比较的牌--j;}// while结束后，j+1所表达的位置便是pick可以插入的位置A[j+1] = pick;}// 对于有N个元素的数组A，采用插入排序法排序时，当外层循环进行了N-1次后排序完毕for(i=1;i<4;i++) //外层{ t=a[i]; for( j=i-1 ; j>=0 && t>a[j] ; j-- ) //内层 a[j+1]=a[j]; a[j+1]=t; } 你要理解插入排序的原理，外层for从第二个数开始遍历（i从1开始），用t（即对应的a[i]）和其前面的所有值进行比较，如果t大，则该数后移一位，直到t小或者j小于0的时候退出内层for循环，这时候出现的格局就是所有在i位置之前比a[i]小的值全部后移了一位，退出循环时就会空出一个位置来。

8、举个例子：输入：1 3 2 4第一次循环时，t=a[1]=3，t>a[0]，所以a[0]后移一位（即：a[j+1]=a[j] -> a[1]=a[0]），之后出现结果：1124，这时候实际上0位置是给此时的t预留的位置，内层for执行完毕后，执行：a[j+1]=t 正好弥补这个空缺。

9、结果：3124第二次循环时，j=1，t=a[2]=2，t>a[1]，所以a[1]后移一位：a[2]=a[1]，之后结果：3114，在比较t和a[0]，t小，跳出内层for，跳出时j为0，执行：a[1]=t=2，结果：3214 下面就不讲了，从上面可以看出，你说的那一句，至关重要，外层for每循环一次就插入一位数据，而a[j+1]=t，就是完成插入的最后一步。

本文到此分享完毕，希望对大家有所帮助。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！