桶排序

广告位

存储桶排序也称为bin 排序。它的工作原理是将元素分配到也称为存储桶的数组中。 桶使用不同的排序算法单独排序。…

存储桶排序也称为bin 排序。它的工作原理是将元素分配到也称为存储桶的数组中。 桶使用不同的排序算法单独排序。

桶排序的复杂性

算法 复杂性
空间 O(1)
最坏情况 O(n^2)
最好情况 Ω(n+k)
平均情况 θ(n+k)

算法

第1步,开始 第2步,设置一个最初为空的“桶”(`buckets`)数组。 第3步,分散:遍历原始数组,将每个对象放入其存储桶中。 第4步,对每个非空桶进行排序。 第5步,收集:按顺序访问存储桶并将所有元素放回原始数组中。 第6步,停止 

使用C语言实现桶排序算法如下 –

#include <stdio.h>   void Bucket_Sort(int array[], int n)   {         int i, j;         int count[n];        for (i = 0; i < n; i++)           count[i] = 0;        for (i = 0; i < n; i++)           (count[array[i]])++;        for (i = 0, j = 0; i < n; i++)             for(; count[i] > 0; (count[i])--)               array[j++] = i;   }      /* End of Bucket_Sort() */    /* The main() begins */   int main()   {       int array[100], i, num;         printf("Enter the size of array : ");          scanf("%d", &num);          printf("Enter the %d elements to be sorted:n",num);        for (i = 0; i < num; i++)           scanf("%d", &array[i]);        printf("The array of elements before sorting : n");       for (i = 0; i < num; i++)           printf("%d ", array[i]);         printf("The array of elements after sorting : n");        Bucket_Sort(array, num);        for (i = 0; i < num; i++)           printf("%d ", array[i]);          printf("n");            return 0;   } 

  

洁姐我爱你

关于作者: 洁姐我爱你

为您推荐

广告位

发表评论