{
break;
}
}
}
tmp = arr[0];
arr[0] = arr[num-1];
arr[num-1] = tmp;
}
}
测试代码：
#include
#include
#include <windows.h>
void HeapSort(int * const arr, const DWORD number);//堆排序
void ExamineArr(const int * const arr, DWORD number);//检查排序结果
int main(int argc, char *argv[])
{
DWORD StartTime, EndTime;
DWORD i;
DWORD num = 50000000;
int *arr = NULL;
arr = (int *)malloc(num * sizeof (int));
if (NULL == arr)
{
free(arr);
printf("内存分配失败，程序退出！\n");
getch();
return -1;
}
StartTime = GetTickCount();
for (i=0; i {
*(arr+i) = rand();
}
EndTime = GetTickCount();
printf("生成%u个随机数耗时：%ums\n", num, EndTime - StartTime);
StartTime = GetTickCount();
HeapSort(arr, num);
EndTime = GetTickCount();
printf("堆排序耗时：%ums\n", EndTime - StartTime);
ExamineArr(arr, num);//检查排序结果
free(arr);
getch();
return 0;
}
void HeapSort(int * const arr, const DWORD number)//堆排序
{
int tmp;
DWORD tmpIndex;
DWORD i=1;
DWORD num;
DWORD indexUp;
DWORD indexDown;
if (number < 2)
{
return;
}
indexUp = number-1;
if (0 != (indexUp%2))
{
tmpIndex = (indexUp - 1) / 2;
if (arr[indexUp] > arr[tmpIndex])
{
tmp = arr[indexUp];
arr[indexUp] = arr[tmpIndex];
arr[tmpIndex] = tmp;
}
indexUp--;
}
for (; indexUp>0; indexUp-=2)
{
tmpIndex = (indexUp / 2) - 1;
if (arr[indexUp-1] >= arr[indexUp])
{
if (arr[indexUp-1] > arr[tmpIndex])
{
tmp = arr[indexUp-1];
arr[indexUp-1] = arr[tmpIndex];
arr[tmpIndex] = tmp;
indexDown = indexUp-1;
}
else
{
continue;
}
}
else
{
if (arr[indexUp] > arr[tmpIndex])
{
tmp = arr[indexUp];
arr[indexUp] = arr[tmpIndex];
arr[tmpIndex] = tmp;
indexDown = indexUp;
}
else
{
continue;
}
}
while ((2*indexDown) < number)
{
tmpIndex = 2*indexDown +1;
if (arr[tmpIndex] >= arr[tmpIndex+1] || (tmpIndex+1 == number))
{
if (arr[tmpIndex] > arr[indexDown])
{
tmp = arr[indexDown];
arr[indexDown] = arr[tmpIndex];
arr[tmpIndex] = tmp;
indexDown = tmpIndex;
}
else
{
break;
}
}
else
{
if ((arr[tmpIndex+1] > arr[indexDown]) && (tmpIndex < number))
{
tmp = arr[indexDown];
arr[indexDown] = arr[tmpIndex+1];
arr[tmpIndex+1] = tmp;
indexDown = tmpIndex+1;
}
else
{
break;
}
}
}
}
tmp = arr[0];
arr[0] = arr[number-1