费氏搜索(Fibonacci Search)算法,运用费氏数列的搜索算法
费氏搜索(Fibonacci Search)算法有点像是二元搜索(Binary Search)算法,同样是在一个已排序好的数组中搜索元素,但是它在移动数组索引值时是去参考费氏数列(Fibonacci Sequence),而不是像二元搜索法那样总是去取索引的中间值。也由于费氏搜索法在移动数组索引值时只需要进行加减运算,不需乘、除法,因此它适合被用在不擅长处理乘、除法的 CPU 上。
MagicLen · https://magiclen.org
本站也提供繁體中文版。切換到繁體中文版
分类
Go 编程语言(也称为 Golang)的文章,以用 Go 实作的各种算法与实用程序范例为主。
共 31 篇文章
费氏搜索(Fibonacci Search)算法有点像是二元搜索(Binary Search)算法,同样是在一个已排序好的数组中搜索元素,但是它在移动数组索引值时是去参考费氏数列(Fibonacci Sequence),而不是像二元搜索法那样总是去取索引的中间值。也由于费氏搜索法在移动数组索引值时只需要进行加减运算,不需乘、除法,因此它适合被用在不擅长处理乘、除法的 CPU 上。
基数排序(Radix Sort)算法是可以利用多个键值来排序数据的算法。排序还需要多个键值?有时候当然会需要啦!像是要排序文件时,可以先依照文件名称排序后,再依照文件大小来排,如此一来,整体上来看这些文件,会是以文件大小来排序,而相同文件大小的文件则是会依照文件名称来排序。基数排序法可以将整数的各个位数当作是键值,来进行线性时间的排序,比起会依照 k(要排序的数据可能的值的数量)愈大而愈吃空间的计...
桶排序(Bucket Sort)算法是先将大量数据分类成少量数据后,再进行排序的算法。可以透过简单的表达式来完成数据的分类,在最好的情况之下,数据可以被完全打散,此时的时间复杂度就会是一个线性时间。
暴力字符串搜索(Brute-force Substring Search)算法是最基本的字符串搜索算法。它可以按照原文中字符的顺序,逐一与搜索样本(pattern)进行比对,判断目前的搜索位置是否就是搜索样本存在的位置。
插补搜索(Interpolation Search)算法又称为内插搜索算法,是二元搜索(Binary Search)算法的变体。这套算法可以在已排序好的串行中根据数据的预测线或近似线来进行高效率的搜索,近似线愈精准,搜索的效率就愈高。
指数搜索(Exponential Search)算法又称为双倍搜索(Doubling Search)算法或是蔓延搜索(Galloping Search)算法,是二元搜索(Binary Search)算法的变体。这套算法可以在已排序好的串行中进行高效率的搜索,要搜索的元素在串行中愈前面的话,搜索性能愈好。
二元搜索(Binary Search)算法又称为二分搜索(Half-Interval Search)算法或是对数搜索(Logarithmic Search)算法,顾名思义,这套算法的核心思想就在于「二分」,可以在已排序好的串行中进行高效率的搜索。
线性搜索(Linear Search)算法又称为循序搜索(Sequential Search)算法,是学习编程语言最先需要学会的搜索算法。它可以按照元素在数据结构中的顺序,从头开始进行走访,并连续判断目前走访到的元素是否是我们想要找的元素。
堆积排序(Heap Sort)算法是利用完全二元树(Complete Binary Tree),也就是堆积(Heap)结构来完成排序的算法。虽然说要用到堆积结构,看起来好像很复杂似的,但其实这个只要一般的数组结构(可以直接用要排序的数组来制作)就能实作出来,而且实作出来的速度保证不会太慢,再怎么差都会有 O(nlogn) 的时间复杂度。
合并排序(Merge Sort)算法是非常通用的排序算法,是稳定排序,即便在最差的情况下也还有 O(nlogn) 的时间复杂度。