内存的分配与回收（笔记）

内存的分配与回收

     -- =（内存管理）分区的分配与回收

---

1. 固定分区时的分配与回收。

     关键点，需要一张描述不用分区使用情况的分区说明表。

     分配时，只要存储管理程序根据请求查询分区说明表（或链表），从中找出一个满足要求的空闲分区，将其分配给申请者。

     回收时，操作就更简单了，不需要内存资源了，管理程序只要将对应的分区状态置为为使用即可。

2. 动态分区时的分配与回收。

     不同于固定分区方案，该方案需主要解决三个问题：

     1）分配程序（算法），从分区表寻找（最）合适的空闲分配出去。

     2）分配之后，更新分区表。

     3）回收算法，回收（释放）分区时需和相邻的空闲区进行链接合并，更新分区表。

     分配算法有三种常用算法包括最先适应法（first fit algorithm），最佳适应法（best fit algorithm）和最坏适应法（worst fit algorithm）。

     a. 最先适应法，要求分区表（表或自由链表）按起始地址递增的次序排列。该算法的最大特点是一旦找到大于或等所要求内存长度的分区则结束搜索。接着，从找到的分区划分要求的长度分配出去，并把余下部分与相邻分区合并（若相邻空闲区存在的话），更新分区表。

          1. 搜索分区表空闲区大小大于或等于申请大小alloc_size，若找到则继续2，否则停止分配失败；

          2. 找到合适空闲区A，若其大小a_size==alloc_size，直接标记分区A为“使用区”完成。

          3. 若a_size > alloc_size，切分A为A1（alloc_size），A2（a_size-alloc_size），标记A1“使用区”，A2“空闲区”。

     b. 最佳适应法，从分区表寻找最合适的空闲区分配。这里的最合适标准可以认为是空闲区的大小与要求的大小相差最小。

          1. 遍历分区表找最接近于申请大小alloc_size空闲区B，若找到则继续2，否则停止分配失败；

          2. 找到最合适空闲区B，若其大小b_size==alloc_size，直接标记分区A为“使用区”完成。

          3. 若b_size> alloc_size，切分B为B1（alloc_size），B2（b_size-alloc_size），标记B1“使用区”，B2“空闲区”。

   c. 最坏适应法，从分区表寻找最大的空闲区分配。

          1. 遍历分区表找最大空闲区W，大小为w_size，若w_size >= alloc_size则继续2，否则停止分配失败；

          2. 找到最合适空闲区W，若其大小w_size==alloc_size，直接标记分区A为“使用区”完成。

          3. 若w_size> alloc_size，切分W为W1（alloc_size），W2（w_size-alloc_size），标记W1“使用区”，W2“空闲区”。

     （详细介绍可从网络搜索参考资料）

3. 几种分配算法的比较

     a. 从搜索速度上看，最先适应算法具有最佳性能。另一个有点就是尽可能地利用了低地址空间，从而保证高地址有较大的空闲区来放置要求内存较多的进程或作业。

     b. 最佳适应法找到的空闲区是最佳的，最合适用户要求的可用空闲区。但这样做在某些情况下并不一定提高内存的利用率。倒是可能导致内存碎片更多，因为分区表可能剩下越来越多的“小碎片”不能满足后续使用。

     c. 最坏适应算法正是基于不留碎片空闲区这点出发的，它选择最大空闲区来满足申请的要求，以期分配后的剩余部分仍能后续分配使用。

最后，总之三种算法各有特长，针对不同的请求队列，效率和功能不一样。实际项目开发使用，可以适度地多者结合一起使用。

……

（完）

Buffer overrun detected!

Buffer overrun detected!

     -- 一个C++栈缓冲区溢出警告（弹窗）

---

> 问题现象

先看看，程序运行过程中弹窗报错，如下图所示：

===

有人见过这种情况吗？最近有些（迅雷）用户遇到这种情况，很诡异。奇怪的地方在与我们开发与测试这边的环境下都不曾出现过这样的错误情况（否则早已解决了☺）。只有在极个别的用户机器上才出现这样的弹窗报错情况，但程序又不崩溃只是弹窗警告，点击确定程序即继续正常工作了，诡异的是这样弹窗报错竟然还有一定的周期性，大概10分钟一次。无语了。

