给力星

Web Developer

堆排序算法_C语言代码

堆排序算法

#include <stdio.h>
void swap(int a[], int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}
/* 保持堆的性质 */
void minHeapify(int a[], int heapSize, int i) {
    int left, right, small;
    left = i*2;
    right = i*2+1;
    small = i;
    if (left < heapSize && a[left] < a[i]) {
        small = left;
    }
    if (right < heapSize && a[right] < a[small]) {
        small = right;
    }
    if (small != i) {
        swap(a, small, i);
        minHeapify(a, heapSize, small); /* 自上而下递归 */
    }
}
/* 自下而上构建堆 */
void minHeapInit(int a[], int heapSize) {
    int i;
    for (i = heapSize/2; i >= 0; --i) {
        minHeapify(a, heapSize, i);
    }
}
/* 堆排序 */
void minHeapSort(int a[], int heapSize) {
    int i;
    for (i = heapSize-1; i > 0; --i) {
        swap(a, i, 0); /* 与根节点交换 */
        minHeapify(a, i, 0);
    }
}
int main() {
    int N, i, a[1000000];
    scanf("%d", &N);
    for (i = 0; i < N; i++) {
        scanf("%d", &a[i]);
    }
    minHeapInit(a, N);
    minHeapSort(a, N);
    for (i = N-1; i >= 0; --i) {
        printf("%d ", a[i]);
    }
    return 0;
}