一个C语言实现不含递归的高效快速排序算法

近来编写一个对性能要求很高的程序，要用到排序功能。要排序的数据类型有很多种，有整数、浮点数、各种结构（根据某个属性进行比较）等。如果调用libc的qsort()函数，调用比较函数的开销将会很大。因此就产生自己写一个排序函数的想法。由于数据类型的多样性，因此算法要有一定通用性。但我又不想用调用比较函数的开销，因此只能用宏来实现了。由于快速排序是目前最快的通用排序算法，因此当前选用快速排序算法。我选用bentley-mcilroy的三路划分快速排序法，原型如下：

void quicksort(item a[], int l, int r)
{ 
  int i = l-1, j = r, p = l-1, q = r; item v = a[r];
  if (r <= l) return;
  for (;;) {
    while (a[++i] < v) ;
    while (v < a[--j]) if (j == l) break;
    if (i >= j) break;
    exch(a[i], a[j]);
    if (a[i] == v) { p++; exch(a[p], a[i]); }
    if (v == a[j]) { q--; exch(a[j], a[q]); }
  }
  exch(a[i], a[r]); j = i-1; i = i+1;
  for (k = l; k < p; k++, j--) exch(a[k], a[j]);
  for (k = r-1; k > q; k--, i++) exch(a[i], a[k]);
  quicksort(a, l, j);
  quicksort(a, i, r);
}

但快速排序是采用分治法进行排序，因此有函数的递归调用。这就给用宏实现算法带来困难。没有办法，只好用堆栈来模拟了。但堆栈有可能溢出，在溢出的时候还是要用libc的qsort()来对未排序的部分数据进行排序，但一但情况下是用不到的。最后完成的排序算法如下（其中在数据量较少时转而用插入排序是我增加的内容）：

#define libcswap(x, y, t) (t) = (x); (x) = (y); (y) = (t)
#define libcsimplelt(x, y)  ((x) < (y))
#define libcsimpleeq(x, y)  ((x) == (y))
extern int libcintcmp(const void *x, const void *y);
#define libcquicksort(type, pdat, ncnt, pltfunc, peqfunc, pcmpfunc) do { int stack[1024], top = 1, l, r, k, i, j, p, q;  type v, t;       /* stack保存要排序数据的起止点 */
 stack[0] = 0;    \    
 stack[1] = (ncnt) - 1;   while (top >= 0) {     r = stack[top--]; l = stack[top--];    /* 从堆栈中弹出要排序数据范围，即排序[l, r]之间的数据 */
  i = l - 1; j = r; p = i; q = r;     v = (pdat)[r];         /* 在数据量比较少时改用插入排序 */
  if (r <= l + 31)          continue;            for (;;) {              while (pltfunc((pdat)[++i], v));       while (pltfunc(v, (pdat)[--j])) if (j == l) break;     if (i >= j) break;           libcswap((pdat)[i], (pdat)[j], t);       if (peqfunc((pdat)[i], v)) { p++; libcswap((pdat)[p], (pdat)[i], t); }     if (peqfunc(v, (pdat)[j])) { q--; libcswap((pdat)[j], (pdat)[q], t); }    }               libcswap((pdat)[i], (pdat)[r], t);       j = i - 1; i++;           for (k = l; k < p; k++, j--) { libcswap((pdat)[k], (pdat)[j], t); }    for (k = r - 1; k > q; k--, i++) { libcswap((pdat)[i], (pdat)[k], t); }   if (top < 1019){            /* 相当于递归调用qsort(pdat, l, j) */
   stack[++top] = l; stack[++top] = j;       /* 相当于递归调用qsort(pdat, i, r) */
   stack[++top] = i; stack[++top] = r;      }               else {               /* 堆栈溢出，调用libc的qsort() */
   qsort((pdat), j - l + 1, sizeof(type), pcmpfunc);     qsort((pdat) + i, r - i + 1, sizeof(type), pcmpfunc);   }                }                 /* 插入排序 */
 for (i = 1; i < ncnt; i++) {    t = (pdat)[i];       for (j = i; j > 0 && pltfunc(t, (pdat)[j - 1]); j--)    (pdat)[j] = (pdat)[j - 1];   (pdat)[j] = t;      }         } while(0);

这样，用：

libcquicksort(int, pdat, ncnt, libcsimplelt, libcsimpleeq, libcintcmp);

就可以完成对一个整数数组的排序。在我的机器上，该函数排序整型数据的效率大概是libc中qsort()的2.5倍。
当然效率的提高也有副作用，比如要定义三个比较函数，而原来只要一个（有时候也可以简化，如libcsimplelt函数实际上可用于任何简单类型的比较），在调用排序之前要对数据类型进行判断（一大堆switch..case）。另外，我对堆栈溢出时的处理方式总是不满意，搞来搞去还是要调用libc，因此把这个算法写出来，大家看看还能如何改进？