一种简单的直接插入排序精解-创新互联

直接插入排序，就像是桌子上一叠正面向下的扑克从小到大地依次拿到自己的手上。

1，显然拿到的第一张扑克（假如是3）是不用比较的，而且可以认为，它是有序的。

2，拿到第二张牌（假如是2）的时候，我们只要和第一张比较，放到合适的位置（现在是2,3），保持有序。

3，接着拿到第三张牌，我们只要和原来有序的序列（2,3）比较组成一个元素加一个的新有序序列即可。

(我们只要从右到左用在原序列一个个比较即可，如是5，只比较一次就可以决定放在3前，如果是1，那就比较两次)

详解如下图：

要点：

1，大循环从第二个元素开始，倒着比较

2，小循环的条件有两种情况

3，i在一趟比较的最后要加1，向后一格置入新元素

特征：

1，插入排序是原址排序，最多用了一个辅助空间来放临时元素

2，新元素之前的部分是本问题的子问题的求解结果

3，完全逆序的比较性能最差（内层循环的次数最多）

for(j=1 ; j< arr.length ; j++)

{

       key = arr[ j] ;//取出当前要插入比较的新元素

       i = j-1;//小循环指示器

       while( i> -1 && arr[i]>key) {//小循环负责在已经有序的部分中找个合适的位置

               arr[i+1] = arr [i] ;//有序部分比新来元素较大者后移

               --i;//继续向前寻找位置

       }

       i=i+1;

       arr[i] = key;//无论是否进入了小循环，把key放在i+1的位置总是对的

 //没有进入小循环的i和j是同一个位置

}

本文已完结；

by mengshengneng@163.com

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。