Heap Sort - Delphi K.Top 討論區

發表時間：2002-08-27 10:58:17

IP:61.231.xxx.xxx 未訂閱

Heap Sort , 也這是一個 Order(n log n) 的排序演算法，其效能比 Merge Sort 還好喔！您可以試著比較看看，或看看原始碼，找出為什麼 Heap Sort 會比 Merge Sort 要快 ... 這就當成是作業好了 > < class="code"> /*---------------------------------------------------------------------------//
// heapsort.c heap sort algorithm //
// //
// Jun.07,2000 Version 0.1 by : Lee Dong-Liang //
//---------------------------------------------------------------------------*/
/*---------------------------------------------------------------------------//
// Command Line Usage: //
// //
// sort [] //
// //
// the default NumberOfData=2000 //
// //
// Data File Format //
// ... //
// xxxxxxx = {IntegerData_i} //
// xxxxxxx = {IntegerData_i 1} //
// ... //
// i.e. one line contain only one data //
// //
// Restriction: the length of line data must < 128 //
// //
// If the number of data in DataFile is less than NumberOfData, the sorting //
// will according to the number of data in DataFile. //
// But If the number of data in DataFile is more than NumberOfData, the //
// sorting will according to NumberOfData. //
//---------------------------------------------------------------------------*/

#include /* for printf,fopen,fclose,fgets,... */
#include /* for calloc,free, atoi */

int MAXIMUM_DATANUM=2000; /* default Maximum data number = 2000 */

int ReadDataFromFile(char *filename,int *piData);
void heapsort(int *piData,int iDataNumber);

int main(int argc, char *argv[])
{
int i,iDataNumber;
int *piData;

if(argc < 2 ) /* Check input command line */
{ /* If error , exit */
printf("Usage: %s []\n",argv[0]);
return 1;
}

if(argc > 2 ) /* Check input command line */
{ /* If user spec. NumberOfData */
MAXIMUM_DATANUM=atoi(argv[2]);
if(MAXIMUM_DATANUM<=0) MAXIMUM_DATANUM=2000; /* If error , set to default */
}

piData=(int *) calloc(MAXIMUM_DATANUM 1,sizeof(int)); /* Allocate Memory */
/* Heap sort is 1-based */
if(piData==NULL) /* Check Memory Status */
{
printf("Allocate Memory ERROR!!!\n");
return 2;
}

iDataNumber=ReadDataFromFile(argv[1],piData 1); /* Read Source Data File */
/* Heap sort is 1-based */
if( iDataNumber==0 ) /* If error , exit */
{
printf("Error of reading file : \"%s\" !!!\n",argv[1]);
printf("Please check : If the filename is correct ?\n");
printf(" If the file format is correct ?\n");
free(piData);
return 3;
}

heapsort(piData,iDataNumber); /* Heap Sort */

printf(" Heap \n"); /* Show Result */
printf("========\n");
for(i=0;i printf("}\n",piData[i 1]); /* Heap sort is 1-based */
printf("========\n");

free(piData); /* Free Allocated Memory */

return 0;
}

/*---------------------------------------------------------------------------//
// Data File Format //
// ... //
// xxxxxxx = {IntegerData_i} //
// xxxxxxx = {IntegerData_i 1} //
// ... //
// i.e. one line contain only one data //
// //
// Restriction: the length of line data must < 128 //
//---------------------------------------------------------------------------*/
int ReadDataFromFile(char *filename,int *piData)
{
FILE *pFile;
int i,iDataNumber=0;
char strtemp[128];
char *strNumber;

pFile=fopen(filename,"r"); /* Open File */
if( pFile == NULL ) return 0;

for(;fgets(strtemp,128,pFile)!=NULL;) /* Read a Line from File */
{
for(i=0;i<128;i ) /* Finding '=' */
if(strtemp[i]=='=' || strtemp[i]=='\0')break;
if(strtemp[i]!='=')continue; /* '=' Not Found ,continue next line */

for(i ;i<128;i ) /* Finding '{' */
if(strtemp[i]=='{' || strtemp[i]=='\0')break;
if(strtemp[i]!='{')continue; /* '{' Not Found ,continue next line */

strNumber=&strtemp[i 1]; /* Data Start from Here! */

for(i ;i<128;i ) /* Finding '}' */
if(strtemp[i]=='}' || strtemp[i]=='\0')break;
if(strtemp[i]!='}')continue; /* '{' Not Found ,continue next line */
strtemp[i]='\0';

piData[iDataNumber ]=atoi(strNumber); /* Convert Data */
if(iDataNumber>=MAXIMUM_DATANUM) break; /* Test if Reach Buffer Len */
}
fclose(pFile); /* Close File */
return iDataNumber;
}
/*---------------------------------------------------------------------------//
// heapsort algorithm //
// //
// procedure sift-down(T[1..n],i) //
// {This procedure sifts node i down so as to re-establish the heap //
// property in T[1..n]. We suppose that T would be a heap if T[i] //
// were sufficiently large. We also suppose that 1 <= i <= n } //
// k = i //
// repeat //
// j = k //
// { find the larger child of node j } //
// if 2j <= n and T[2j] > T[k] then k = 2j //
// if 2j < n and T[2j 1] > T[k] then k = 2j 1 //
// exchange T[j] and T[k] //
// { if j=k, then the node has arrived at its final position } //
// until j=k //
// //
// procedure make-heap(T[1..n]) //
// {This procedure makes the array T[1..n] into a heap } //
// for i =[n/2] down to 1 do sift-down(T,i) //
// //
// procedure heapsort(T[1..n]) //
// { T is an array to be sorted } //
// make-heap(T) //
// for i&

------
http://www.ViewMove.com