近来编写一个对性能要求很高的程序，要用到排序功能。要排序的数据类型有很多种，有整数、浮点数、各种结构（根据某个属性进行比较）等。如果调用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，因此把这个算法写出来，大家看看还能如何改进？