Instantly share code, notes, and snippets.

# thinkphp/heap_sort.c Created May 8, 2017

What would you like to do?
Heap Sort in action.
 #include #define size 100 #define FIN "algsort.in" #define FOUT "algsort.out" #define SIZE 500005 int arr[SIZE], n; void create_heap() { int i, j; for(i = 2; i <= n; i++) { j = i; while(j > 1) { if(arr[ j ] <= arr[ j / 2 ]) { int aux = arr[j]; arr[j] = arr[j/2]; arr[j/2] = aux; j /= 2; } else j = 1;//or break } } }; int eliminate() { int i, j, x = arr[1]; arr[ 1 ] = arr[ n ]; n--; i = 1; while(i <= n) { if( 2 * i <= n ) { j = 2 * i; if(j + 1 <= n && arr[j + 1] <= arr[ j ]) j++; if(arr[ i ] >= arr[ j ]) { int aux = arr[i]; arr[i] = arr[j]; arr[j] = aux; i = j; } else break; } else break; } return x; }; void print() { int i; for(i = 1; i <= n; i++) printf("%d ",arr[i]); printf("\n"); }; int main() { int i; freopen(FIN, "r", stdin); freopen(FOUT, "w", stdout); scanf("%d",&n); for(i = 1; i <= n; i++) scanf("%d", &arr[i]); create_heap(); for(i = n; i >= 1; i--) { printf("%d ", eliminate()); } print(); return(0); };