对程序员有帮助的五大基础实用算法

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

算法步骤:

1. 从数列中挑出一个元素,称为「基准」(pivot),

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

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

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

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

算法步骤:

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

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

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

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

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

算法四:二分查找算法

算法五:BFPRT(线性查找算法)

算法步骤:

1. 将 n 个元素每 5 个一组,分成 n/5(上界) 组。

2. 取出每一组的中位数,任意排序方法,比如插入排序。

3. 递归的调用 selection 算法查找上一步中所有中位数的中位数,设为 x,偶数个中位数的情况下设定为选取中间小的一个。

4. 用 x 来分割数组,设小于等于 x 的个数为 k,大于 x 的个数即为 n-k。

5. 若 i==k,返回 x;若 i

转载请注明:《对程序员有帮助的五大基础实用算法