堆排序算法 Heap sort -- C source code

这是基于堆排序算法的C源代码，对于那些正在找工作的dd、mm们是很有帮助的，特将其共享与此！

typedef int element;

struct node {
    element key;
};
typedef struct node ARRAY;



void swap(element *A, element *B) {

    element tmp = *A;

    *A = *B;
    *B = tmp;
}

/* The index of ARRAY is start from zero */
void pushdown(int first, int last, ARRAY *A) {

    int r = first<<1;

    while(r+1 <= last) {
        if ((r+1 == last) && last%2==1 && A[first].key > A[r+1].key) {
            swap(&A[first].key, &A[r+1].key);
            first <<= 1;
        } else if (r+2 <= last && A[first].key > A[r+2].key && A[r+1].key > A[r+2].key) {
            swap(&A[first].key, &A[r+2].key);
            first = (first<<1) + 2;
        } else if (r+2 <= last && A[first].key > A[r+1].key && A[r+1].key <= A[r+2].key) {
            swap(&A[first].key, &A[r+1].key);
            first = (first<<1) + 1;
        } else {
        /* in this case, we do nothing */
            r = last;
            continue;
        }
        r = first<<1;
    }
}

void heap_sort(ARRAY *A, int n) {

    int i = 0;

    /* init the heap */
    for (i=n/2;i>=0;i--) {
        pushdown(i, n-1, A);
    }
    
    for(i=1;i<n;i++) {
        swap(&A[0].key, &A[n-i].key);
        pushdown(0, n-i-1, A);
    }
}

完整的程序可以在这里下载：

文件:	heap-sort.c.tar.gz
大小:	1KB
下载:	下载