堆排序 (二)

void HeapAdjust(int* ua, int nStart, int nEnd)
{
int nMaxIndex = 0;

while ( ( 2*nStart + 1) < nEnd )
{
nMaxIndex = 2*nStart + 1;
if ( ( 2*nStart + 2) < nEnd)
{
//比较左子树和右子树,记录较大值的Index
if (ua[2*nStart + 1] < ua[2*nStart + 2])
{
nMaxIndex++;
}
}

//如果父结点大于子节点，则退出，否则交换
if (ua[nStart] > ua[nMaxIndex])
{
break;
}
else
{
swap( ua[nStart], ua[nMaxIndex] );
//堆被破坏,继续递归调整
nStart = nMaxIndex;
}
}
for (int i = 0; i < N; i++)
{
printf("%d ",ua[i]);
}
printf("\r\n");
//printf("%d ", O++);
}

void HeapSort(int* ua, int nStart, int nEnd)
{
for (int i = nEnd/2 -1; i >= 0 ; i--)
{
HeapAdjust( ua, i, nEnd);
}

for (int i = nEnd-1; i > 0; i--)
{
swap(ua[0], ua[i]);
HeapAdjust(ua, 0, i);
}
}
[cpp]
SYSTEMTIME StartTime = {0};
FILETIME StartFileTime = {0};
SYSTEMTIME EndTime= {0};
FILETIME SEndFileTime= {0};

int _tmain(int argc, _TCHAR* argv[])
{
//int* a = GenRandom();
int a[] = {3,4,9,7,5,6,10,8,2,1};
GetLocalTime(&StartTime);
printf("timeBefore %d:%d:%d \r\n", StartTime.wMinute, StartTime.wSecond, StartTime.wMilliseconds);

HeapSort(a, 0, N);

GetLocalTime(&EndTime);
printf("timeAfter %d:%d:%d \r\n", EndTime.wMinute, EndTime.wSecond, EndTime.wMilliseconds);
printf("times %d \r\n", O);
return 0;
}

SYSTEMTIME StartTime = {0};
FILETIME StartFileTime = {0};
SYSTEMTIME EndTime= {0};
FILETIME SEndFileTime= {0};

int _tmain(int argc, _TCHAR* argv[])
{
//int* a = GenRandom();
int a[] = {3,4,9,7,5,6,10,8,2,1};
GetLocalTime(&StartTime);
printf("timeBefore %d:%d:%d \r\n", StartTime.wMinute, StartTime.wSecond, StartTime.wMilliseconds);

HeapSort(a, 0, N);

GetLocalTime(&EndTime);
printf("timeAfter %d:%d:%d \r\n", EndTime.wMinute, EndTime.wSecond, EndTime.wMilliseconds);
printf("times %d \r\n", O);
return 0;
}