首页 > 代码库 > 桶排序

桶排序

桶排序 (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]);    }

 

桶排序