定义
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
more
算法步骤
插入排序算法的运作如下：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后
重复
继续阅读 »
定义
快速排序（英语：Quick Sort），又称划分交换排序（partition-exchange sort），一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
more
算法步骤
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
步骤为：
从数列中挑出一个元素，称为"基准"（pivot），
重新排序数列
继续阅读 »
定义
基数排序（英语：Radix Sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
more
算法步骤
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
然后，从最低位开始，依次进行一次排序。
这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由
继续阅读 »
这是一个基础算法系列，主题是：为什么知道原理还是写不出正确的程序呢？
第一篇已经写好，叫做我尝试去写快排，结果。。。。文章结构都差不多：原理、联想、用法、框架、分步实现、完整代码及测试用例。
原理
插入排序的原理是：
- 将集合分为两个部分：已排好的部分和待排序的部分
- 每次从待排序部分抽一个元素跟已排好部分中的元素逐一比较，直到找到合适的位置，插入待排序元素
- 合适的位置可以是第一个比待排序元素小（大）的，也可能是已排好部分的下界
继续阅读 »
最近整理了一些常见的排序算法，资料基本上都来自网上，大部分参考了维基百科，分析了常见算法的原理，并举例分步说明，有的还给出了排序动画演示，但没有涉及算法复杂度等方面的概念，最后对每一种排序算法都给出了至少一种 JavaScript 的实现方法（因为我是做前端方面的，所以只给出了 JavaScript 代码）。
由于自己能力和经验有限，难免出现某些纰漏和错误，欢迎指正。
日本程序员 norahiko，写了一个排序算法的动画演示，非常有趣。另外，今天一同事告诉我有一个排序算法的舞蹈，请点击【程序员的艺术：排序算法舞蹈】。
常见排序算法 - 冒泡排序 (Bubble Sort)
常见排序算法 - 快速排序 (Quick Sort)
继续阅读 »
算法原理
桶排序 (Bucket sort)或所谓的箱排序的原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。
排序过程：
1. 假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶
2. 将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序
3. 将各个桶中的数据有序的合并起来
Data Structure Visualizations 提供了一个桶排序的分步动画演示。
more
实例分析
设有数组 array = [29, 25, 3, 49, 9, 37, 21, 43]，那
继续阅读 »
生成二叉树
type Node struct {
data string
left *Node
right *Node
}
nodeG := Node{data: "g", left: nil, right: nil}
nodeF := Node{data: "f", left: &nodeG, right: nil}
nodeE := Node{data: "e", left: nil, right: nil}
nodeD := Node{data: "d", left: &nodeE, right: nil}
nodeC := Node{data: "c", left: nil, right:
继续阅读 »
题目描述
给定一个已排序的单链表，去除单链表中的重复元素，只保留一个重复的元素，并且返回新的单链表。
例如：
给出1->1->2，你的函数调用之后必须返回1->2。
输入
一个已排序的单链表，例如1->1->2。
输出
返回1->2。
代码示例
``` 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;
继续阅读 »
连连看是一种益智游戏，其核心算法是要在一个M * N的矩阵上找出两个点的“最短路径”，满足：1. 转弯数最少 2. 经过的点最少。谈到图的两点间最短路径，我们会想到用于无权图的广度优先搜索（BFS）和带权图的Dijkstra算法。那么对于连连看的M * N矩阵来说，究竟可以抽象成有权图呢还是无权图？如果有，权重又是什么呢？
继续阅读 »
算法原理
希尔排序算法是按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布，是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
- 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位
算法思路：
1. 先取一个正整数 d1(d1 < n)，把全部记
继续阅读 »