最近看到了一道非常有趣的排序问题，这道题是这样的，在图书馆里面，有一个图书管理员需要针对一些图书进行排序，方便管理，但是排序的方法有很多，这个管理员就想到了这样一种方法，如上图所示。图书本来的序列是混乱的，最后我们期望得到的结果序列是有序的，但是这个排序的方法却和普通的排序不太相同，这个方法具体为：管理员拿出其中的一本书，然后按照这个书的序列号，放到相应的为止，其新位置的相关的书籍也随着移动（如果放到前面去了，后面的相应位置的书籍全部后移，如果放到后面去了，则前面的相应位置的书籍全部前移），一直重复这样操作，直到整个书本有序为止。
昨天晚上看了一个题目，这个题目很强，一开始在做的时候，没有考虑那么多，想来想去还是没有什么头绪，后来看到一个哥们写的题目发现特别简单，但是特别难懂，后来查了一下相关资料，哇，确实是一个强题，可能一般人来看这个题目的话，代码可能会写很多，而且效率也不算很高，但是这个标准解答还是很不错的。题目如下。
结果为0的序列：
考虑由1到n(n<=9)按递增顺序排成的序列1234…n,在他们之间加入加号，减号或者什么也不加，分别使它们做加法，减法或者将数字合并。然后求出结果，看看是否为0。
写一个程序，找出所有长度为n的结果为0的序列,返回序列的个数。
函数接口：int ResultIsZero(int n);
其中n表示序列的长度，int表示返回的序列的个数。
今天一个朋友发来一道题，初步看上去好像蛮有挑战的，但是仔细想了一下之后其实好像没那么难，好像也没什么特别的陷阱，琢磨了一下，貌似也真的没什么好检查的，所以觉得也不是很难，但是朋友发的，所以就贴上来告知一下答案了。。哎，其实也没什么好些的，放假的时候无聊的朋友也可以练一下小手。。
已知f[]和g[]两个数组，大小分别为m和n，其中的元素都已经从小到大排列，且每个数组内的元素都各不相同。
例：f[5] = {1,3,4,7,9}, g[4] = {3,5,7,8}; 因为只有2组元素相同，分别是f[1]与g[0] 和 f[3]与g[2]，所以函数Count的返回值应为2。
题目：从M个数中随机的选取N个数。
提示：
* 遍历一次（至少要在O（n））。
* 保证随机（数学上概率相等）。
* 不允许使用随机函数（不是不允许使用，但是注意，不允许在M个数里面利用随机函数随机的取N个数，那就没意义了）。
同样，我把C#/C++代码发在下面。思路在C#代码里面，可以先看思路。这也是我自己和朋友同事讨论的一个方法，不是最好，欢迎讨论。
第一就是关于内存的速度的，其实不难，但是开发的时候想到的很少，能想到的优化的就是高人，我也是路过看到不错，觉得很有用，就贴过来了。
另一个就是《算法导论》了，国外的教材，也是MIT的标准教材，很好很强大，昨天看到了堆排序和快速排序（100页），用了好多张纸证明线性比较排序的上界和下界，堆排序和快速排序的最好的速度是nlogn，从数学角度上证明了线性比较排序（如判断a[1]>a[0]）的最快就是nlogn，也就是说只要你是比较的，而且还是线性的，nlogn就是最快的了。
数学公式太复杂，什么期望啊，概率啊，极限啊，记的不是很清楚，让我自己推倒也没这个能力，不过倒是让我知道了，以后别想线性快速的排序还能超过nlogn了。：）
前面有一篇文章里面我写了LRU算法，其中还将一些算法更新了一下，现在我就做个笔记，写一下LRU算法的一些用途，另外说明一下，这里我们LRU算法都不会考虑空间不足的问题（因为从软件模拟来说基本不会存在这个问题），如果在CPU硬件设计上出现空间不足的话，我们直接将链表的第一个元素剔除即可，当然，也有相应硬件能够直接做这种事情。
当然，LRU不仅仅在硬件设计上有很好的作用，在软件设计上也有很好的作用，例如Orical的数据库就是用了LRU算法。我们可以先看看下面这个图。
Oracle的设计可以从上图看到，这里buffer（缓冲区）就像一个水池，水池的最小单位就是数据块。当每个数据块被读入buffer 时，Oracle或相应的软件都会抽取数据块的头部，在内存中构建buffer header，并将这些buffer header串成链表的形式。而buffer header里面记录的指针就指向buffer中的该数据块本身。于是，当我们在搜索某个数据块时，就不用去缓冲区中找，而是直接扫描链表上该数据块所对应的buffer header，然后根据找到的buffer header所记录的指针就能到buffer中直接定位该数据块了。而维护buffer header就是hash表，而buffer header就是一个LRU维护的链表。
昨天同事说了一道题，这道题说难也难，说简单也简单，但是细节比较麻烦，是个难题，如果这个是面试题的话，确实能够拦下很多人。
题目：有一串字符串，根据字符串生成二叉树，输入输出如下（输出是以树的形式输出）。
输入：{1}
输出：1
输入：{1{2,3}}
输出：根节点1，1的左节点为2，1的右节点为3
输入：{1{2{4},3{5,6}}}
输出：根节点1，1的左节点为2，2的左节点为4，右节点为空，1的右节点为3，3的左右节点分别为5，6。
今天在逛鲁攀的QQ空间，看到一个很有意思的题目，也从另一方面告诉我们了编程中数学的重要性，很多时候数学能够给好的算法和高效的速度提供灵感，例如一个非常复杂的问题，我们却可以用几步就可以实现。
在看到这个题目之后，我就在网上查了一下这个题目并看到了异或运算的神奇，因为在说到xor异或运算的时候，大部分人都不会认为xor异或运算有什么有意思的事情，但是xor异或运算真的很神奇，不如我们首先先看个游戏，这个游戏的名字叫Nim游戏。而我们要看到的就是Nim游戏的必胜法则。（即在何种情况下无论对手如何走自己都会必胜）
有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。
今天在看厕所专刊（编程珠玑）的时候看到了粗略估算，有点感悟，所以写下关于粗略估算的笔记。
粗略估算在工程角度来说是非常重要的，对于个人的能力评估也是很重要的，粗略估算不是说和仔细的数学的计算正确结果相悖，而是在某些情况下，在得到正确的结果之前，能够给我们一个很准确的方向，例如下面这道题。
题目：从N个数中取M个最大值。N是无序的，不连续的。
当然，在做上面这道题的时候，大家都可以很容易的做出来，例如快速排序，取前M个数，用二叉排序树，后序遍历M个数，堆排序，等等，不是很复杂。当然，这个题还可以变形一下，如下。
题目：从100万个数中取最大的10个数。
好吧，我想大部分的人都会犯这样一个错误，100万？这么大，那么我怎么组织空间才能性能最好，速度最快呢？其实，这个肯定是有一定问题的，100 万，不是小数目，但是我们不妨计算一下，在各个系统中占用的内存最坏是多少，我们可以大约估算一下，在16位的机器里，一个指针和一个整数大约占4个字节，32位，那么就是8字节，那么64位就是16字节。那么100万个32位的整数和指针，大约会占用8M的内存，也就是说，在现在的计算机里，就算你将100万个数全部放到内存中，也才8M，那么，最坏最坏才8M，你就可以为你的程序计算出最坏的情况，比如这个程序需要10M内存，CPUx%以及进程数n，那么最后的程序应该在这个预期之内或更好。为了追求速度，可以牺牲一点空间，可以全部读入，如果要求空间有限，那就要优化一下，只用4M或2M内存或者更少。
