插入排序

作者: admin 分类: 算法 发布时间: 2013-02-16 13:03 ė1,287 浏览数 6没有评论
文章转自王牌软件
站长推荐:NSetup一键部署软件
一键式完成美化安装包制作,自动增量升级,数据统计,数字签名。应对各种复杂场景,脚本模块化拆分,常规复杂的脚本代码,图形化设置。无需专业的研发经验,轻松完成项目部署。(www.nsetup.cn)

插入排序InsertionSort,参数是一个数组包含了n个待排序的数,输入的各个数字是原地排序的(sorted in place),意即这些数字就是在数组A中进行重新排序的,在任何时刻,至多只有其中的常数个数字是存储在数组之外的,当过程InsertionSort执行完毕后,输入数组A中就包含了已排好序的数组输出序列。

下面是利用C++语言实现的插入排序代码:

插入排序的算法复杂性分析:对于插入排序,它的复杂性依赖于待排序数组的一些属性,待排序数组长度、已排好序程度等。我们一般考察最坏情况下即逆序排序和最佳情况下即已排好序的复杂性。

最佳情况下:此时待排序数组已经是一个排好序的数组,推理可得程序运行时间可以表示为an+b;因此,它是n的一个线性函数。

最坏情况下:此时待排序数组是一个逆序数组,此时,我们必须把每个元素array[i]与整个已排序的子数组array[1...i-1]中的每个元素进行比较,因而,最坏情况下程序的运行 时间为an^2+bn+c,这是一个关于n的二次函数。

一般来说,如同插入排序一样,一个算法的运行时间对某一给定的输入来说,往往是固定的。



只回答业务咨询点击这里给我发消息 点击这里给我发消息

王牌软件,兼职软件设计,软件修改,毕业设计。

本文出自 王牌软件,转载时请注明出处及相应链接。

本文永久链接: http://www.softwareace.cn/?p=169

0

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">


Ɣ回顶部

无觅相关文章插件,快速提升流量