Heap sort Sample
2014年03月22日
⁄ 综合
⁄ 共 1323字 ⁄ 字号
小 中 大
- static void u32_swap(void *a, void *b, int size)
- {
- u32 t = *(u32 *)a;
- *(u32 *)a = *(u32 *)b;
- *(u32 *)b = t;
- }
- static void generic_swap(void *a, void *b, int size)
- {
- char t;
- do {
- t = *(char *)a;
- *(char *)a++ = *(char *)b;
- *(char *)b++ = t;
- } while (--size > 0);
- }
- void sort(void *base, size_t num, size_t size,
- int (*cmp)(const void *, const void *),
- void (*swap)(void *, void *, int size))
- {
-
- int i = (num/2 - 1) * size, n = num * size, c, r;
- if (!swap)
- swap = (size == 4 ? u32_swap : generic_swap);
-
- for ( ; i >= 0; i -= size) {
- for (r = i; r * 2 + size < n; r = c) {
- c = r * 2 + size;
- if (c < n - size && cmp(base + c, base + c + size) < 0)
- c += size;
- if (cmp(base + r, base + c) >= 0)
- break;
- swap(base + r, base + c, size);
- }
- }
-
- for (i = n - size; i > 0; i -= size) {
- swap(base, base + i, size);
- for (r = 0; r * 2 + size < i; r = c) {
- c = r * 2 + size;
- if (c < i - size && cmp(base + c, base + c + size) < 0)
- c += size;
- if (cmp(base + r, base + c) >= 0)
- break;
- swap(base + r, base + c, size);
- }
- }
- }