> 网上说法

 从网上搜索得到下面几种说法，包括：

 a，安全程序（软件）包括防火墙，杀毒软件，安全卫生，管家等，可能引起程序的不兼容导致这样的情况。

 b，系统升级打补丁，导致之前正常运行的程序出现这样的错误，只要针对XP系统sp3。

 c，驱动程序由于升级版本与之前正常运行的程序出现不兼容，导致程序报错。

 ……

 具体的网上参考链接，有：

http://topic.csdn.net/u/20080617/17/0d16e504-0af9-40d5-911e-eee9fcdfdb75.html

http://topic.csdn.net/u/20080617/10/f3b02b0a-fa29-49c4-b4fc-c21ccc

http://answers.microsoft.com/en-us/windows/forum/windows_other-gaming/microsoft-visual-c-runtime-library-buffer-overrun/bb1cb707-622d-4fc6-b46d-c2bb4dec6207

其中，微软的官网论坛有这么句描述问题的，如下：

"The problem is due to a known bug in the ATI drivers - there are several threads on it on the AMD site. The thread I read was closed by a moderator with the statement "It will be fixed soon". I'm running the 10.11 drivers on a 4870 and I have the problem too."

===

> 问题分析

经过与出现该问题的用户的多次沟通，以上（网上得来的）说法均在用户环境一一确认，我们的情况不然，所以，这些说法都可以排除掉。

后来，好不容易从一个用户那重新问题，并顺利抓取了出错程序的堆栈信息（dmp文件）。这里还有一个小小的意外故事，当时让用户将dmp文件传过来，过程中刚好公司意外断点了，结果泡影了，所以赶紧手机登录上线让用户发到qqmail……还好，这位用户比较热心，帮dmp文件发到了邮箱。

再后来，分析了dmp文件，显然有了堆栈信息问题明确好多了。弹窗报错的原因在这里，详见下面说明：

（引用自\Microsoft Visual Studio .NET 2003\Vc7\crt\src\secchk.c）

/***
*seccook.c - checks buffer overrun security cookie
*
*       Copyright (c) Microsoft Corporation.  All rights reserved.
*
*Purpose:
*       Defines compiler helper __security_check_cookie, used by the /GS
*       compile switch to detect local buffer variable overrun bugs/attacks.
*
*       When compiling /GS, the compiler injects code to detect when a local
*       array variable has been overwritten, potentially overwriting the
*       return address (on machines like x86 where the return address is on
*       the stack).  A local variable is allocated directly before the return
*       address and initialized on entering the function.  When exiting the
*       function, the compiler inserts code to verify that the local variable
*       has not been modified.  If it has, then an error reporting routine
*       is called.
*
*       NOTE: The ATLMINCRT library includes a version of this file.  If any
*       changes are made here, they should be duplicated in the ATL version.
*
*******************************************************************************/

……

但是，具体的错误根源，虽然找到了错误点（疑点），但还需程序验证确认问题解决了，不出现弹窗报错方知真相。

程序错误点其实很简单，只是隐藏在大几十万行代码里头，不好找出来，而且奇怪的是那里的代码一直也没啥改动的啊？

===


> 解决方案

该程序逻辑涉及一个Windows API 读取注册表一个键值，接口如下：

LONG WINAPI RegQueryValueEx(
  __in          HKEY hKey,
  __in          LPCTSTR lpValueName,
  LPDWORD lpReserved,
  __out         LPDWORD lpType,
  __out         LPBYTE lpData,
  __in_out      LPDWORD lpcbData
);

（该函数的具体说明参考MSDN）

注意，最后一个参数lpcbData为__in_out类型，既是输入又是输出参数。

其中错误程序，描述如下：

void function() 

{

     ...
     char buffer[MAX_PATH]
     unsigned size; // Error：这里没有初始化。
     if (ERROR_SUCCESS == RegQueryValueEx(..., buffer, size)) {
          ...
     }
     // Error：这里也再没有初始化size，此时size为上次RegQueryValueEx操作的读取字节数。

     if (ERROR_SUCCESS == RegQueryValueEx(..., buffer, size)) {
          ...
     }
     ...

} // BTW，从堆栈信息看来，运行出错的程序是在这里函数退出时，弹窗报错的！

