", num, EndTime - StartTime);
StartTime = GetTickCount();
QuickSort(arr, num);
EndTime = GetTickCount();
printf("快速排序耗时：%ums\n", EndTime - StartTime);
ExamineArr(arr, num);//检查排序结果
free(arr);
getch();
return 0;
}
void QuickSort(int * const arr, DWORD number)//快速排序
{
int tmp;
int key;
DWORD left, right;
DWORD tmpLeft, tmpRight;
BUFF *p = NULL;
BUFF buff = {NULL, NULL, 0, NULL};
buff.LeftBuff = (int *)malloc(1024*1024*sizeof (int));
buff.RightBuff = (int *)malloc(1024*1024*sizeof (int));
if ((NULL == buff.LeftBuff) || (NULL == buff.LeftBuff))
{
free(buff.LeftBuff);
free(buff.LeftBuff);
printf("分配缓存出错！\n");
return;
}
buff.LeftBuff[buff.number] = 0;
buff.RightBuff[buff.number] = number-1;
buff.number++;
p = &buff;
while (buff.number/* && (NULL == buff.next)*/)
{
tmpLeft = p->LeftBuff[p->number-1];
tmpRight = p->RightBuff[p->number-1];
left = tmpLeft;
right = tmpRight;
key = arr[left++];
do
{
while ((arr[left] < key) && (left < tmpRight))
{
left++;
}
while ((arr[right] >= key) && (right > tmpLeft))
{
right--;
}
if (left < right)
{
tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
}
}
while (left < right);
tmp = arr[right];
arr[right] = arr[tmpLeft];
arr[tmpLeft] = tmp;
if (p->number >= 1024*1024-1)
{
p->next = (BUFF *)malloc(sizeof (BUFF));
if (NULL != p->next)
{
p = p->next;
p->LeftBuff = (int *)malloc(1024*1024*sizeof (int));
p->RightBuff = (int *)malloc(1024*1024*sizeof (int));
p->number = 0;
p->next = NULL;
}
if ((0 != p->number) || (NULL == p->LeftBuff) || (NULL == p->RightBuff))
{
printf("分配缓存出错！\n");
while (NULL != buff.next)
{
p = buff.next;
do
{
p = p->next;
}
while (NULL != p->next);
free(p);
}
getch();
return;
}
}
else
{
p->number--;
}
if (tmpLeft+1 < right)
{
p->LeftBuff[p->number] = tmpLeft;
p->RightBuff[p->number] = right-1;
p->number++;
}
if (tmpRight > left)
{
p->LeftBuff[p->number] = left;
p->RightBuff[p->number] = tmpRight;
p->number++;
}
if ((0 == p->number) && (NULL != buff.next))
{
p = &buff;
while (NULL == p->next->next)
{
p = p->next;
}
free(p->next);
p->next = NULL;
}
}
}
void ExamineArr(const int * const arr, DWORD number)
{
DWORD i=0, j=1;
if (number <2)
{
return;
}
for (; j {
if (arr[i] > arr[j])
{
printf("第%u个数 |