排序算法:计数排序

算法思想:

假设有6个数分别代表6个人竞选，{5,2,8,7,4,3}

有六个投票箱，初始值为0，{0,0,0,0,0,0}

有六个桶，表示按投票箱票数最终放的位置，即排序结果

首先给5投票，比5小的数给5投票，2，4，3均比5小，5得三票，{3,0,0,0,0,0}

然后给2投票，由于2是6个数中的最小值，所以2得0票，自己的1票在这不算哦！依旧是{3,0,0,0,0,0}

依次类推，最后投票箱的投票情况为{3,0,5,4,2,1}

然后把投票箱放到相应的位置，这里赋桶的初始值为-1，即{-1,-1,-1,-1,-1,-1}，为了方便区分票数相等的情况

{5,2,8,7,4,3}

{3,0,5,4,2,1}

{-1,-1,-1,-1,-1,-1}

3号桶应该放上数字5，0号桶放上数字2，5号桶放上数字8......

结果 {2,3,4,5,7,8}

附上简单粗暴的C代码:

#include <stdio.h> #include <malloc.h> #include <string.h> void countSort(int *a, int *bucket, int n) { int *vote = (int *)malloc(sizeof(int)*n), i, j, t; memset(vote, 0, sizeof(int)*n); memset(bucket, -1, sizeof(int)*n); for (i = 0; i < 6; i++) { for (j = 0; j < 6; j++) { if (j == i) continue; if (a[i] > a[j]) vote[i]++; } } for (i = 0; i < 6; i++) { if (bucket[vote[i]] == -1) { bucket[vote[i]] = a[i]; } else { int t = vote[i]+1; //解决票数相等的情况 while (bucket[t] != -1) t++; bucket[t] = a[i]; } } free(vote); } int main() { int a[] = {5,2,8,7,4,3}, bucket[6], i; countSort(a, bucket, 6); for (i = 0; i < 6; i++) printf("%d ", bucket[i]); return 0; }