修正程序，如下：

     char buffer[MAX_PATH]
     unsigned size = MAX_PATH;
     if (ERROR_SUCCESS == RegQueryValueEx(..., buffer, size)) {
          ...
     }
     size = MAX_PATH;
     if (ERROR_SUCCESS == RegQueryValueEx(..., buffer, size)) {
          ...
     }

结果程序运行正常了，不再报错了！


===
最后，仍然心存疑问的是，“为啥这样的程序出错不是必须的，而且是很稀罕的？”。
猜想：因为变量size未初始化，其值为未确定状态。导致程序出错的概率，很可能跟系统（C++运行时）内存栈环节有关。

（完）

两种优先搜索算法

两种优先搜索（查找）算法

     -- 深度优先 & 广度优先 （经典算法）

---

> 描述

”如果说深度优先查找遍历表现出来的是一种勇气（该算法尽可能地“离家”远些），广度优先查找遍历表现出来的则是一种谨慎。“

好吧，具体两种优先搜索算法逻辑描述，如下：

 1， DFS -- 深度优先搜索

 2， BFS -- 广度优先搜索

> 算法

 DFS(G)

 // 实现给定图的深度优先查找遍历

 // 输入: 图 G = <V, E>

 // 输出: 图G的顶点, 按照被DFS遍历第一次访问到的先后次序, 用连续的整数标记.

 V = { 0 } // 将V包含顶点标记为0, 表示均未访问状态.

 count = 0;

 for each vertex v in V do

if v is marked with 0

dfs(v)

dfs(v)

 // 递归访问所有和v相连接的未访问的顶点, 然后按照全局变量 count的值

 // 根据遇到它们的先后顺序, 给它们赋上相应的数字

 count +=1;

 mark v with count

 for each vertex w in V adjacent to v do

 if w is marked with 0

  dfs (w);

 BFS(G)

 // 实现给定图的广度优先查找遍历

 // 输入: 图 G = <V, E>

 // 输出: 图G的顶点, 按照被BFS遍历第一次访问到的先后次序, 用连续的整数标记.

 V = { 0 } // 将V包含顶点标记为0, 表示均未访问状态.

 count = 0;

 for each vertex v in V do

if v is marked with 0

bfs(v)

bfs(v)

// 访问所有和v相连接的未访问的顶点, 然后按照全局变量 count的值

// 根据访问它们的先后顺序, 给它们赋上相应的数字

count +=1;

mark v with count and initialize a queue with v

while the queue is not empty do

for each vertex w in V adjacent to the front vertex v do

if w is marked with 0

 cout += 1;

 mark w with count

 add w to the queue

 remove the front vertex from the queue

> 对比

两种优先搜索算法，多方面因素对比表如下：

项目	DFS	BFS
数据结构	栈(stack)	队列(queue)
顶点顺序的种类	两种顺序	一种顺序
边的类型(无向图)	树向边和回边	树向边和交叉边
应用	连通性/无环行/关节点	连通性/无环性/最少边路径
邻接矩阵的效率	O (|V|^2)	O (|V|^2)
邻接链表的效率	O (|V| + |E|)	O (|V| + |E|)

> 参考

A.

  文章描述包含有引用自《算法设计与分析基础（第2版）》涉及的章节内容。

B.

  二叉树的两种优先搜索（遍历），示例C++程序代码参见 Github。

void bfs_tree(treeT* tree);

void dfs_tree(treeT* tree);

还有，下面两道小算法题，可以借助深度优先搜索算法得到快速的求解。

a 简单栈的实现，前序遍历二叉树（深度优先搜索）。

b 关于二叉树，查找存在一条从根节点至叶子节点的路径的数值总和为Value。

     （结合深度优先搜索二叉树）

单链表删除节点的技巧

单链表删除节点的技巧

     -- 注：删除节点非尾节点！
 

---

在此分享一个小小技巧，在单向链表中删除节点时不必知道其前面节点（若存在前面节点的话），亦可高效地完成删除节点。

===

从一篇别人的博文说起吧，引用自这里，内容很少，仅此如下：

标题：学习数据结构的感想

在链表中删除动作比较多的时候，用双联表比用单链表效率要高，双链表不用从头开始遍历去删除，而是可以直接删除。

