堆排序代码

#include <stdio.h>
#include <stdlib.h>

#define N 10
#define swap(x, y) {int t; t = x; x = y; y = t;}

static void createheap(int number[]);
static void heapsort(int number[]);

int main(int argc, char** argv)
{
        int number[N+1] = {0, 7, 9, 21, 55, 23, 2, 99, 44, 37, 44};
        int i;

        printf("Input data: ");
        for(i = 1; i <= N; i++){
                printf("%d ", number[i]);
        }
        printf("\n");
        printf("Create heap: ");
        createheap(number);
        for(i = 1; i <= N; i++){
                printf("%d ", number[i]);
        }
        printf("\n");
        heapsort(number);
        printf("\n");

        exit(0);
}

static void createheap(int number[])
{
        int heap[N+1] = {-1};
        int i, s, p;

        for(i = 1; i <= N; i++){
                heap[i] = number[i];
                s = i;
                p = s/2;
                while((s > 1) && (heap[p] > heap[s])){
                        swap(heap[p], heap[s]);
                        s = p;
                        p = s/2;
                }//while

        }

        for(i = 1; i <= N; i++){
                number[i] = heap[i];
        }
}

static void heapsort(int number[])
{
        int i, m, p, s;

        m = N;
        while(m > 1){//m-1次调整

                swap(number[1], number[m]);
                m--;
                p = 1;
                s = 2*p;
                while(s <= m){
                        if((s < m) && (number[s] > number[s+1])){
                                s++;
                        }
                        if(number[p] <= number[s]){
                                break;
                        }
                        swap(number[p], number[s]);
                        p = s;
                        s = 2*p;
                }
                printf("sorting: ");
                for(i = N; i > 0; i--){
                        printf("%d ", number[i]);
                }
                printf("\n");
        }
}


运行结果：
Input data: 7 9 21 55 23 2 99 44 37 44
Create heap: 7 9 21 55 23 2 99 44 37 44
sorting: 7 37 44 99 2 23 55 44 9 21
sorting: 7 21 44 99 2 23 55 44 9 37
sorting: 7 21 37 99 2 23 55 44 9 44
sorting: 7 21 37 44 99 23 55 2 9 44
sorting: 7 21 37 44 44 23 99 2 55 9
sorting: 7 21 37 44 44 9 99 2 55 23
sorting: 7 21 37 44 44 9 23 2 99 55
sorting: 7 21 37 44 44 9 23 55 99 2
sorting: 7 21 37 44 44 9 23 55 2 99