2015年9月17日

Heap Sort 堆疊排序法

#include "iostream"

void heapsort(int data[],int number);
void heap(int data[],int index,int n);
int main()
{
    int number=9;
    int data[]={5,6,4,8,2,3,7,9,1};
    int i;

    for (i=0;i<number;i++){
        printf("%d",data[i]);
    }
    printf("\n");

    heapsort(data,number);

    printf("\n");
    for (i=0;i<number;i++){
        printf("%d",data[i]);
    }

    printf("\n");
    system("PAUSE");
    return 0;
}

void heapsort(int data[],int n){
    int i;
    for (i=(n-2)/2;i>=0;i--)
    {
        heap(data,i,n);
    }
 
    for (i=n-1;i>=0;i--)
    {
        int temp=data[0];
        data[0]=data[i];
        data[i]=temp;
        heap(data,0,i);
    }
}
void heap(int data[],int index,int n){
     int left=index*2+1;
     int right=index*2+2;
     int largest=index;
     int i;
   
     if ((left<n)&&(data[left]>data[largest]))
     {
     largest=left;
     }
     if ((right<n)&&(data[right]>data[largest]))
     {
     largest=right;
     }
   
     if (index!=largest)
     {
       int temp=data[index];
       data[index]=data[largest];
       data[largest]=temp;
       heap(data,largest,n);
     }
   
}

沒有留言:

張貼留言