qsort.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

/* qsort -- qsort interface implemented by faster quicksort */
#include <stdlib.h>

#define SWAPINIT(a, es) swaptype =                            \
    (a - (char*) 0) % sizeof(long) || es % sizeof(long) ? 2 : \
    es == sizeof(long) ? 0 : 1;
#define swapcode(TYPE, parmi, parmj, n) {  \
    long i = (n) / (int) sizeof(TYPE);     \
    register TYPE *pi = (TYPE *) (parmi);  \
    register TYPE *pj = (TYPE *) (parmj);  \
    do {                                   \
        register TYPE t = *pi;             \
        *pi++ = *pj;                       \
        *pj++ = t;                         \
    } while (--i > 0);                     \
}
static void swapfunc(char *a, char *b, int n, int swaptype)
{   if (swaptype <= 1) swapcode(long, a, b, n)
    else swapcode(char, a, b, n)
}
#define swap(a, b) {                       \
    if (swaptype == 0) {                   \
        long t = * (long *) (a);           \
        * (long *) (a) = * (long *) (b);   \
        * (long *) (b) = t;                \
    } else                                 \
        swapfunc(a, b, es, swaptype);      \
}
#define vecswap(a, b, n) { if (n > 0) swapfunc(a, b, n*es, swaptype); }

static char *med3func(char *a, char *b, char *c, int (*cmp)(const void *, const void *))
{	return cmp(a, b) < 0 ?
		  (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a ) )
		: (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c ) );
}
#define med3(a, b, c) med3func(a, b, c, cmp)

void qsort(void *va, size_t n, size_t es, int (*cmp)(const void *, const void *))
{
	char *a, *pa, *pb, *pc, *pd, *pl, *pm, *pn;
	int  r, swaptype, na, nb, nc, nd, d;

	a = va;
	SWAPINIT(a, es);
	if (n < 7) { /* Insertion sort on small arrays */
		for (pm = a + es; pm < a + n*es; pm += es)
			for (pl = pm; pl > a && cmp(pl-es, pl) > 0; pl -= es)
				swap(pl, pl-es);
		return;
	}
	pm = a + (n/2) * es;
	if (n > 7) {
		pl = a;
		pn = a + (n-1) * es;
		if (n > 40) { /* On big arrays, pseudomedian of 9 */
			d = (n/8) * es;
			pl = med3(pl, pl+d, pl+2*d);
			pm = med3(pm-d, pm, pm+d);
			pn = med3(pn-2*d, pn-d, pn);
		}
		pm = med3(pl, pm, pn); /* On medium arrays, median of 3 */
	}
	swap(a, pm); /* On tiny arrays, partition around middle */
	pa = pb = a + es;
	pc = pd = pn = a + (n-1)*es;
	for (;;) {
		while (pb <= pc && (r = cmp(pb, a)) <= 0) {
			if (r == 0) { swap(pa, pb); pa += es; }
			pb += es;
		}
		while (pb <= pc && (r = cmp(pc, a)) >= 0) {
			if (r == 0) { swap(pc, pd); pd -= es; }
			pc -= es;
		}
		if (pb > pc) break;
		swap(pb, pc);
		pb += es;
		pc -= es;
	}
	na = (pa - a)  / es;
	nb = (pb - pa) / es;
	nc = (pd - pc) / es;
	nd = (pn - pd) / es;
	if (na < nb) { vecswap(a,  a + nb*es,  na); }
	else	     { vecswap(a,  a + na*es,  nb); }
	if (nc < nd) { vecswap(pb, pb + nd*es, nc); }
	else	     { vecswap(pb, pb + nc*es, nd); }
	if (nb > 1) qsort(a, nb, es, cmp);
	if (nc > 1) qsort(a + (n-nc) * es, nc, es, cmp);
}