2016-08-28 crane-yuan
定义 选择排序(英语:Selection sort)是一种简单直观的排序算法。它首先在未排序的序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。 more 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。 算法步骤 选择排序算法的运作如下: 首先在未排序序列中找到最小(大)元素,存放到排序 继续阅读 »
2016-08-29 crane-yuan
定义 插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。 more 算法步骤 插入排序算法的运作如下: 从第一个元素开始,该元素可以认为已经被排序 取出下一个元素,在已经排序的元素序列中从后向前扫描 如果该元素(已排序)大于新元素,将该元素移到下一位置 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复 继续阅读 »
2016-08-30 crane-yuan
概念 归并排序(英语:Merge sort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n)。 归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。 more 递归法 原理如下(假设序列共有n个元素): 1. 将序列每相邻两个数字进行归并操作,形成floor(n/2)个序列,排序后每个序列包含两个元素 2. 将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素 3. 重复步骤2,直到所有元素排序完毕 迭代法 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排 继续阅读 »
2016-09-03 crane-yuan
定义 快速排序(英语:Quick Sort),又称划分交换排序(partition-exchange sort),一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n)算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。 more 算法步骤 快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)。 步骤为: 从数列中挑出一个元素,称为"基准"(pivot), 重新排序数列 继续阅读 »
2016-09-05 crane-yuan
定义 基数排序(英语:Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。 more 算法步骤 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。 然后,从最低位开始,依次进行一次排序。 这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。 基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由 继续阅读 »
2016-10-12 crane-yuan
基本问题 如何删除单链表中的倒数第n个节点? 常规解法 先遍历一遍单链表,计算出单链表的长度,然后,从单链表头部删除指定的节点。 more 代码实现 ``` java /** 删除单链表倒数第n个节点,常规解法. * * @param head * @param n * @return ListNode */ public static ListNode removeNthFromEnd(ListNode head, int n) { if(head == null) { return null ; } //get length of list ListNode p 继续阅读 »
2016-07-05 jude
这是一个基础算法系列,主题是:为什么知道原理还是写不出正确的程序呢? 第一篇已经写好,叫做我尝试去写快排,结果。。。。文章结构都差不多:原理、联想、用法、框架、分步实现、完整代码及测试用例。 原理 插入排序的原理是: - 将集合分为两个部分:已排好的部分和待排序的部分 - 每次从待排序部分抽一个元素跟已排好部分中的元素逐一比较,直到找到合适的位置,插入待排序元素 - 合适的位置可以是第一个比待排序元素小(大)的,也可能是已排好部分的下界 继续阅读 »
2016-10-10 crane-yuan
基本问题 如何将单链表反转? 单链表结构定义 ``` java /** 单链表定义 * * @author: crane-yuan * @date: 2016-9-17 下午12:11:13 */ public class ListNode { public int val; public ListNode next; public ListNode(int x) { val = x; } } ``` more 算法实现 java /** 单链表反转 * * @param head * @return ListNode */ public static ListNode rever 继续阅读 »
2014-01-15 W.Y.
算法原理 桶排序 (Bucket sort)或所谓的箱排序的原理是将数组分到有限数量的桶子里,然后对每个桶子再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序),最后将各个桶中的数据有序的合并起来。 排序过程: 1. 假设待排序的一组数统一的分布在一个范围中,并将这一范围划分成几个子范围,也就是桶 2. 将待排序的一组数,分档规入这些子桶,并将桶中的数据进行排序 3. 将各个桶中的数据有序的合并起来 Data Structure Visualizations 提供了一个桶排序的分步动画演示。 more 实例分析 设有数组 array = [29, 25, 3, 49, 9, 37, 21, 43],那 继续阅读 »
2016-05-22 MoreFreeze
学习了下LevelDB的实现原理,发现G厂大神Jeff Dean果然牛B,实现也很巧妙。 参考链接是这里 继续阅读 »