COUNTING-SORT(计数排序) and

计数排序         

        计数排序假设n个输入元素（适用于小范围区间）中的每一个都是在0到k区间内的一个整数，其中k为某个整数。当k=O(n)时，排序的运行时间为.

        计数排序的基本思想：对每一个输入的元素x，确定小于x的元素个数。利用这一信息，就可以直接把x放到它在输出数组中的位置上了。例如，如果有17个元素小于x，则x就应该在第18个输出位置上。当有几个元素相同时，这一方案要略做修改。因为不能把它们放在同一个输出位置上。

         我们假设个数组 A[0...n-1 ],   A.length = n,  k 为A中最大元素，我们还需要两个数组：B(0...n)存放排序的输出，C[0...k] 提供临时存储空间

伪代码：

COUNTING-SORT(A , B , k)

        let C[0...k]  be a new array            

        for i = 0 to k                             //将数组C都置为0

                C[ i ] = 0

        for j = 0 to A.length                        

                C[ A [ j ] ] = C[ A [ j ] ] + 1

        for i = 1 to k                                        //找到元素的位置

             C [ i ] = C[ i ] + C[ i -1 ];   

        for j = A.length downto 0

                B[ C[ A[ j ] ]  - 1 ]  =A[ j ]

                C[ A[ j ] ]  = C[ A[ j ] ] -1

看图理解：

根据上图排完序后相同元素的位置与排之前相同，所以计数排序是稳定的排序。

算法分析：

COUNTING-SORT(A , B , k)

        let C[0...k]  be a new array                     1

        for i = 0 to k                                             k+1

                C[ i ] = 0                                           k

        for j = 0 to A.length                                   n+1

                C[ A [ j ] ] = C[ A [ j ] ] + 1                  n

        for i = 1 to k                                                k

             C [ i ] = C[ i ] + C[ i -1 ];                           k-1

        for j = A.length downto 0                             n+1

                B[ C[ A[ j ] ]  - 1 ]  =A[ j ]                      n

                C[ A[ j ] ]  = C[ A[ j ] ] -1                         n

可知时间消耗为

我们写一个存在负数的计数排序代码：

#include<iostream>
using namespace std;

//计数排序
void COUNTING_SORT(int A[], int B[],int k,int size,int n)
{
	int* C = (int*)malloc(sizeof(int) * k);
	for (int i = 0; i < k; ++i)
	{
		C[i] = 0;
	}
	for (int j = 0; j < size; ++j)
	{
		C[A[j] + n]++;
	}
	for (int i = 1; i < k; ++i)
	{
		C[i] = C[i] + C[i - 1];
	}
	for (int j = size - 1; j >= 0; --j)
	{
		B[C[A[j]+n]-1] = A[j];
		C[A[j] + n]--;
	}
	free(C);
}

//打印
void Print(int A[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		cout << A[i] << " ";
	}
	cout << endl;
}
int main()
{
	int A[] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };//想要负数存入计数数组C中，要将负数变为正数
	int size = sizeof(A) / sizeof(int);
	int n = 25; //每个元素都加上n值存入数组C
	int k = 46;
	int B[16];
	cout << "要排列的数组为：" << endl;
	Print(A, size);
	COUNTING_SORT(A, B, k, size,n);
	cout << "使用计数排序后：" << endl;
	Print(B, size);

}

结果:

要排列的数组为：
13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7
使用计数排序后：
-25 -23 -22 -16 -7 -5 -4 -3 -3 7 12 13 15 18 20 20