用单链表删除的时候，每次知道需要删除元素的前一个指针就好了。不过这个好像很难知道。

我是在无意之间，看到那位朋友的上面问题，先是无意间网上搜到他转载了我的一篇博文《STL稳定排序源码分析》，好奇之下到了他的csdn博客的。

所以我就一时兴致勃勃回复了其问题，与之讨论，内容如下：

===

单向链表删除节点时候，可做到不需要知道（若有的话）上一个节点同样完成删除操作。你可以这么做，描述如下：
原来的链表 ... A -> B[b_ptr] -> C[c_ptr] -> D[d_ptr] ...

现在要删除节点 B，其对于指针为b_ptr（注：删除节点非尾节点，重要）。

首先你可以使用B得到C，D指针，c_ptr和d_ptr，然后你可以用C去覆盖掉B，即*b_ptr = *c_ptr，那么这时你可以删除C即可达到你要的结果即删除节点B。具体操作：
*b_ptr = *c_ptr;
b_ptr->next = d_ptr;
delete c_ptr;

结果的链表 ... A -> C[b_ptr] -> D[d_ptr] ...

按照以上的操作，这样就不需要从头去遍历链表定位上一个节点A了，简单有效吧☺。

===

但是，删除节点不应该为尾节点（链表的最后一个节点），因为B作为尾节点，虽然你可以删除节点B，但无法给节点A的next赋值NULL。若删除的节点为尾节点，那就得老老实实从头遍历链表了，将其前面节点A的next赋NULL。

===

当然你说的“用双（向）链表比用单链表效率要高”，是对的。确切说应该叫实用性高吧，但是其实现的逻辑要复杂不少，可参见STL链表的实现源码。像C++ STL里面的链表（包括单向双向）底层的实现都是以双向链表形式的。可以参考sgi stl源码，std::list，std::slist。

（完）

一种特殊的排序算法 II

一种特殊的排序算法 II

  -- 计数排序(Counting sort)

---

后续想找时间再写一篇《一种特殊的排序算法 II》，关于计数排序☺。（引自 《一种特殊的排序算法 I》）

所以，继上篇文章《一种特殊的排序算法 I》，在此就（继续）描述，总结另一种特殊的排序算法，计数排序。算法的步骤如下：

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

引用自维基内容，完整介绍可以参见计数排序（维基）。

（后面，开始分享我的内容）

关于计数排序（算法），可以划分两种具体的计数法，如下：

 * 比较计数法

 * 分布计数法

===

> 比较计数法

算法 ComparisonCountingSort(A[0 ... n-1])

          // 用比较计数法对数组排序

          // 输入:可排序数组 A[0 ... n-1]

          // 输出:将A中元素按照升序排列的数组 S[0 ... n-1]

          for i : 0 to n-1 do 

               Count[i] = 0;

          for i : 0 to n-2 do

               for j : i+1 to n-1 do

                    if A[i] < A[j]

                         Count[j] += 1;

                    else

                         Count[i] += 1;

          for i : 0 to n-1 do

               S[Count[i]] = A[i];

          return S;

该算法的时间效率如何？答案为O(n^2)。因为该书法执行的键值比较次数和选择排序一样多，并且还占用了线性数量的额外空间，我们几乎不能推荐它来实际的应用。但是计数思想在一种情况下还是卓有成效的，在这种情况下，待排序的元素的值都来自于一个已知的小集合，这就是下面要描述的另一种计数排序算法，分布计算法。

===

> 分布计数法

算法 DistributionCountingSort(A[0 ... n-1, l, u])

          // 用分布计数法对数组排序,对来自于有限范围整数的一个数组进行排序

          // 输入:可排序数组 A[0 ... n-1],数组中的整数位于l和u之间( l <= u)

          // 输出:将A中元素按照升序排列的数组 S[0 ... n-1]

          for i : 0 to u-l do 

               D[i] = 0;                       // 初始化频率数组

          for i : 0 to n-1 do 

               D[A[i] - l] = D[A[i] - l] + 1;  // 计算频率值

          for i : 1 to u-l do 

               D[i] = D[i-1] + D[i];           // 重用于分布值

          for i : n-1 downto 0 do 

               j = A[i] - l;

               S[D[j] - 1] = A[i];             // D[j] - 1]为对应的数组下标

               D[j] -= 1;

          return S;

