排序算法总结及习题VIP免费

下载本文档

阅读 88
下载 3
格式 docx
大小 36.51 KB
约7页
2024-11-11 发布于河南
收藏
评论
点赞(0)
海报
举报

1/7页

2/7页

3/7页

在线预览已结束，请下载后查看完整版，加入VIP享文档下载特权

文本预览下载提示常见问题

排序算法总结及习题一、概述排序是最基础和常用的算法之一，一般情况下，排序不开比较、数据交换，怎样降低算法的时间及空间复杂性是算法设计的目标，尽管经典算法已有不少，但研究一直不断，2001年还有综合性能很好的新算法出现。为了对n个元素的线性表进行排序，至少必须扫描一遍以获取n各元素，因此排序问题的计算复杂性下界为：Ω(n)如果对输入的数据不做任何要求，则仅能通过比较来确定输入序列各元素间的顺序。无论算法采用怎样的比较策略/顺序，总能对应一个两两比较序列，考察所有可能则可对应一棵决策树。例如：a1:a2(<=)/\(>)(a1a2)(a2a1)树的非叶子结点表示一次比较，叶子结点对应一个可能的结果队列。显然树高度为比较次数。可以为任意的输入，叶子结点数目为n!高度最小情况为满二叉树，则2h=n！一般情况下：2h>=n!,则h>=log2n!>log2(n/e)n=nlogn-nloge则任意分布数据，算法复杂性下界：Ω(nlogn)二、常用基本算法及思想名次排序、冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。1.名次排序（1）计算名次voidRank(Ta[],intn,intr[]){//计算a[0:n-1]中n个元素的排名for(inti=0;i

1、当您付费下载文档后，您只拥有了使用权限，并不意味着购买了版权，文档只能用于自身使用，不得用于其他商业用途（如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利）。
2、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。
3、如文档内容存在违规，或者侵犯商业秘密、侵犯著作权等，请点击“违规举报”。

碎片内容

排序算法总结及习题

您可能关注的文档

精品中小学资料 + 关注: 实名认证
内容提供者

精品文档

收藏店铺进入空间

排序算法总结及习题VIP免费

排序算法总结及习题

您可能关注的文档

热门下载

相关标签