问题XYZ的10种语言解决方案（一）之C语言篇

      写这篇，或者这个系列的无聊博客文章完全是由于昨晚没事瞎想想到的，本来是在思考《Learn you a Hashkell for Great Good》中快速排序的Haskell实现代码，突然想到用其它语言来写写，然后做做对比其实很有意思，于是决定今天起来就做这件事情，由于是在想快速排序时想到的，因此也就将快速排序的实现作为第一篇吧。
      在这个系列的博客文章里（当然也许就这一篇，我不保证，哪天无聊了也许会写第二篇，第三篇......），我会尝试用我接触过的编程语言来解决一系列乱七八糟的问题，并尝试分析比较不同语言的解决方案，主要从表达力和抽象封装度两个方面吧，暂时也就想到这两个方面。当然，我得承认，这10种语言我常用的不过两三种而已，甚至在写这篇博客之前我都没用过D和Lua，但是我对它们都很感兴趣，所以也放在这里，就当练习；而我虽然用过或者知道，但是目前不是很感兴趣的语言，例如汇编语言（实在太低级，就是一堆PUSH、POP、CALL INT了，里面转一圈的话我都不知道怎么写“Hello，World”了）、Basic（没什么兴趣）、C++（杀了我吧，光是虚析构函数、纯虚函数什么的东东就让人晕菜了，更别提编译器私底下自以为是搞的一大坨乱七八糟的东西）等。
      好吧，废话少说，就正式开始吧。在这篇博客里，我们将使用C、Clojure、D、Factor、JavaScript、Groovy、Haskell、Java、Lua、Python这10种编程语言来实现快速排序。
      问题描述：呃，如果你不知道快速排序的话那么还是自己去找本教科书或去google一下吧，我在这里就不赘述了。
      按照字母排序，就先从C开始吧。
    

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "qsort.h"

void q_sort(int* values)
{
  if(values.length <= 1)
    return;
  size_t length = values.length;
  size_t wl = sizeof(int);
  int* p = malloc(wl * length);
  if(p == NULL) exit(1);
  int* p1 = malloc(wl * length);
  if(p1 == NULL) exit(1);
  int lp = 0, lp1 = 0, i = 1,value = values[0];

  int* cp = p;
  int* cp1 = p1;
  for(; i < length; i++)
  {
    if(values[i] <= value)
    {
      (*p) = values[i];
      p++;
      lp++;
    }
    else
    {
      (*p1) = values[i];
      p1++;
      lp1++;
    }
  }
  values[lp] = value;
  q_sort(cp,lp);
  q_sort(cp1,lp1);
  i = lp;
  while(i > 0) {
    values[i - 1] = cp[i - 1];
    i--;
  }
  i = 1;
  while(lp1 > 0) {
    values[lp + i] = cp1[i - 1];
    lp1--;
    i++;
  }
}

很好，我们的C语言版快速排序完成了，编译吧，blah，blah... ...
什么，出错了？！
In file included from qsort.c:3:
qsort.h:3: error: conflicting types for ‘qsort’
/usr/include/stdlib.h:175: error: previous declaration of ‘qsort’ was here
qsort.c:6: error: conflicting types for ‘qsort’
/usr/include/stdlib.h:175: error: previous declaration of ‘qsort’ was here
qsort.c: In function ‘qsort’:
qsort.c:7: error: request for member ‘length’ in something not a structure or union
... ...
哦，原来已经有qsort的实现了，那就改成q_sort吧，但是，length的调用不合法？哦，我忘记了这是C语言，要自己实现length的 ，好吧，改写一下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "qsort.h"

void q_sort(int* values, size_t length)
{
  if(length <= 1)
    return;
  size_t wl = sizeof(int);
  int* p = malloc(wl * length);
  if(p == NULL) exit(1);
  int* p1 = malloc(wl * length);
  if(p1 == NULL) exit(1);
  int lp = 0, lp1 = 0, i = 1,value = values[0];

  int* cp = p;
  int* cp1 = p1;
  for(; i < length; i++)
  {
    if(values[i] <= value)
    {
      (*p) = values[i];
      p++;
      lp++;
    }
    else
    {
      (*p1) = values[i];
      p1++;
      lp1++;
    }
  }
  values[lp] = value;
  q_sort(cp,lp);
  q_sort(cp1,lp1);
  i = lp;
  while(i > 0) {
    values[i - 1] = cp[i - 1];
    i--;
  }
  i = 1;
  while(lp1 > 0) {
    values[lp + i] = cp1[i - 1];
    lp1--;
    i++;
  }
  free(cp);
  cp = NULL;
  free(cp1);
  cp1 = NULL;
}