注：频率值，表示元素出现的次数；分布值表示在最后有序数组中，元素最后一次出现的位置。

假设数组值的范围是固定的，这显然是一个线性效率的算法，因为它仅仅对输入数组A从头到尾连续处理两遍，其时间复杂度 O(n)。然而，要重点记忆的是，除了空间换时间之外，分布计数排序这种高效率是因为利用了输入列表独特的自然属性。

===

附：

文章内容乃学习心得（笔记），亦包括引用自《算法设计与分析基础（第2版）》内容（第七章时空权衡，7.1计数排序）。

以上描述的算法，以C\C++完成了简单的实现，示例代码参见 github。

(完）

一只兔子的深情故事

转：那些你爱过的人，总会在平行时空爱着你.

  -- 一只兔子的深情故事

前几天在同事的日志上，看到一篇转载文章，故事以一只（雌性）小白兔为载体讲述一段不顺利的爱情故事，令人有种触目伤怀，为之惋惜的感情流露，颇为感触。或许你已经看过了该故事，那不免再读一遍吧。好吧，开始转载故事(from here)，如下 ……

那些你爱过的人，总会在平行时空爱着你。小兔子故事的另一个版本，有些悲伤……小象版本比较大团圆，可现实总是这么心酸吗？

1.

小白兔有一家糖果铺，小老虎有一个冰淇淋机。兔妈妈告诉小白兔，如果你喜欢一个人呐，就给一颗糖他。小白兔喜欢上了小老虎，那么那么喜欢，忍不住就把整个店子送给了他。回家后兔妈妈问她，那小老虎喜欢你吗。小白兔直点头，妈妈说，那他为什么不给你吃个冰淇淋呢。

2.

小白兔说，他是要给我来着，我说我不爱吃。兔妈妈说，那你真的不爱吃吗，有七种口味呢，巧克力味道的里面还有你最爱吃的杏仁啊。小白兔用脚划拉着地板，喃喃的说，其实我也没吃过，只是就想着把糖给他了。

3.

小老虎有了糖果店，小白兔说不如我帮你把冰淇淋机推到公园去卖吧。夏天可真热啊，冰淇淋每天都卖得光光的，大家都夸小白兔好聪明。小白兔呢，还是一口也舍不得吃。她就想等小老虎亲手送她一个，小白兔自己也没发现，她最爱的口味已经换成了香草，想要的也不再只是冰淇淋了。

4.

时间一天天过去了，小白兔还是没有吃到冰淇淋。倒是隔壁摊子卖饼干的小熊，给了她一盒小兔子造型的曲奇。小白兔留下糖果店和冰淇淋机给了小老虎，跟小熊去了更远的小公园卖饼干。兔妈妈问她，你不是不喜欢吃饼干吗，怎么又收下了呢。小兔子揉着红红的眼睛说，我就是饿了。

5.

后来小兔子听说，小老虎把冰淇淋机送给了小企鹅，和她一起住在了糖果店里。小熊把这些告诉小兔子的时候，她耷拉着耳朵呆了很久。小熊开玩笑的问她，你是不是后悔没有吃个冰淇淋再走呀。小白兔愣愣的转过脸说，就是有点难受，没能留些糖给你。

6.

小兔子卖力的帮着小熊卖饼干，没多久就又攒了一笔积蓄，买了新的糖果铺。这次兔妈妈千叮咛万嘱咐，她说宝宝啊，这糖要慢慢的给，不然后来就不甜了。小兔子 嘴上连连答应，心里却想着小熊收到糖果店该多开心啊。她只知道小熊又加班去了，不知道他小鸭子形状的饼干马上就要烤好了。

7.

小兔子回家看到了偷偷藏起来的小鸭子饼干，什么也没有多问，只是跑回家跟妈妈大哭了一场。她呜咽着和兔妈妈说，小熊最喜欢吃糖了，我终于可以给他糖果屋了，他为什么要离开我呢。兔妈妈笑了，她摸摸小兔子的头说，当他不爱你了，你的糖就不甜了。

8.

小兔子还是想不通，只好带着糖果店搬去了更远的地方。小鸭子可不是什么善茬儿，她不知从哪里打听到了糖果店的事。一天饭后，她揶揄的告诉小熊，哎呀你可不知道吧，你心里最单纯的小白兔，背着你用卖饼干的钱给自己买了好东西呢。不久之后，小兔子就收到了小熊的来信。

9.

信里只有短短几句话，大致是说小兔子走后饼干铺子生意一直不好，钱怎么说也是卖饼干挣来的，希望小兔子能把糖果店还给他。小兔子看完信后眼睛哭成了桃子， 她想起了妈妈的话，把店给了小熊。兔妈妈说小兔子是韭菜馅的脑子勾过芡的心啊，她说妈妈，其实糖还是甜的，只是人生太苦了。

10.

后来小白兔又爱过几个人，都无疾而终了。这缺心眼的小兔子啊，喜欢上一个人，就会使劲对他好，恨不得掏心掏肺给他看。她以为只有这样，才能让爱情活得更久更久一些。可惜那时候的小兔子还不明白，其实任何东西啊只要够深，都是一把刀。

11.

有一天小兔子出门，发现小熊醉倒在她门口。他哭着碎碎念着，说他过的不开心，说糖果店已经被吃完了，小鸭子嫌他没本事拍拍屁股就走了。 他一把抱住小兔子说，如果说着世界上我还有什么值得得回忆的，大概也只有你了。 小兔子被勒的喘不过气来，他心里想着，也许爱上一个旧人，就不会再有新的问题了吧。

12.

很久很久以后，小兔子和别人讲起这段故事，总是感慨万分的说，那些值得回忆的事啊，就该永远放在回忆里。

13.

不知道你又没有玩过一种游戏机，投硬币的那种。有好多小爪子推啊推，硬币们互相推搡着，摇摇欲坠却又固若金汤。拟投入的越多就越难收手，机器里的硬币落得越厚重就越不会有收获，可越是不掉币你就越觉得大奖就要来了。这逻辑很有趣，它只在你输的时候成立。可小兔子就是这么觉得的，她在万丈悬崖边，以为跳下去是学会飞翔的捷径。她默默地想，大奖终于要来了。她被大把硬币即将掉落的景象迷红了眼，以至于忘记了，自己没有翅膀。

14.

既然是童话，总得有点好的不是。小兔子回到了小熊身边，日子没有想象中的糟糕。一起吃饭，逛逛公园，小熊每天都采一朵最漂亮的花回来送给她，小兔子会做一手好菜，小熊总是抢着洗完。小熊以为一切都好了，他甚至点点失望，都说感情是刻骨铭心的，可小兔子似乎没留下任何伤痕。多可笑啊，那些拿刀子去花豆腐的人，永远都不知道疼。

15.

直到有一天晚上，小熊从厨房出来，随手递了一块饼干给小兔子。小兔子摇摇头，说我好久不吃饼干了。然后她抬起头看着小熊，淡淡的说，你给过别人的东西，就不要再给我了。小熊一瞬间明白，这些伤口还是血淋淋的。那年小兔子扑在妈妈怀里哭得那个下午，他就已经弄丢他的小兔子了。一起弄丢的，还有原本可以幸福的可能。

16.

可小熊舍不得小兔子，小兔子自己也没发现自己当初的喜欢，已经只剩下不甘心。日子还在继续，小兔子除了还是不吃饼干，什么都是百依百顺的。在别人眼里，他们俨然成为了恩爱的一对儿。直到有一天，他打开一只旧箱子，里面装满了小熊每天送她的花。花都枯萎了，小兔子想起这些日子，她每天接过小熊的花都是敷衍的笑笑，转身便扔进这个破箱子里。她一下子发现，原来不爱了，是早就不爱了。

17.

和小熊分手后，小兔子断断续续的又开过几个糖果店，卖的卖送的送，也所剩无几了。可她还是学不会开口，说她饿，说她想要吃个带杏仁儿的冰淇淋。她把给糖果当成了一种惯性和礼节，看起来和从前没什么差别。她还给它们报了亮晶晶的糖纸，但小兔子心里明白，它们早就没有味道了。

18.

后来小兔子结婚了，是和其貌不扬的小猪，再后来还有了两个孩子。小猪是隔壁村子来旅行的，据他后来说，是来小兔子店里买糖的时候，一眼就喜欢上了这个小机灵。小猪一连来了好几次，每次都是买完糖，付了钱，又悄悄把糖留下。兔妈妈说，这样的孩子品行好，可以嫁了。小猪果然也没让兔妈妈失望，结婚后包揽了所有家务，他家都夸小兔子好福气。小兔子也总是笑眯眯的，她常常摸着两个孩子的头说，如果你们喜欢上一个人啊，就找他要一颗糖。

19.

故事就要结束了。没人知道，当年小猪留下的糖，是小兔子准备吃下的毒药。小兔子明明知道是有毒的，却也懒得阻拦就卖给了小猪。她想，这些贪图甜腻的人啊，总该受到些惩罚。当她刚准备重新拿出毒药服下的时候，发现了小猪买走的糖，居然安安静静的放在罐子中。

20.

第天小猪又来了，第三天也是。小兔子还是给他有毒的糖，她甚至不明白自己为什么要这样残忍，他总想着只要小猪收下一次，一切就都结束了。可小猪每次都巧妙的放回了罐子里，然后趁小兔子还来不及发现就走了。小兔子在和自己较劲中，似乎又看到了春天。他幸免的不只是那些有毒的糖果，而是小兔子这些年对这个世界巨大的失望。终于他们相爱了，后面的故事也水到渠成了。

21.

可她忘记了兔妈妈说的，你拿谎言去考验爱情，就永远遇不到真心的爱人。

22.

有一次小猪喝多了，朋友们起哄问到他当时怎么想到不收下糖果。小猪被灌了太多酒，回答的稀里糊涂，颠三倒四。但当那些字组合在一起，传到小兔子耳朵里时。在场的谁也没听懂，只有她在一瞬间放声大哭。

23.

小猪说，那天啊，那天我只是路过来着，小熊硬塞的钱，小老虎说如果我能把糖放回去，冰淇淋机就是我的了。

24.

嗯，故事说完了。

别哭，这世界是守恒的。你付出的每一颗糖都去了该去的地方。

那些你爱过的人，总会在平行时空，爱着你。

（完）

一种特殊的排序算法 I

一种特殊的排序算法 I

     -- 位排序 OR 桶排序

---

绝大部分经典的排序算法，都是以元素间的比较为基础，如冒泡，选择，插入，快速，归并，堆排序等，虽然这些排序算法的时间和空间复杂度存在不同，但其算法平均时间复杂度均不超过O(n logn) （基数排序也比较特殊可做到O(k*n)），详细对比情况可以参见维基排序算法。

===

而下面内容描述的排序算法比较特殊，并非以元素间比较为基础的，其算法时间复杂度达到了O(n)。先来看看一道简单的示例题目吧（引用自：Google groups TopLanguage）。

   
特殊排序算法题目，如下：
     姓名集合names，名次集合ranks，按照名次顺序输出她们的名字，要求O(N)的时间复杂度。

解法如下： 
     解法一，不改变原来集合顺序，O(N)时间， O(N)空间。
     描述： 数组下标相当于姓名索引，新空间以名次顺序依次记录着姓名索引。

     解法二，在位重新排序，改变原来集合顺序，O(N)时间， O(1)空间。
     描述：每一次swap确定一元素的位置，最多总共N次swap能全部定位。

具体的程序设计（C/C++）代码在这里。

===

有一种特殊的排序算法，在《编程珠玑I II》有讲述到的位排序(bitsort)，也称桶排序。

其实，上面的排序题目正是位排序的一种变种的应用，不知你是否已经发现了否？

位排序算法的整体思想，可以描述如下：
     1. 每字节有8bit（位），那么它就可标记8个连续的数，分别对应每bit位，若数值存在则对应bit位置为1。
     2. 把N个数分为1+N/8组(相当于有这么多个桶)，每组标记连续的8个数。

     3. 申请（1+N/8）字节数组均初始化为0，遍历要排序的集合，存在的元素在对应的bit位标记1。

     标记规则： array[i/8] = (array[i/8] | (1<<(i%8)))

注：算法描述的字节亦可替换为整型类型，对应的比特位数字变为32。

===

关于位排序，同样可以瞄瞄其他网友描述，这里。

后续想找时间再写一篇《一种特殊的排序算法 II》（20120629更新链接），关于计数排序☺。

（完）