计数排序

常见的排序算法都是基于比较的，这些算法的时间复杂度最好也只能到O (n*lg (n))，而实际上的排序算法的时间复杂度也是能够达到O(n)的，用空间来换时间，比如说这里的计数排序：

使用计数排序有一定的前提，需要知道数组中最大的元素（其实不知道也是可以的，多遍历一次找出最大值罢了），假设这个值为k。基本的原理是构造一个长度为k + 1的数组c，用来保存要排序数组a中每个元素的出现次数。

算法中包括4个循环，第一个循环仅仅是把这个数组c置零（我忽然想起来，为啥不用memset呢……）。
第二个循环取得了数组a中每个元素出现的次数。

那么要怎么进行排序呢？

直接遍历数组c？不行，这样时间复杂度变变成O(n^2)了

于是，第三个循环从第二个元素开始，依次累加前一个元素的值。对于数组a中的每个元素a[i]，这样我们得到了整个数组中有几个元素小于等于a[i]，这也就是a[i]应该出现的位置。

第四个循环就按照这个位置在新的数组b中填充元素，排序完成。这一步不是很好理解，看看代码仔细体会一下。

BTW，这个代码还有点问题，假如元素中还有负数，算法就需要修改了；
假如传入的两个数组长度不同，也没法得到完整的排序。

#include "array_sort.h"
#include "base.h"

/**
 * @brief counting sort
 *
 * @note Complexity O ( n );
 * @param a the input array;
 * @param b the sorted output array, only len_b elements will be written
 * @param len_a length of array a;
 * @param len_b length of array b;
 * @param k all elements in array a should be lesser than or equal to k;
 * @return the sorted array, that is array b;
 */
int *counting_sort (int *a, int *b, int len_a, int len_b, int k)
{
	int i, j;
	/* there are (k + 1) elements between 0 and k */
	int c[k + 1];
	for (i = 0; i <= k; i++)
	{
		c[i] = 0;
	}

	/* c[i]: contains number of element i */
	for (j = 0; j < len_a; j++)
	{
		c[a[j]]++;
	}

	/* c[i]: contians numbers than lesser than or equal to element i */
	for (i = 1; i <= k; i++)
	{
		c[i] += c[i-1];
	}

	for (j = len_a - 1, i = 0; (i < len_b) && (j >= 0); j--, i++)
	{
		/**
		 * j: 			index of array i, range (0, len_a - 1);
		 * a[j]:		In array a, what's in index j?
		 * c[ a[j] ]:	how many elements are lesser than or equal to a[j]?
		 * c[a[j]] - 1:	In array b, where's the position for a[j]?
		 * b[c[a[j]] - 1] = a[j]:	place a[j] to the right position on array b.
		 */
		b[c[a[j]] - 1] = a[j];
		/* we have add a[j] to array b, reduce counting by 1 */
		(c[a[j]])--;
	}

	return b;
}