Posts Tagged ‘bucket sort’

排序算法是大家刚学编程的时候一定要学的算法，冒泡算法(bubble sort)，快速排序(quick sort)等等相信大家耳熟能详。我下面要介绍的bucket sort其实大家应该也学过，不过最近刚刚帮别人交了一份作业，勾起了不少回忆，所以顺便在这里发出来。下面的算法有几个限制：所排序的一定要是正整数，至于整数的大小和个数都是可以修改的。

[code:c#]

#include
#include 

#define MAX_INT 65536
#define MAX_NO_INPUT 1000

struct bucket{
 int data;
 bucket* next;
};

void addToBucket(struct bucket *head[],int value)
{
 bucket* current;

 if (head[value] == NULL)
 {
  head[value] = (bucket*)malloc(sizeof(bucket));
  head[value]->data = value;
  head[value]->next = NULL;
 }
 else
 {
  current = head[value];
  while (current->next != NULL)
   current = current->next;
  current->next = (bucket*)malloc(sizeof(bucket));
  current->next->data = value;
  current->next->next = NULL;
 }
}
void printOut(bucket* head[],int size)
{
 int i=0;
 bucket *current;
 FILE *fp;

 fp = fopen("output.txt","w");

 for (i=size-1;i>=0;i--)
 {
  if (head[i] == NULL)
   continue;
  current = head[i];
  while(current != NULL)
  {
   fprintf(fp,"%d\n",current->data);
   current = current->next;
  }
 }
 fclose(fp);
}
int main()
{
 bucket* head[MAX_INT] = {NULL};
 int unsorted[MAX_NO_INPUT];
 FILE *fp;
 int i=0;

 //read in a file
 if ((fp = fopen("input.txt","r"))==NULL)
 {
  printf("Cannot open file");
  exit(0);
 }

 i=0;
 while (fscanf(fp,"%i\n",&unsorted[i])!=EOF && i< MAX_NO_INPUT)
  i++;
 fclose(fp);

 int length = i;
 i = 0;
 for (i=0;i

[/code]

以上的算法时间复杂度是O(n)。算是比较快速的排序算法，不过就跟所有算法一样，其实都是时间和空间上的取舍。它的空间复杂度相当大，尤其是在整数上限很大的情况下，更是占用了不少内存。所以，大家还是要按情况使用。