三种线性时间排序算法 - C++实现 (三)

#include
#include

const int N =10;
double input[N+1] = {-1, 0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};
typedef struct BucketNode
{
double data;
struct BucketNode* next;
}* bucketList, bucketNode;
bucketList bucketArr[N];

void print(bucketList bucketArr[])
{
for(int i = 0; i < N; i++)
{
bucketNode* pb = bucketArr[i];
while(pb)
{
printf("%e ", pb->data);
pb = pb->next;
}
printf("\n");

}
printf("\n");
}

void initBucketList(bucketList bucketArr[])
{
for(int i = 0; i < N; i++)
{
bucketArr[i] = NULL;
}
}
bool insertBucketWithSorting(bucketList& bucket, double data)
{//sorting while inserting
bucketNode* pb = new bucketNode;
if(NULL == pb)
return false;
pb->data = data;
if(NULL == bucket || pb->data < bucket->data)
{//insert before the first element
pb->next = bucket;
bucket = pb;
return true;
}

bucketNode* ptemp = bucket;
bucketNode* ptempn = bucket->next;
while(ptempn)
{//insert after the first element(that is in the middle)
if(pb->data < ptempn->data)
{
pb->next = ptempn;
ptemp->next = pb;
break;
}
ptemp = ptempn;
ptempn = ptempn->next;
}
if(NULL == ptempn)
{//insert after the last element
ptemp->next = pb;
pb->next = NULL;
}

return true;
}

void destroyBucketList(bucketList bucketArr[])
{
for(int i = 0; i < N; i++)
{
while(bucketArr[i]!= NULL)
{
bucketNode* pb = bucketArr[i];
bucketArr[i] = bucketArr[i]->next ;
delete pb;
pb = NULL;
}
}

}
void bucketSort(double input[], bucketList bucketArr[],int n)
{
for(int i = 1; i <= n; i++)
{
int index = (int)floor(input[i]*n);
insertBucketWithSorting(bucketArr[index], input[i]);
}

}

int main()
{
initBucketList(bucketArr);
bucketSort(input, bucketArr, N);
print(bucketArr);

destroyBucketList(bucketArr);

return 0;
}