排序

1、插入排序

void runsub5()

{

    int array[10] = {7,6,3,2,0,5,4,9,1,8};

    int result[10] = {};

    int i,j;

    for (i=0;i<10;++i)

    {

        cout<

    }

    cout<

    for (i=1;i<10;++i)//将array[1],...,array[9]分别插入

    {

        if(array[i]

        {

            for(j=i;j>0;--j)//计算array[i]的插入位置

            {

                if(array[j]

                {

                    int tmp=array[j-1];

                    array[j-1]=array[j];

                    array[j]=tmp;

                }

                else

                {

                    break;

                }

            }

        }

    }

    for (i=0;i<10;++i)

    {

        cout<

    }

    cout<

}

2、希尔排序

希尔排序基本思想是：通过分组来，来对各个组内的元素进行排序，随着分组的逐渐粗化，使得整个待排序记录由无序到基本有序，再到有序的过程。

这里需要注意这两种插入排序算法各自的优点和缺点：

直接插入排序，由程序可知他的算法时间复杂度为O(n2)，空间复杂度是O(1)，且是一种稳定的排序算法（即关键字相同的记录，在排序后，相对彼此的顺序没有改变），它适用于待排序记录按关键字基本有序或是待排序记录较少的情况，在这些情况下，效率较高。

希尔排序，时间复杂度是O(nlog2n)，空间复杂度是O(1)，是一种不稳定的算法（因为在分组时可能把两个关键字相同的记录分到不同的组，这样在排序时两者就不能比较了），它的性能在待排序的记录有较多时能得到充分的发挥。

阅读(1694) | 评论(0) | 转发(0) |

0

上一篇：C++汇总

下一篇：链表

给主人留下些什么吧！~~

评论热议

请登录后评论。

登录 注册

关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6