1/* Sort.c */ 2 3#include "Sort.h" 4 5#define HeapSortDown(p, k, size, temp) \ 6 { for (;;) { \ 7 UInt32 s = (k << 1); \ 8 if (s > size) break; \ 9 if (s < size && p[s + 1] > p[s]) s++; \ 10 if (temp >= p[s]) break; \ 11 p[k] = p[s]; k = s; \ 12 } p[k] = temp; } 13 14void HeapSort(UInt32 *p, UInt32 size) 15{ 16 if (size <= 1) 17 return; 18 p--; 19 { 20 UInt32 i = size / 2; 21 do 22 { 23 UInt32 temp = p[i]; 24 UInt32 k = i; 25 HeapSortDown(p, k, size, temp) 26 } 27 while(--i != 0); 28 } 29 /* 30 do 31 { 32 UInt32 k = 1; 33 UInt32 temp = p[size]; 34 p[size--] = p[1]; 35 HeapSortDown(p, k, size, temp) 36 } 37 while (size > 1); 38 */ 39 while (size > 3) 40 { 41 UInt32 temp = p[size]; 42 UInt32 k = (p[3] > p[2]) ? 3 : 2; 43 p[size--] = p[1]; 44 p[1] = p[k]; 45 HeapSortDown(p, k, size, temp) 46 } 47 { 48 UInt32 temp = p[size]; 49 p[size] = p[1]; 50 if (size > 2 && p[2] < temp) 51 { 52 p[1] = p[2]; 53 p[2] = temp; 54 } 55 else 56 p[1] = temp; 57 } 58} 59 60/* 61#define HeapSortRefDown(p, vals, n, size, temp) \ 62 { UInt32 k = n; UInt32 val = vals[temp]; for (;;) { \ 63 UInt32 s = (k << 1); \ 64 if (s > size) break; \ 65 if (s < size && vals[p[s + 1]] > vals[p[s]]) s++; \ 66 if (val >= vals[p[s]]) break; \ 67 p[k] = p[s]; k = s; \ 68 } p[k] = temp; } 69 70void HeapSortRef(UInt32 *p, UInt32 *vals, UInt32 size) 71{ 72 if (size <= 1) 73 return; 74 p--; 75 { 76 UInt32 i = size / 2; 77 do 78 { 79 UInt32 temp = p[i]; 80 HeapSortRefDown(p, vals, i, size, temp); 81 } 82 while(--i != 0); 83 } 84 do 85 { 86 UInt32 temp = p[size]; 87 p[size--] = p[1]; 88 HeapSortRefDown(p, vals, 1, size, temp); 89 } 90 while (size > 1); 91} 92*/