C语言中的插入排序(2016-12-30)

直接插入排序:

算法思想:假设待排序的记录存放在数组R[1……n]中,初始时,i=1,R[1]自成一个有序区,无序区为R[2……n].然后从i=2起直到i=n,依次将R[i]插入当前的有序区R[1...n-1]中,最后,生成含n个的记录的有序区。

算法实现:

void insertsort(Reqlist R)

{

  int i,j;

  for(i=2;i<=n;i++)//从第二个数字开始插入排序

  {

    R[0]=R[i];//R[0]作为哨兵,一方面暂存数据,另一方面,检测下标j是否越界(2)

    j=i-1;

    while(R[0].key<R[j].key)//(2)

    {

      R[j+1]=R[j];

      j--;

    }

    R[j+1]=R[0];

  }

}

算法复杂度计算:

  当待排序的n个数据为正序时候,算法复杂度为O(n);

  当待排序的n个数据为反序时候,算法复杂度为O(n^2);

  当待排序的n个数据为乱序时候,算法复杂度为O(n^2);

希尔排序:

希尔排序是插入排序的一种,也称为“缩小增量排序”

 基本思想:是把待排序的记录一组记录按照增量分成若干个小组(以n个数据为例,分成了若干次的n/2个小组(小组内都有俩个记录),但是每次组内的两个数据之间的间距不一样,即增量d不同),分别进行组内直接插入排序,待整个序列中的记录“基本有序时候”,再对全体记录进行依次直接插入排序,这样大大减少了记录的移动次数,提高了算法的排序效率。

算法的实现如下://与直接插入排序基本一样,只不过是把数据之间的比较间距由原来的1拉大到d

  void shellsort(Sqlist R,int n)//n为待排序的记录的个数

  {

    int i,j;

    d=n/2;

    while(d>0)

    {

      for(i=d+1;i<=n;i++)//从第d+1个数据开始,与相应的前面的第(i-d)个数据进行比较,采用插入思想进行排序

      {

        R[0]=R[i];//R[0]作为暂存单元

        j=i-d;

        while(j>0&&(R[0].key<R[j].key))//若干次的小组插入排序

        {

           R[j+d]=R[j];

           j=j-d;

        }

        R[j+d]=R[0];

      }

      d=d/2;

    }

  }

算法的复杂度为O(n^2);希尔排序不稳定

上一篇:SVN Error:请求的名称有效并且在数据库中找到,但是它没有相关的正确的数据来被解析


下一篇:枚举类型Enum