《直接插入排序》算法设计之三

<span style="font-family:SimSun;font-size:18px;"> /// <summary>
        /// 直接插入排序
        /// </summary>
        /// <param name="a">数组，用来保存数值</param>
        /// <param name="n">数组中元素个数</param>
        static void Insertsort(int[] a, int n)
        {
            int i, j, k;
            for (i = 1; i < n; i++)
            {
                //用来帮插入的数值找到合适的位置
                for (j = i - 1; j >= 0; j--)
                {
                    //如果小于的话，直接退出，因为排序已经完成
                    if (a[j] < a[i])
                    {
                        break;


                    }



                }

                //如果找到了一个合适的位置
                if (j != i - 1)
                {
                    //保存插入的变量
                    int temp = a[i];
                    //从插入的后一个，到合适的位置的所有数值整体向后移动
                    for (k = i - 1; k > j; k--)
                    {
                        //向后移动
                        a[k + 1] = a[k];
                    }
                    //把插入的数值，放到该位置上
                    a[k + 1] = temp;

                }
            }
        }</span>

 方法二

 看上面的代码我们还可以做一下优化，比如如果刚插入的数值大于满足整体排序的话，就应该直接退出里层循环，而上述代码并没有，因此我们可以换一种思路

 先比较

 类似于先把要插入的数字放到一个格子里，依次与前面的比较。如果小于前者，则让前者向后移动

 再移动

 如果插入的数值小于前者，如上图所示刚插入的1小于6的话，6向后移动，接着再进行比较

......................................................................................................

<span style="font-family:SimSun;font-size:18px;"> //直接插入排序法
        static void Insertsort(int []a,int n)
       {
           int i, j;
            //数组中默认是由一个数的
            //for循环来放置后面的N个数 
            for(i=1;i<n;i++)
            {
                //依次与前者比较
                //如果小的话,执行迁移
                if(a[i]<a[i-1])
                {
                    //先保存插入的数值
                    int temp = a[i];
                    //内层采用循环来一边执行移动，一边比较
                    for(j=i-1;j>=0&&a[j]>temp;j--)
                    {
                        a[j + 1] = a[j];
                    }
                    //最后还是把插入的数值放到合适的位置

                    a[j + 1] = temp;
                }
            }
       }</span>

原文：http://blog.csdn.net/luckyzhoustar/article/details/40184315