桶排序

2013-01-03 12:18:11   最后更新: 2015-08-06 19:11:25   访问数量:562




与堆排序一样,桶排序也是一个基于数据结构的排序算法,桶排序所基于的数据结构就是HashMap,由于在数据均匀分布的情况下,哈希表的遍历和插入的时间复杂度都是线性的,因此,桶排序在输入符合均匀分布时,也可以以线性时间运行

 

 

/* * file: main.c * author: 龙泉居士 * date: 2013-01-09 16:24 */ #include <stdio.h> #include <malloc.h> #include "function/function.h" int bucket_sort (int *array, int n) { if (array == NULL || n<=0) { printf ("bucket_sort param error\n"); return -1; } Node **tmp = (Node**)malloc(10*sizeof(Node*)); int i; for (i=0; i<10; ++i) { Node *n = (Node *)malloc(sizeof(Node)); tmp[i] = n; tmp[i]->next = NULL; } for (i=0; i<n; ++i) insert (tmp, array[i]); give_value (tmp, array); return 0; } int main () { int i, n=0; int array[256]; printf ("Please input numbers, end by 9999:\n"); while (1) { scanf ("%d", &array[n]); if (array[n] == 9999) break; ++n; } if (bucket_sort(array, n)) return -1; for (i=0; i!=n; ++i) printf ("%d ", array[i]); printf ("\n"); return 0; }

 

/* * file: function.h * author: 龙泉居士 * date: 2013-01-09 16:25 */ #ifndef FUNCTION_H_20130109 #define FUNCTION_H_20130109 typedef struct Node { int value; struct Node *next; } Node; void insert (Node **tmp, int v); void give_value (Node **tmp, int *array); int bucket_sort (int *array, int n); #endif

 

/* * file: function.c * author: 龙泉居士 * date: 2013-01-09 16:25 */ #include <stdio.h> #include <malloc.h> #include "function.h" void insert (Node **tmp, int v) { Node *n = (Node *)malloc(sizeof(Node)); n->value = v; Node *rec = tmp[v/10]; Node *c = rec->next; while (c!=NULL) { if (c->value >= v) break; rec = c; c = c->next; } rec -> next = n; n -> next = c; } void give_value (Node **tmp, int *array) { int i, j=0; for (i=0; i!=10; ++i) { Node *n = tmp[i]->next; free(tmp[i]); while (n != NULL) { array[j] = n->value; ++j; Node *tmpn = n; n = n->next; free(tmpn); } } free (tmp); }

 

 






读书笔记      技术帖      算法      算法导论      数据结构      龙潭书斋      排序      hash      sort      哈希表      hashtable     


京ICP备15018585号