排序算法是大家刚学编程的时候一定要学的算法,冒泡算法(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)。算是比较快速的排序算法,不过就跟所有算法一样,其实都是时间和空间上的取舍。它的空间复杂度相当大,尤其是在整数上限很大的情况下,更是占用了不少内存。所以,大家还是要按情况使用。