我们可以改进通用快速排序以省略交换功能。
#ifdef _WIN32
#define alloca _alloca
#else
#include <alloca.h>
#endif
// the generic swap function
void arrswap(void * const a, void * const b, int const sz) {
int64_t tmp;
void * p;
bool needfree = false;
if (sz > sizeof(int64_t)) {
p = alloca(sz);
if (p == NULL) {
p = malloc(sz);
//assert(p != NULL, "not enough memory");
needfree = true;
}
}
else {
p = &tmp;
}
memcpy(p, b, sz);
memcpy(b, a, sz);
memcpy(a, p, sz);
if (needfree) {
free(p);
}
}
// O(n^2) sort
void arrsort(void * const p, int const sz, int const n,
int(*compare)(void const * const pa, void const *const pb)) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (compare((char*)p + i*sz, (char*)p + j*sz) == 1) {
arrswap((char*)p + i*sz, (char*)p + j*sz, sz);
}
}
}
}
// guess the index of the pivot value from three value in the array.
static int guessmidval(void * const p, int const sz, int const n,
int(*compare)(void const * const pa, void const *const pb)) {
int a = 0;
int b = n / 2;
int c = n - 1;
int ab = compare((char*)p + a*sz, (char*)p + b*sz);
int bc = compare((char*)p + b*sz, (char*)p + c*sz);
int cb = compare((char*)p + c*sz, (char*)p + b*sz);
int ba = compare((char*)p + b*sz, (char*)p + a*sz);
if (ab <= 0 && bc <= 0 || cb <= 0 && ba <= 0) {
return b;
}
int ac = compare((char*)p + a*sz, (char*)p + c*sz);
int ca = compare((char*)p + c*sz, (char*)p + a*sz);
if (ba <= 0 && ac <= 0 || ca <= 0 && ab <= 0) {
return a;
}
return c;
}
// quick sort
void arrqsort(void * const p, int sz, int const n,
int(*compare)(void const * const pa, void const *const pb)) {
if (n <= 2) {
arrsort(p, sz, n, compare);
return;
}
int midval_index = guessmidval(p, sz, n, compare);
arrswap(p, (char*)p + midval_index*sz, sz);
int i, j;
for (i = 1, j = n - 1; ; i++, j--) {
for (; compare((char*)p + i*sz, p) <= -1 && i <= j; i++);
for (; compare((char*)p + j*sz, p) >= +1 && i <= j; j--);
if (i >= j)break;
arrswap((char*)p + i*sz, (char*)p + j*sz, sz);
}
arrqsort(p, sz, i, compare);
arrqsort((char*)p + i*sz, sz, n - i, compare);
}
为 int64 创建比较函数:
int compare_int64(void const * const pa, void const *const pb) {
int64_t a = *(int64_t*)pa;
int64_t b = *(int64_t*)pb;
if (a > b)return 1;
else if (a < b)return -1;
return 0;
}
我们可以arrqsort
这样称呼:
int64_t a[] = { 3,1,65,4,-1 };
int n = sizeof(a) / sizeof(*a);
arrqsort(a, sizeof(*a), n, compare_int64);
for (int j = 0; j < n; j++) {//-1,1,3,4,65,
printf("%d,", a[j]);
}