标题:实现插入排序


基本插入排序的实现是这样的:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。

下面是插入排序算法的实现代码:

 

void insertsort(int a[], int n)

{

     int i, j, tmp;

     for (i = 1; i < n; i++)

    {

         tmp = a[i];

         j = i - 1;

         while (tmp < a[j])

        {

              a[j+1] = a[j];

              j--;

         }

         a[j+1] = tmp;

     }

}

 

基本插入排序的时间复杂度为O(n2),是一种稳定排序算法。

 

希尔排序是一种经过改进的插入排序算法。基本思想是:先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下(接近最好情况),效率是很高的,因此希尔排序在时间效率上比前两种方法有较大提高。具体做法:首先确定一组增量d0d1d2d3...,dt-1()其中n>d0>d1>...>dt-1=1),对于i =0,1,2,...,t-1,依次进行下面的各趟处理:根据当前增量din个元素分成di个组,每组中元素的下标相隔为di;再对各组中元素进行直接插入排序。

下面是一个希尔排序的实现算法:

 

void shellsort(int a[], int n)

{

     int i, j, gap, tmp;

     gap = n/2;

     while (gap > 0) {

         for (i = gap + 1; i <= n; i++)

         {

              j = i - gap;

              while (j > 0)

             {

                   if (a[j] > a[j+gap])

                   {

                       tmp = a[j];

                       a[j] = a[j+gap];

                       a[j+gap] = a[j];

                   }

                   else

                   {

                       j = 0;

                   }

              }

         }

         gap /= 2;

     }

}

 

希尔排序的复杂度为:O(n1.25),它不是稳定排序。



看文字不过瘾?点击我,进入腾讯课堂视频教学
麦洛科菲长期致力于IT安全技术的推广与普及,我们更专业!我们的学员已经广泛就职于BAT360等各大IT互联网公司。详情请参考我们的 业界反馈 《周哥教IT.C语言深学活用》视频

我们的微信公众号,敬请关注