线性时间排序--桶排

1、桶排序

创新互联长期为千余家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为丰顺企业提供专业的做网站、网站制作，丰顺网站改版等技术服务。拥有10年丰富建站经验和众多成功案例,为您定制开发。

  可以排序的范围数较小，是一种以空间换时间的排序算法；

  不考虑重复元素的出现---->桶排；解决方案在计数排序；

  (1)、代码实现

#include

void bucketSort(int *a, int count);
void showArray(int *a, int count);

void showArray(int *a, int count){
    int i;

    for(i = 0; i < count; i++){
        printf("%d ", a[i]);
    }
    printf("\n");
}

void bucketSort(int *a, int count){
    int b[10] = {0};  //知道要排序值的最大范围
    int i;
    int n = 0;

    for(i = 0; i < count; i++){
        b[a[i]]++;
    }

    for(i = 0; i < 10; i++){
        if(b[i]){
            a[n++] = i;
        }
    }
}

void main(void){
    int a[] = {3, 5, 1, 8, 9, 6};
    int count = sizeof(a)/sizeof(int);

    bucketSort(a, count);
    showArray(a, count);
}

  (2)、结果截图

  (3)、算法分析

  时间复杂度：O(n);