数一数，总共45行代码，用了我n个小时（n>1，从中我认识到自己是个多么蹩脚的C程序员，虽然和我很久没写C代码也有关系），其中真正和快速排序相关的只有7行左右，其它的全是用来分配内存、移动指针、释放内存之类的操作。经过这个练习，我深深地认识到，学校里用C来教数据结构是件多么愚蠢的事情，我不过是要做个排序，却要写那么多与排序没有直接关系的一大坨代码！用Joel的话来说，这是一种严重的抽象泄漏啊（abstraction leaky），我得不停的在两个不同的抽象层次上进行context switch才能得到我想要的结果。等等，这还只是对整数的排序，浮点数呢？字符串呢？xxyy呢？好吧，撸起袖子继续吧，声明一个能够处理各种能进行排序比较的数据类型的函数的signature吧：
void q_sort(void* values, size_t length, size_t unit, int (*compare)(void* v1, void* v2))
看懂没有？为什么这么声明？哈，C自带的类库里的qsort的声明和这个也差不多，一个一个看看吧：第一个参数，要排序的数组，必不可少，C里面类似泛型的效果只能通过void*来达到了，这样我们可以处理任意类型的数组，哪怕是函数指针呢，呵呵！第二个是要排序的数组的长度，没办法，谁知道这个数组会在哪里结束？只能别人告诉我们了，第三个参数是数据类型的长度，不多解释了，这和C的数据类型的长度在各个平台上都可能不一致有关系，最后一个参数,呃，看着眼花是吧，其实不过是用来对给定数据类型的两个值进行比较的函数指针而已，好吧，我们来实现它吧... ...

void q_sort_g(void* pValue, size_t length, size_t wl, compare cmp)
    {
      if(length <= 1)
      {
        return;
      }
      void* p = malloc(wl * length);
      if(p == NULL) exit(1);
      void* p1 = malloc(wl * length);
      if(p1 == NULL) exit(1);
      int lp = 0, lp1 = 0;
      int i = 1;
      BYTE* b = (BYTE*)pValue;
      BYTE* pivot = b;
      b += wl;
      BYTE* b1 = (BYTE*)p;
      BYTE* b2 = (BYTE*)p1;
      BYTE* b3 = NULL;
      for(; i < length; i++)
      {
        int result = cmp(b,pivot);
        if(result <= 0)
        {
            b3 = (BYTE*)b1;
            b1 += wl;
            lp++;
        }
        else
        {
            b3 = (BYTE*)b2;
            b2 += wl;
            lp1++;
        }
        memcpy(b3,b,wl);
        b += wl;
      }-
      q_sort_g(p,lp,wl,cmp);
      q_sort_g(p1,lp1,wl,cmp);
      memcpy(pValue + lp * wl, pValue, wl);
      memcpy(pValue,p,lp * wl);
      memcpy(pValue + lp * wl + wl,p1,lp1 * wl);
      free(p);
      free(p1);
      p = NULL;
      p1 = NULL;
    }
    
    static int intCmp(void* v1, void* v2)
    {
        int* pV1 = (int*)v1;
        int* pV2 = (int*)v2;
        return (*pV1) - (*pV2);
    }

经过一番和指针的苦战，终于完成了这个泛型版本，从实现的过程来看，可以得出以下几个结论：
1 用C语言的一个最大问题就是需要自己分配和管理内存，实现上面这个快速排序，大概我只有不到10％的时间是在编写实现快速排序的代码，剩下的时间都在和内存分配、指针作斗争，所以Joel（又提到他了，最近在翻他写的东东）曾经写文章说过OO并不能大幅提高程序员的效率，而是自动内存管理，上面的例子虽然简单，但是我想也还是能够证明他的这个观点；
2 C语言是一门通用语言，但是不是“通吃”语言:)，让人烦恼的内存和指针管理其实也正是C语言的强大与灵活之处，如果要解决的问题是和机器密切相关，那么用C来解决是相当舒服的事情，拿到一个指针，想怎么捏就怎么捏，哪怕是传给你一个int型指针，我也可以把它当成char型或者其它任何我想要的类型的指针来玩，呵呵。
C语言的版本就告一段落吧，下面我们该看看Clojure了。