(1)原理和代码以及时间复杂度分析          1.计数排序的原理：设被排序的数组为A,排序后存储到B，C为临时数组。所谓计数，首先是通过一个数组C[i]计算大小等于i的元素个数，此过程只需要一次循环遍历就可以；在此基础上，计算小于或者等于i的元素个数，也是一重循环就完成。下一步是关键：逆序循环，从length[A]到1，将A[i]放到B中第C[A[i]]个位置上。原理是：C[A[i]]表示小于等于a[i]的元素个数，正好是A[i]排序后应该在的位置。而且从length[A]到1逆序循环，可以保证相同元素间的相对顺序不变，这也是计数排序稳定性的体现。在数组A有附件属性的时候，稳定性是非常重要的。          2.计数排序的前提及适用范围:A中的元素不能大于k,而且元素要作为数组的下标，所以元素应该为非负整数。而且如果A中有很大的元素，不能够分配足够大的空间。所以计数排序有很大局限性，其主要适用于元素个数多，但是普遍不太大而且总小于k的情况，这种情况下使用计数排序可以获得很高的效率。          3.算法代码及测试代码：          [cpp] view plaincopy#include <stdio.h>  #include <conio.h>  #define MAX 1000    //函数原型  void counting_sort(int A[],int length_A,int B[],int k);    //测试代码  int main()  {      int A[]={-1,2,6,5,4,8,9,7,1,10,3};//1到10,十个测试数据      int B[11]={0};      int k=10;//所有测试数据都处于0到k之间      counting_sort(A,10,B,k);      for(int i=1;i<11;i++)          printf("%d ",B[i]);      getch();  }    //计数排序  void counting_sort(int A[],int length_A,int B[],int k)  {      int C[MAX]={0};//C是临时数组      for(int i=1;i<=length_A;i++)          C[A[i]]++;      //此时C[i]包含等于i的元素个数      for(int i=1;i<=k;i++)          C[i]=C[i]+C[i-1];      //此时C[i]包含小于或者等于i的元素个数      for(int i=length_A;i>=1;i--)//从length_A到1逆序遍历是为了保证相同元素排序后的相对顺序不改变      {                           //如果从1到length_A,则相同元素的相对顺序会逆序，但结果也是正确的          B[C[A[i]]]=A[i];          C[A[i]]--;      }  }           4.时间复杂度分析：整个counting_sort中，只有3个单重循环，所以时间复杂度为O(n)。属于非比较类型的排序，比较类型的排序的时间下界都是O(nlogn)         (2)计数排序的扩展         1.对负数排序的扩展思路：计数排序要求元素能够作为数组的下标，自然不能是负数。我的思路是先把负数和非负数分离开来，对负数取绝对值，再对这两组数分别计数排序，最后再把两组数合并可以了。时间复杂度依旧是O(n)，只是n会大一点。当然处理的都是整数。         2.对浮点数排序的扩展思路：浮点数不能作为数组下标。先后否定了自己两个比较鸡肋的办法，这里写一个我认为可以作为基础的算法，但是还需要非常大的改进。把一个浮点数存储在一个链表中，每个结点存储一位，然后对每一组结点进行计数排序。这样会导致O(n2)的时间复杂度，我还没想到如何进行优化，如果您有思路，请告诉小弟我，非常感谢。         总结：计数排序不是就地排序，需要借助一个辅助空间并且存储结果到另一个空间，而且适用范围相对狭窄，但是却有着O(n)的时间复杂度。我现在理解到算法设计就是在时间和空间，以及适用范围之间找一个最优的平衡点。相关文章：快速排序的随机化版本    快速排序的优化算法   归并排序的递归算法    堆排序  归并排序的非递归算法
http://blog.csdn.net/neilhappy/article/details/7202507