桶排序
visualxyk
posted @ 2011年8月17日 16:15
in 未分类
, 717 阅读
#include <iostream>
using namespace std;
class listnode
{
public:
int elem;
listnode* next;
listnode()
{
next = 0;
}
};
class list
{
public:
listnode* head;
list()
{
head = NULL;
}
~list()
{
listnode* t = head;
while (t != 0)
{
listnode* tmp = t;
t = t->next;
delete tmp;
}
}
void insertElem(int elem)
{
listnode* node = new listnode();
node->elem = elem;
node->next = 0;
if (head == NULL)
{
head = node;
}
else
{
if (node->elem < head->elem)
{
node->next = head;
head = node;
}
else
{
listnode* prev = head;
listnode* t = head->next;
while (t != 0)
{
if (node->elem < t->elem)
{
prev->next = node;
node->next = t;
return ;
}
prev = t;
t = t->next;
}
prev->next = node;
}
}
}
void print_list()
{
listnode* t = head;
while (t)
{
cout << t->elem << " ";
t = t->next;
}
cout << endl;
}
};
void print_array(int* array, int size)
{
for (int i=0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void bucket_sort(int* array, int size)
{
list* buckets = new list[10]; //假设分成10个区间
for (int i=0; i<10; i++)
buckets[i].head = NULL;
for (int i=0; i<size; i++)
{
int which_bucket = array[i] / 100;
buckets[which_bucket].insertElem(array[i]);
}
int m = 0;
for (int i=0; i<10; i++)
{
// copy back
listnode* t = buckets[i].head;
while (t != 0)
{
array[m] = t->elem;
t = t->next;
m++;
}
}
delete[] buckets;
}
void main()
{
int* array = 0;
int size;
cout << "input the size:";
cin >> size;
array = new int[size];
for (int i=0; i<size; i++)
{
array[i] = rand()%1000;
}
print_array(array, size);
bucket_sort(array, size);
print_array(array, size);
}
2021年9月15日 23:40
I love visiting sites in my free time. I have visited many sites but did not find any site more efficient than yours. Thanks for the nudge! 123movies
2021年11月04日 08:12
Took me time to read all the comments, but I really enjoyed the article. It proved to be Very helpful to me and I am sure to all the commenters here! It's always nice when you can not only be informed, but also entertained! 오피 아트
2023年1月31日 02:36
It’s very informative and you are obviously very knowledgeable in this area. You have opened my eyes to varying views on this topic with interesting and solid content.
2023年2月04日 09:34
I really enjoy simply reading all of your weblogs. Simply wanted to inform you that you have people like me who appreciate your work. Definitely a great post. Hats off to you!
2023年3月21日 09:39
this is amazing!! I love it a lot thanks for this wonderful website
2023年4月18日 13:29
Today, I was just browsing along and came upon your blog. Just wanted to say good blog and this article helped me a lot, due to which I have found exactly I was looking
2023年5月06日 22:11
Hey there! I know this is kinda off topic but I was wondering if you knew where I could get a captcha plugin for my comment form? I’m using the same blog platform as yours and I’m having difficulty finding one? Thanks a lot
2023年6月04日 09:58
I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work.
2023年7月03日 03:31
What a fantabulous post this has been. Never seen this kind of useful post. I am grateful to you and expect more number of posts like these. Thank you very much.
2023年8月19日 09:00
I was very pleased to find this site.I wanted to thank you for this great read!! I definitely enjoy every little bit of it and I have you bookmarked to check out new stuff you post.
2023年9月14日 10:52
I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work.
2023年9月25日 10:27
I was exceptionally satisfied to find this site.I needed to thank you for this extraordinary read!! I most certainly partaking in every single piece of it and I have you bookmarked to look at new stuff you post.
2023年11月04日 10:01
I’m happy to find so many useful info here in the post, thanks for sharing. I love the variety of content available on your website. I’ll bookmark your blog and take the feeds also!