C++ 计数排序算法的实现与改进(含笔试面试题)

      计数排序局限性比较大，算法思想：假定输入是有一个小范围内的整数构成的（比如年龄等），利用额外的数组去记录元素应该排列的位置，思想比较简单。

      计数排序是典型的不是基于比较的排序算法，基于比较的排序算法最少也要O(nlogn)，有没有可能创造线性时间的排序算法呢？那就是不基于比较的排序算法；

      如果数组的数据范围为0~100，则很适合此算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序

算法步骤：

1、找出待排序的数组中最大和最小的元素

2、统计数组中每个值为i的元素出现的次数，存入数组C的第i项

3、对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）

4、反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

实现代码：

/***************************************************************************
 *  @file       main.cpp
 *  @author     MISAYAONE
 *  @date       27  March 2017
 *  @remark     27  March 2017 
 *  @theme      Counting Sort 
 ***************************************************************************/

#include <iostream>
#include <vector>
#include <time.h>
#include <Windows.h>
using namespace std;

void Counting_sort(int a[], size_t n, int k)
{
	//申请额外空间
	int *p = new int[n];
	int *q = new int[k+1];
	for (int i = 0; i < k; ++i)
	{
		q[i] = 0;//将q指向的数组所有元素置0
	}

	//保存数组a中每个元素出现的个数，将排序交给了q数组(其顺序在q数组中就是有序的)
	
	for (int j = 0; j < n; ++j)
	{
		q[a[j]]++ ;
	}
		

	//将所有计数次数累加
	for (int i = 1; i < k; ++i)
	{
		q[i] = q[i] + q[i-1];
	}


	//将元素重新输入
	for (int i = n-1; i >= 0; --i)
	{
		//次数大小最小为1、数组开始为0
		p[q[a[i]]-1] = a[i];
		q[a[i]]--;
	}

	for (int j = 0; j < n; ++j)
	{
		a[j] = p[j];
	}
	//不要忘了释放分配的空间
	delete []p;
	delete []q;
}

int main(int argc, char **argv)
{
	int a[10] = {2,56,4,2,9,56,3,59,9,16};
	int max = a[0];
	for (int i = 1;i < 10; ++i)
	{
		if (a[i]>max)
		{
			max = a[i];
		}
	}

	Counting_sort(a,10,max+1);//传入max+1是为了让计数的数组从0开始足够大
	for (int i = 0; i < 10; ++i)
	{
		cout<<a[i]<<" ";
	}
	cin.get();
	return 0;
}
           

复杂度分析：

在一定限制下时间复杂度为O(n)，额外空间O(n)（需要两个数组）

O(n+k), n为原数组长度，k为数据范围

特点：稳定排序stable_sort，out_place排序

例题1、某地区年龄排序问题？

够典型的计数排序吧，年龄的区间也就那么大，代码就不上了，请参照上述参照计数排序算法。