设为首页收藏本站

LUPA开源社区

 找回密码
 注册
文章 帖子 博客
LUPA开源社区 首页 业界资讯 技术文摘 查看内容

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

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

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

算法一:快速排序算法

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



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

算法步骤:

1 从数列中挑出一个元素,称为 “基准”(pivot),

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

3 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

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


算法二:堆排序算法

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

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

算法步骤:

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

把堆首(最大值)和堆尾互换

3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

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


算法三:归并排序

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

算法步骤:

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

2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置

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

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

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

6

酷毙

雷人

鲜花

鸡蛋

漂亮

刚表态过的朋友 (6 人)

发表评论

最新评论

引用 游客 2017-7-11 17:27
开心就好
引用 游客 2017-5-4 15:10
作者要是能用通俗易懂的方式,或者说以自己理解的方式将这些算法讲出来,那就好了。
引用 游客 2017-3-31 15:35
图做的不错,然并卵,有些不懂的依然不懂。
引用 游客 2017-3-24 17:13
学习了
引用 游客 2017-2-9 11:05
太给力了!
引用 游客 2016-11-25 13:56
神马都是浮云!
引用 游客 2016-11-22 17:13
顶!
引用 游客 2016-10-24 17:21
动画做的非常好
引用 游客 2016-10-24 14:11
H[0..n-1]这是啥东西,看不懂
引用 游客 2016-9-25 17:17
元芳,你怎么看?
引用 游客 2016-8-25 08:57
666
引用 游客 2016-8-6 08:21
动态规划是一种思想吧,不是算法
引用 游客 2016-6-3 11:31
: 与其说这些算法 还不如把思想说出来
思想说出来?也是感人,这个只是说书有哪些算法,而且网上一搜就有,何必多此一举。
引用 游客 2015-10-31 16:25
与其说这些算法 还不如把思想说出来

查看全部评论(14)

(200字以内)
验证问答 换一个 验证码 换一个

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

最新评论

关于LUPA|人才芯片工程|人才招聘|LUPA认证|LUPA教育|LUPA开源社区 ( 浙B2-20090187  

返回顶部