木桶排序

bucket.c

#include <stdio.h>
#define MAXNUM 100 // Count数组大小(M)
/* 功能：桶式排序
 * 输入: 待排序数组arrayForSort[]
 * 待排序数组大小arraySize (N)
 * 上界maxitem，元素都落在[0, maxitem]
 * 输出 void
 * 时间复杂度 O(M+N)
 */

void BucketSort(int arrayForSort[], int arraySize, int maxitem);

int main(void){
  int a[] = {2, 5, 6, 12, 4, 8, 8, 6, 7, 8, 8, 10, 7, 6, 0, 1};
  BucketSort(a, sizeof(a) / sizeof(a[0]), 12);
  return 0;
}

void BucketSort(int arrayForSort[], int arraySize, int maxitem){
  int Count[MAXNUM];
  int i, j;
  for(i = 0; i <= maxitem; i++)
    Count[i] = 0;
  for(i = 0; i <= arraySize; i++)
    Count[arrayForSort[i]]++;
  for(i = 0; i <= maxitem; i++)
    for(j = 1; j <= Count[i]; j++)
      printf("%3d", i);
  printf("\n");
}