本文译自Doug McIlroy主页上的文章The tiniest C sort function. 大名鼎鼎的Doug已从Bell Lab退休多年，现在是Dartmouth学院的Adjunct Professor. 前段时间看Programming Pearls时我才知道老先生的大名，大家经常用的“管道”、sort、diff、tr等工具都是先生的发明，我真是有眼不识泰山，现在在看The Art of UNIX Programming又能看到老先生的名字了，可谓功德无量啊！

--------------------------------------------------------------------

我想知道我能用C写出多短的排序代码，经过多次的努力和别人的协助下，我最终把它浓缩成67字节的函数s(a,b)。这个函数对一组整数就地排序，参数a和b分别指向数组的开始和结尾元素。你能打破我的记录吗？

本来我的直觉认为越短的代码将会越模糊不清，可令人惊讶的是，第11步得到的最终代码与第1步的代码居然具有相当的可读性，而且我敢断言前者更可读性：因为第1步的代码有个先天的优势，就是大家都之前都学习过它，要不然它的逻辑其实也是挺复杂的。在通向第11步的过程中，第5步是稍微有点困难的，需要动动脑筋。

s(int*a,int*b){for(int*c=b,t;c>a;)
if(t=*c--,*c>t)c[1]=*c,*c=t,c=b;}

HTML警告：为了保持原始的C代码，应该使用原样的>号，而不是HTML中的转义字符。Internet Explorer,Safari和Firefox都允许这样做。

选择排序(Selection Sort)

1.先从一个香草(vanilla)选择排序开始，它的前置条件为a!=NULL&&n>=0。这里唯一的技巧是惯例：用逗号代替分号，从而省掉大括号。除了换行符，长度是93字节。
Bill McKeeman(他相信Steve Johnson)指出它的毛病：当a指向地址0和n==0时，函数就会失败。在通常的实现当中，这其实不是个问题，一个指向0的指针会被解析为NULL。

void sort(int*a,int n){int*b,*c,t;for(b=a+n;--b>a;)
for(c=b;--c>=a;)if(*c>*b)t=*b,*b=*c,*c=t;}

2.抛开C++/C99标准，在循环初始化中声明变量；并用n代替t。(87字节)

void sort(int*a,int n){for(int*b=a+n,*c;--b>a;)
for(c=b;c-->a;)if(*c>*b)n=*b,*b=*c,*c=n;}

3.将函数签名改为sort(first,last+1)，省去b的计算。(83字节)

void sort(int*a,int*b){for(int*c,t;--b>a;)
for(c=b;c-->a;)if(*c>*b)t=*b,*b=*c,*c=t;}

4.Peter McIlroy把c和t的声明移到第二个for里面。(82字节)

void sort(int*a,int*b){while(--b>a)
for(int*c=b,t;c-->a;)if(*c>*b)t=*b,*b=*c,*c=t;}

5.疯狂的东西现在来了：将两个循环测试放到一个for里面。(81字节)
这会有一点无用功。首先，内循环测试失败，然后做外循环测试，并进入第一次外循环；接下来的每次内循环测试条件失败将导致下一次的外循环；直到内外条件都不满足时，程序结束。
缺点：对于b==a的空数组，外循环测试中的c等于a-1，但C标准并没有保证不在[a,b]的指针能正确地与a作比较，尽管这基本上都是能正常工作的。

void sort(int*a,int*b){for(int*c=a,t;c-->a
||(c=--b)>a;)if(*c>*b)t=*b,*b=*c,*c=t;}

6.Peter抽取公共子表达式*b，将赋值嵌入到比较当中。(80字节)

void sort(int*a,int*b){for(int*c=a,t;c-->a
||(c=--b)>a;)if(*c>(t=*b))*b=*c,*c=t;}

7.去掉一个循环。扫描整个数组，当交换发生时，把正在下降的下标又打回到顶部。(79字节)
这把O(N^2)的操作变到O(N^3)。但速度不是我们的目标，而且O(N^2)本来就好不了哪里。

void sort(int*a,int*b){for(int*c=b,t;--c>a;)
if(t=c[-1],t>*c)c[-1]=*c,*c=t,c=b;}

8.缩短名字。(76字节)

void s(int*a,int*b){for(int*c=b,t;--c>a;)
if(t=c[-1],t>*c)c[-1]=*c,*c=t,c=b;}

9.把参数first,last+1转换成first,last，从而去掉自减操作符，并使用[1]代替两个[-1]。(72字节)

void s(int*a,int*b){for(int*c=b,t;c>a;)
if(t=*c--,*c>t)c[1]=*c,*c=t,c=b;}

10.使用旧语法(pre-void)。(68字节)

s(a,b)int*a,*b;{for(int*c=b,t;c>a;)
if(t=*c--,*c>t)c[1]=*c,*c=t,c=b;}

11.有惊无险。跟第10步差不多，但用的是现代的参数声明。(67字节)
事实上，我是先写11的，但误以为必须使用旧语法从而得到一个不返回的int函数。其实代码是合法的，标准只是禁止使用丢失的结果罢了。

s(int*a,int*b){for(int*c=b,t;c>a;)
if(t=*c--,*c>t)c[1]=*c,*c=t,c=b;}

递归

12.在这个(终究也没什么好处的)方法中，第一个递归对第一个元素之后的元素排序；然后，如果第一个元素不是最小的，就把它跟第二个(刚排完序数组中最小的)元素交换，再对第一个元素后的数组排序。函数签名是s(first,last+1)。
(70字节)
函数体里有两次递归调用，貌似是以O(2^N)的复杂度来运行的，但更细心的分析可以证明它是O(N^3)的。有趣的是，它跟之前的程序是等价的。
缺点：即使数组是空的也有一个元素被操作。

s(int*a,int*b){int t=*a;if(b>++a)
if(s(a,b),t>*a)a[-1]=*a,*a=t,s(a,b);}

Brian Kernighan和Rob Pike在Practice of Programming的第3章讨论了单词级别的马尔可夫文本生成问题，并用C、C++、Java、Awk和Perl实现该算法。Jon Bentley在Programming Pearls的第15章用排序的后缀数组和二分搜索给出了一个更优雅快速的实现，他说如果用散列代替排序和二分搜索可以使速度提高一倍。

我用Python试着写了个玩玩，挺有趣的。我用了collections模块中的deque来储存前缀短语，因此可以很容易实现任意阶的马尔可夫近似。但我感觉速度一般，估计是我的代码太差了。

P.S. 昨天发现原来计算所有个中文分词工具叫ICTCLAS，用了一下开源版的，感觉一般，不像它声称的好。不过弄来玩玩还可以，今天搞了篇张五常伯伯的文章分了一下词，然后用sed处理一下，使得词与词之间用空格隔开，于是就可以用Markov算法生成中文文本了，我的Python程序一点都不用改。ICTCLAS有个不好的地方就是不处理UTF8编码，所以中间要用iconv转换一下文本。(Oct.20)

To indent Python in VIM, append the following lines to file named /usr/share/vim/vim72/indent/python.vim:

setlocal tabstop=4

setlocal softtabstop=4

setlocal shiftwidth=4

setlocal textwidth=80

setlocal smarttab

setlocal expandtab

setlocal smartindent