算法

算法广义上是指一种确定的,有穷的和可执行的,用来解决问题的指令。我们这里要讨论的算法的范围定义相对较窄,主要指的是能够解决某个问题的一个程序。任何可以解决问题的程序都可以称之为算法,但正如数学里我们有各种定理一样,某些经典的算法可以为解决其它问题提供良好的基础。这篇文章的主要目的即是将我收集到的各种经典算法罗列出来,方便学习和参考。

排序

选择排序(Selection Sort)

选择排序是一种最简单直观的排序算法。中心思想是在未排序的序列中,找出最小(最大)的元素,将其放在序列的最前端,并归为已经排序的序列,然后再在剩下的未排序序列中继续寻在最小(最大)的元素,放到最前端。以此类推,直到处理完所有的未排序元素。

插入排序(Insertion Sort)

插入排序是我们在整理扑克牌手牌的时候不自觉会用到的一种排序方法。基本原理是构造一个一开始为空的有序序列,然后不停地在未排序的序列中抓取一个元素放入有序序列中,直至未排序序列为空。在将新元素放入有序序列的时候,对已经在序列里的元素由后向前依次进行扫描,找出适合当前元素插入的位置,以使每次插入后序列依然保持有序。

冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法。他的名字来源于在运算过程中,未完成排序的较小(较大)元素会随着它运行慢慢往排序好的序列浮,就像水中的气泡一样。冒泡排序的基本原理是重复地走访尚未完成排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。每一轮走访,未排序中的最小(最大)元素就会被交换到最末端。重复走访数列的工作直到没有再需要交换,测试整个序列就已经完成排序。

希尔排序(Shell Sort)

希尔排序是插入排序的一个改进版本。希尔排序的改进基础在于插入排序具有对接近正序(partially sorted)的序列能高效进行排序的特性,通过对精心选择的部分元素进行排序,让整个序列趋近于正序,最终完成排序。

归并排序(Merge Sort)

归并排序是建立在分治法(divide and conquer)思想上的一种排序方法。基本的原理是把要排序的序列先分成两半,然后对各半个序列分别进行归并排序,然后再将排好序的半个序列用归并操作合成一个有序的完整序列。

快速排序(Quick Sort)

快速排序是现今为止不管是理论上还是实际上都是最高效的一种通用排序方法。它使用分治法(Divide and conquer)策略来把一个序列分为较小和较大的2个子序列,然后递归地排序两个子序列。

搜索

二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

图论

字符串