C语言插入排序&希尔排序

2020年01月07日 167点热度 2人点赞 0条评论

1.插入排序

插入排序,顾名思义是将一个数取出再插入到数组中合适位置,通过多次插入使得数组呈有序状态的一种排序算法.
时间复杂度:O(n^2),被称为最稳定的排序算法,它适用于数据量较少的排序.

算法步骤(从小到大):

  1. 将数组视作两部分,一部分有序一部分无序,初始时有序部分为左边第一个元素.
  2. 选择有序部分后一个元素将其取出,将其与有序部分最后一个元素比较,有序部分最后一个元素大于该元素,就将有序部分最后一个元素后移,然后该元素继续与有序部分前一个元素对比,直到找到有序部分某个元素小于该元素或到达有序部分最前端,就插入到找到的元素的后面。
  3. 插入好之后选取下一个元素再次与有序部分对比插入,直到选取的元素为最后一个元素。

下面还是看一个栗子:

我有一组数:5 8 3 1 4 2,绿色为有序部分,红色为选择进行比较的元素.

5 8 3 1 4 2                cur=8

选择的8>5发现位置合适,不移动

5 8 3 1 4 2                cur=3

选择3<8不合适,将8后移,原来8的地方视为空(蓝色)

5 8 8 1 4 2                cur=3

3>5发现不合适,将5后移,原来5的地方视为空(蓝色)

5 5 8 1 4 2                cur=3

发现已经到了头部,就将cur=3插入

3 5 8 1 4 2                cur=1

重复上述过程,将1插入

1 3 5 8 4 2                cur=4

将4插入

1 3 4 5 8 2                cur=2

将2插入

1 2 3 4 5 8

数组有序排序完成。

根据算法写出c代码

void insertSort(int a[],int lenth)
{
    int i,cur,j;
    for(i=1;i<lenth;i++)
    {
        cur=input[i];
        for(j=i-1;j>=0&&input[j]>cur;j--)
        {           
            input[j+1]=input[j];//后移
        }   
        input[j+1]=cur;//将拿出的元素插入
    }
}

2.希尔排序

希尔排序是对插入排序进行的一种优化,时间复杂度O(n^(1.3—2)),不稳定。

插入排序最适合的情况是数组有序性高,数据量小的情况,希尔排序就是看中了插入排序的这个特点,用了一种分治的思想实现了对它的优化。

算法步骤.

1.选择一个增量(第一次一般选择lenth/2)

2.将距离为增量的元素看做一个数组

3.对每个数组进行插入排序。

4.将增量减半再回到第二步,直到增量为0

还是举个例子有一组数:5 8 3 1 4 2

选择一个增量incre=lenth/2得到3,分成三组蓝绿红,分别对他们排序.

再将incre=incre/2 得到1 4 2 5 8 3 的顺序 ,再按incre=1排序得到如下绿色部分

incre=incre/2得到incre==0  排序完成.

写成代码如下:

void shellSort(int input[],int lenth)
{
    int i,incre,cur;
    for(incre=lenth/2;incre>=1;incre/=2)
    {
        for(i=incre;i<10;i++)//插入排序
        {
            cur = input[i];
            for(j=i-incre;j>=0&&input[j]>cur;j-=incre)
            {
                input[j+incre]=input[j];
            }
            input[j+incre]=cur;
        }
    } 
}




Danny

我就如一粒石子,在随波逐流中,逐渐冲蚀了自己的棱角,变光滑,也变丑陋。

文章评论