Bucket-Sort

原创
2015/12/26 17:34
阅读数 107
 
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <alloca.h>
#include <math.h>
#include <vector>
#include <malloc.h>
using namespace std;

typedef struct node
{
	float value;
	struct node* next;
}node,*nodeptr;

void print(nodeptr p)
{
	if(p==NULL) return;
	printf("%4f ",p->value);
	print(p->next);
}
void bucket_sort(vector<float>& values)
{
	vector<node> buckets(values.size());
	auto insert_bucket=[&buckets](int i,float value)
	{
		auto prePtr=&buckets[i];
		while((prePtr->next!=NULL)&&(prePtr->next->value<value)) prePtr=prePtr->next;
		auto temp=(nodeptr)malloc(sizeof(node));
		temp->value=value;
		temp->next=prePtr->next;
		prePtr->next=temp;
	};
	for(auto i=buckets.begin();i!=buckets.end();++i)
	{
		(*i).next=NULL;
		(*i).value=0;
	}
	for(auto i=values.begin();i!=values.end();++i)
	{
		insert_bucket(int(values.size()**i),*i );
	}
	for(auto i=buckets.begin();i!=buckets.end();++i)
		print((*i).next);
}
	template<class T>
void print(string format,vector<T> & vectort)
{
	for(auto i=vectort.begin();i!=vectort.end();++i)
	{
		printf(format.c_str(),*i);
	}
	putchar('\n');
}
int main()
{
	vector<float> array;
	for(int i=0;i<1000;++i) array.push_back((float)(random()%1000/1000.0));
	print("%4f ",array);
	bucket_sort(array);
	return 0;
}



展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部