计数排序

1.计数排序的定义和原理
计数排序（Counting sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组C ，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组 C 来将A中的元素排到正确的位置。

如图所示：

贴代码

head.h

#ifndef HEAD_H
#define HEAD_H
#include<iostream>
#include<time.h>
#include <iomanip>

using namespace std;

#define MaxSize 30

void  Count_Sort(int a[],int len);
void Array_generate(int a[], int len);

operation.cpp

#include"head.h"
void Array_generate(int a[], int len)//生成一个随机数组
{
	srand(time(NULL));
	for (int i = 0;i < len;i++)
	{
		a[i] = rand() % 100;
	}
	for (int j = 0;j < len;j++)
	{
		cout << setw(3) << a[j];
	}
	cout << endl;
}

void Count_Sort(int a[], int len)
{

			//确定数列最大值
			int max = a[0];
			int min = a[0];
			for (int i = 1; i < len; ++i)
			{
				if (a[i] > max)
					max = a[i];
				if (a[i] < min)
					min = a[i];
			}

			int d = max - min;             //最大值与最小值之间最多有max-min+1种“元素”
			int* count = new int[d+1];
	    	memset(count, 0, sizeof(int) * (d+1));
			/*注：在我将int d = max - min;写成int d = max - min+1; 的时候调试的时候,vs会弹出
			一个叫Debug Error的警告框我也不知道为什么。写成前面那种样子就没事.
			如果有人用我的代码如果这种情况或者你们知道为什么会这样你们评论里告诉我一声*/
			                               
			for (int i = 0; i < len; ++i)    // 遍历数组，统计每个数出现的次数
				count[a[i] - min]++;
			                               
			for (int i = 1; i <= d; ++i)
				count[i] += count[i - 1];      // 后面的元素下标右边界等于自己元素个数与前面的元素下标之和
			                                
			int* sorted = new int[len];         // 倒序遍历原始数组，从统计数组找到正确的位置，输出到结果数组
			for (int i = len - 1; i >= 0; i--)
			{
				sorted[count[a[i] - min] - 1] = a[i]; 
				count[a[i] - min]--;        
			}
			for (int i = 0;i < len;i++)
			{
				a[i] = sorted[i];
			}

		delete[]sorted;
		delete[]count;
	
}

main.cpp

#include"head.h"


int main()
{
	
	int  len;
	int  a[MaxSize];
	cout << "输入随机数组元素个数" << endl;
	cin >> len;
	cout << endl;
	cout << "生成一个元素个数为" << len << "的随机数组" << endl;
	Array_generate(a, len);
    cout << endl;

   
	cout <<" 计数排序结果如下：" << endl;
	Count_Sort(a,len);
    for (int i = 0; i < len; ++i)
        cout << setw(3)<<a[i];   
    return 0;
}