首页 > 代码库 > 桶排序
桶排序
桶排序 (Bucket sort)工作的原理是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。
#include<iostream>struct barrel { int node[10]; int count; };void bucket_sort(int data[], int size){int max, min, num, pos; int i, j, k; struct barrel *pBarrel; max = min = data[0]; for (i = 1; i < size; i++) { if (data[i] > max) { max = data[i]; } else if (data[i] < min) { min = data[i]; } } num = (max - min + 1) / 10 + 1; pBarrel = (struct barrel*)malloc(sizeof(struct barrel) * num); memset(pBarrel, 0, sizeof(struct barrel) * num); /* put data[i] into barrel which it belong to */ for (i = 0; i < size; i++) { //quick_sort((pBarrel+i)->node, 0, (pBarrel+i)->count);/* sort node in every barrel */ k = (data[i] - min + 1) / 10;/* calculate the index of data[i] in barrel */ (pBarrel + k)->node[(pBarrel + k)->count] = data[i]; (pBarrel + k)->count++; } pos = 0; for (i = 0; i < num; i++) { for (j = 0; j < (pBarrel+i)->count; j++) { data[pos++] = (pBarrel+i)->node[j]; } } free(pBarrel); }void main(){ int data[] = {78, 17, 39, 26, 72, 94, 21, 12, 23, 91}, i; int size = sizeof(data) / sizeof(int); bucket_sort(data, size); for (i = 0; i < size; i++) printf("%d ", data[i]); }
桶排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。