算法面试题
利用0,1真的是能巧妙地解决好多问题啊，今天看到了下面这个题：
有1000桶酒，其中1桶有毒。而一旦吃了，毒性会在1周后发作。现在我们用小老鼠做实验，要在1周后找出那桶毒酒，最少需要多少老鼠？ 答案是10只！！！将10只老鼠按顺序排好，每桶酒按照编号转换为二进制，给相应位置上是1的老鼠喝，最后按死掉的老鼠是哪几只，再转成十进制，就是第几桶酒。我最开始看到题目，陷入了固有思维，默认只有一只老鼠会死，觉得哪只老鼠死了，它喝的酒就有毒，看了答案，觉得太妙了，所有的老鼠都含有有效信息！
基数排序和快排
关于基数排序
先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小……排到最后，就是一组有序的元素了。不过，他在以某位数进行排序的时候，是采用“桶”来排序的，基本原理就是把具有相同个（十、百等）位数的数放进同一个桶里。
若以最高位来排序的话，是可以减少数据之间比较的次数。但以最高位来排序有个致命的缺点。在每个小部分的排序中，我们也是需要10个桶来将他们进行排序，最后导致的结果就是，每个不同值的元素都会占据一个“桶”，如果你有1000个元素，并且1000个元素都是不同值的话，那么从最高位排序到最低位，需要1000个桶。这样子的话，空间花费不仅大，而且看起来有点背离基数排序最初的思想了。所以，我们一般采用从最低位到最高位的顺序。
复杂度比较
基数排序的时间复杂度为O(n)，快排的时间复杂度为O(nlogn)，对于大的数组，在操作次数上，基数排序比快排要有优势，但随着排序数据的增加，快速排序的速度却比基数排序快。这其中的原因涉及到每项排序平均cache缺失率。