首页 > 代码库 > 《直接插入排序》算法设计之三

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

 

 直接插入排序

 每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的序列中,知道全部记录插入完成。

 

 排序过程

 1.每次插入的数值都要与自己前面的做比较

   A.如果大于前面的数,则停止。因为每次都是排好的序列

   B.如果小于前面的数,接着向前比较,指导找到自己的位置,插入即可


 如右图所示

 当插入2时,需要与前面做比较,直到找到自己合适的位置即可

 当插入1时,用现在插入的数值依次与前面做比较,直到找到合适的位置即可 


 代码分析

 通过以上的分析,因此我们可以采取以下思路来处理直接插入排序

 方法一

 找位置

 让插入的数值与前一个数做比较,比如上图中插入的1与6做比较,如果小的话,继续执行,知道找到自己该放的位置。

 整体移动

 让该位置到最后的数值整体向后移动,最后把要插入的数字放到该位置即可

<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>




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