桶排序
2013-01-03 12:18:11 最后更新: 2015-08-06 19:11:25 访问数量：1923
概述
与堆排序一样，桶排序也是一个基于数据结构的排序算法，桶排序所基于的数据结构就是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);
}
微信公众号
欢迎关注微信公众号，以技术为主，涉及历史、人文等多领域的学习与感悟，每周三到七篇推文，只有全部原创，只有干货没有鸡汤
