- 1、本文档共15页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
算法排序
/xiajuarticle/details/6898246
下面简要总结了常用的一些排序算法。如有错误,还请大家指正、见谅~~谢谢~~
【1】插入排序:
是一个对少量元素进行排序的有效算法。实现比较简单。时间复杂度:O(n^2),空间复杂度:O(1)。是稳定的排序方法。
代码:
view plaincopy to clipboardprint?
//insertion?sort ??
#include?iostream ??
using?namespace?std;??
??
//insertion?sort ??
void?InsertionSort(int?*a,int?n)??
{??
????int?temp;??
????for(int?i?=?1;i??n;++i)??
????{??
????????temp?=?*(a?+?i);??
????????int?j?=?i?-?1;??
????????while(j?=?0??*(a?+?j)??temp)??
????????{??
????????????*(a?+?j?+?1)?=?*(a?+?j);??
????????????--j;??
????????}??
????????*(a?+?j?+?1)?=?temp;??
????}??
}??
??
int?main()??
{??
????int?n,temp;??
????coutplease?input?the?number?of?the?values?that?need?to?sort:endl;??
????cinn;??
????int?*a?=?(int*)malloc(n?*?sizeof(int));??
????coutplease?input?each?value:endl;??
????for(int?i?=?0;i??n;++i)??
????{??
????????cintemp;??
????????*(a?+?i)?=?temp;??
????}??
????/*?
????//insertion?sort?
????for(int?i?=?1;i??n;++i)?
????{?
????????temp?=?*(a?+?i);?
????????int?j?=?i?-?1;?
????????while(j?=?0??*(a?+?j)??temp)?
????????{?
????????????*(a?+?j?+?1)?=?*(a?+?j);?
????????????--j;?
????????}?
????????*(a?+?j?+?1)?=?temp;?
????}*/??
????InsertionSort(a,n);??
??
????coutthe?values?after?sort:endl;??
????for(int?i?=?0;i??n;++i)??
????????cout*(a?+?i)?;??
view plaincopy to clipboardprint?
free(a);??
view plaincopy to clipboardprint?
}??
数据测试:
上述代码可以改进的一个地方是:在查找插入位置的时候可以采用二分查找,但是这样依然不可以把时间复杂度降低为O(nlogn),因为移动元素的复杂度没有降低。所以时间复杂度仍然是O(n^2)。
做此改进需要添加函数InsertLoc用于二分查找需要插入的位置,以及修改函数InsertionSort的实现。具体如下:
view plaincopy to clipboardprint?
//改进:用二分查找来找到插入的位置 ??
//在数组a[low]a[high]查找val插入的位置 ??
int?InsertLoc(int?*a,int?low,int?high,int?val)??
{??
????if(low?==?high)??
????{??
????????if(val??*(a?+?low))return?(low?+?1);??
????????else??
????????????return?low;??
????}??
????int?mid?=?(low?+?high)?/?2;??
????if(val??*(a?+?mid)??val??*(a?+?mid?+?1))??
????????return?InsertLoc(a,mid?+?1,high,val);??
????else?if(val??*(a?+?mid)??val??*(a?+?mid?+?1))??
????????return?InsertLoc(a,l
文档评论(0)