归并排序(Merge sort)

很多的算法都是递归的结构,递归的目的呢,是在自己调用自己的时候,将问题分解成更小的问题,这个过程也叫做divide-and-conquer,通过把原来的问题的一个大问题,分解成一个更小的问题,再把更小的问题分解成微不足道的问题,再一一解决所有所有的问题。
devide-and-conquer一般是这样来解决问题的:
Divide:将问题分解成更小的,但是相似的问题
Conquer:递归解决这些小问题,如果小问题已经足够小,直接解决;否则可以重复Divide的过程
Combine:将解决小问题的方案合并和大的解决方案中,从而解决更大的问题
今天要说的归并排序,就是这样的一种模式。 继续阅读归并排序(Merge sort)

二分查找(binary search)

二分查找又叫折半查找,要查找的前提是检索结果位于已排序的列表中。

概念

在一个已排序的数组seq中,使用二分查找v,假如这个数组的范围是[low…high],我们要的v就在这个范围里。查找的方法是拿low到high的正中间的值,我们假设是m,来跟v相比,如果m>v,说明我们要查找的v在前数组seq的前半部,否则就在后半部。无论是在前半部还是后半部,将那部分再次折半查找,重复这个过程,知道查找到v值所在的地方。
实现二分查找可以用循环,也可以递归,先给出两种方式的伪代码。
继续阅读二分查找(binary search)

排序算法 – 选择排序(selection sort)

选择排序(Selection sort)跟插入排序一样,也是O(n^2)的复杂度,这个排序方式也可以用我们的扑克牌来解释。

概念

桌面上有一堆牌,也是杂乱无章的,现在我们想将牌由小到大排序,如果使用选择排序来做,应该是这样来做。
1. 遍历桌面牌堆里的牌,从第一张牌到最后一张,找到牌面最小的一张,然后将抽出,并扣在手上。
2. 第二次遍历桌面牌堆里的牌,从第一张牌到最后一张,仍然去找现在桌面上牌面最小的一张,找出来,还是扣在手上。
3. 第三次遍历……重复步骤。虽然桌面上的牌是无序的,但是我们扣在手上的牌是有序的。
4. 第N次遍历……重复直到结束,现在桌面上没有牌,所有的牌都抓在手里,而且手上的牌全是排序排好的。
这个过程就是选择排序。
继续阅读排序算法 – 选择排序(selection sort)

排序算法 – 插入排序(Insertion sort)

插入排序对于少量元素的排序是很高效的,而且这个排序的手法在每个人生活中也是有的哦。
你可能没有意识到,当你打牌的时候,就是用的插入排序。

概念

从桌上的牌堆摸牌,牌堆内是杂乱无序的,但是我们摸上牌的时候,却会边摸边排序,借用一张算法导论的图。

每次我们从牌堆摸起一张牌,然后将这张牌插入我们左手捏的手牌里面,在插入手牌之前,我们会自动计算将牌插入什么位置,然后将牌插入到这个计算后的位置,虽然这个计算转瞬而过,但我们还是尝试分析一下这个过程:
1. 我决定摸起牌后,最小的牌放在左边,摸完后,牌面是从左到右依次增大
2. 摸起第1张牌,直接捏在手里,现在还不用排序
3. 摸起第2张牌,查看牌面大小,如果第二张牌比第一张牌大,就放在右边
4. 摸起第3张牌,从右至左开始计算,先看右边的牌,如果摸的牌比最右边的小,那再从右至左看下一张,如果仍然小,继续顺延,直到找到正确位置(循环)
5. 摸完所有的牌,结束
所以我们摸完牌,牌就已经排完序了。
讲起来有点拗口,但是你在打牌的时候绝对不会觉得这种排序算法会让你头疼。
这就是传说中的插入排序。
继续阅读排序算法 – 插入排序(Insertion sort)