设为首页收藏本站

                      LUPA开源社区

                       ?#19968;?#23494;码
                       注册
                      文章 帖子 博客
                      LUPA开源社区 首页 业界资讯 技术文摘 查看内容

                      十大编程算法助程序员走上高手之路

                      2014-8-28 16:14| 发布者: joejoe0332| 查看: 388460| 评论: 15|原作者: techug|来自: techug

                      摘要: 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比 较,但这种状况并不常见。事实上,快速排序通常明?#21592;?#20854;他Ο(n log n) 算法更快,因 ...

                      算法一:快速排序算法

                        快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比 较,但这种状况并不常见。事实上,快速排序通常明?#21592;?#20854;他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构 上很有效?#23454;?#34987;实现出来。



                        快速排序使用?#31181;?#27861;(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

                      算法步骤:

                      1 ?#37038;?#21015;中挑出一个元素,称为 “基准?#20445;╬ivot),

                      2 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,?#27809;?#20934;就处于数列的中间位置。这个称为分区(partition)操作。

                      3 递归地(recursive)把小于基准值元素的?#37038;?#21015;和大于基准值元素的?#37038;?#21015;排序。

                      递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。


                      算法二:堆排序算法

                      堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

                      堆排序的平均时间复杂度为Ο(nlogn) 。

                      算法步骤:

                      创建一个堆H[0..n-1]

                      ?#35759;?#39318;(最大值)和堆?#19981;?#25442;

                      3. ?#35759;?#30340;尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整?#36739;?#24212;位置

                      4. 重复步骤2,直到堆的尺寸为1


                      算法三:归并排序

                      归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用?#31181;?#27861;(Divide and Conquer)的一个非常典型的应用。

                      算法步骤:

                      1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

                      2. 设定两个指针,最初位置?#30452;?#20026;两个已经排序序列的起始位置

                      3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

                      4. 重复步骤3直到某一指针达到序列尾

                      5. 将另一序列剩下的所有元素直接复制到合并序列尾

                      6

                      酷毙

                      雷人

                      鲜花

                      鸡蛋

                      漂亮

                      刚表态过的朋友 (6 人)

                      • 快毕业了,没工作经验,
                        找份工作好难啊?
                        赶紧去人才芯片公司磨练吧!!

                      最新评论

                      关于LUPA|人才芯片工程|人才招聘|LUPA?#29616;?/a>|LUPA教育|LUPA开源社区 ( 浙B2-20090187  

                      返回顶部
                      双色球中奖图片

                                                              NW新世界棋牌太假了 北京赛车pk10开奖搜狐 北京福彩pk10彩票 wnba直播 江西时时中奖两千万 多彩网开奖开奖结果 竞彩足球专家稳胆推荐预测 吉林时时中奖规则 内蒙古时时彩平台 象棋残局单机版下载