首页 > 程序开发 > 软件开发 > C语言 >

快速排序(非递归)

2012-01-05

以下代码经测试,排序5000000(五千万)int型数据没有问题!第一个参数是数组首地址第二个参数是数组元素个数typedef struct _BUFF { int *LeftBuff; int *RightBuff; DWORD number;//有多少个 struct...

以下代码经测试,排序5000000(五千万)int型数据没有问题!


第一个参数是数组首地址
第二个参数是数组元素个数

typedef struct _BUFF {
int *LeftBuff;
int *RightBuff;
DWORD number;//有多少个
struct _BUFF *next;
}BUFF;
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;
}
}
}
typedef struct _BUFF {
int *LeftBuff;
int *RightBuff;
DWORD number;//有多少个
struct _BUFF *next;
}BUFF;
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;
}
}
}

测试代码:

#include <stdio.h>
#include <conio.h>
#include <windows.h>

typedef struct _BUFF {
int *LeftBuff;
int *RightBuff;
DWORD number;//有多少个
struct _BUFF *next;
}BUFF;

void QuickSort(int * const arr, 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<num; i++)
{
*(arr+i) = rand();
}
EndTime = GetTickCount();
printf("生成%u个随机数耗时:%ums\n", 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<number; i++,j++)
{
if (arr[i] > arr[j])
{
printf("第%u个数大于第%u个数!\n", i, j);
return;
}
}
}

\

摘自 kevinshq的专栏

相关文章
最新文章
热点推荐