My Blogs
Bash 使用技巧
Published 2013年01月10日 22:30 by james
Bash 参数说明
$#是传给脚本的参数个数$0是脚本本身的名字$1是传递给该shell脚本的第一个参数$2是传递给该shell脚本的第二个参数$@是传给脚本的所有参数的列表$*是以一个单字符串显示所有向脚本传递的参数，与位置变量不同，参数可超过9个$$是脚本运行的当前进程ID号$?是显示最后命令的退出状态，0表示没有错误，其他表示有错误
Bash 一行流
回溯算法Ruby实现
Published 2011年02月14日 10:52 by james
什么是回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
算法实现
算法准备
准备一个默认的打印函数，把数组a中的数组转换成字母打印出来。
ALPHABET = Array('A'..'Z')
DISPLAY = lambda {|a| p a.map{|i …回溯算法Python实现
Published 2010年01月01日 19:52 by james
什么是回溯法
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。 若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
算法实现
算法准备
准备一个默认的打印函数，把数组a中的数组转换成字母打印出来。
def display(a):
l = ['A', 'B', 'C', 'D', 'E', 'F', 'G', …归并排序(C语言描述)
Published 2009年10月10日 16:52 by james
归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序算法以O（nlogn）最坏情形运行时间运行，而所使用的比较次数几乎是最优的。但它的一个显著问题就是需要额外的存储空间来辅助排序，空间复杂度是O(n)的，与quicksort和heapsort相比就逊色了不少，不过也可以实现空间复杂度为O（1）的归并排序，这将增加比较操作和交换操作的次数。归并排序可以使用在外部排序上：一般两路的外部排序是从源文件里读出内存大小的一块，然后在内存中排序，在放回文件里，这样生成若干文件。然后在从其中两个文件中读数据，按照merge的方式写到另一个文件中去。这一步根本用不到辅助空间。唯一可能用到辅助空间的地方是前面的一步，即将一块数据在内存中排序。
归并操作
归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。
归并操作的工作原理如下：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针达到序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
归并排序
归并排序具体工作原理如下（假设序列共有n个元素）:
- 将序列每相邻两个数字进行归并操作（merge），形成floor(n / 2)个序列，排序后每个序列包含两个元素
- 将上述序列再次归并，形成floor(n / 4)个序列，每个序列包含四个元素
- 重复步骤2，直到所有元素排序完毕
算法演示1 （非递归版本）:
#include<stdio.h>
#include<stdlib.h>
void merge( …堆排序(C语言描述)
Published 2009年09月09日 17:15 by james
1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964年共同发明了著名的堆排序算法(Heap Sort)。 n个关键字序列Kl，K2，…，Kn称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质)：
(1) Ki <= K2i且Ki <= K2i+1 或
(2) Ki >= K2i且KI >= K2i+1 (1≤i≤ n)
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
大根堆和小根堆的根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆,又称最小堆. 根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆又称最大堆. 注意： ①堆中任一子树亦是堆. ②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。
堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构)，在当前无序区中选择关键字最大(或最小)的记录。
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
实现一个数从小到大排序，既可以使用大根堆，也可以使用小根堆。 …